脳log[20200803] AtCoder Beginner Contest 174／C 問題 Repsept

最終更新: 2020-09-03T17:14+0900

♪ [AtCoder] AtCoder Beginner Contest 174／C 問題 Repsept

時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。

解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。

 提出 #15651178 (AC / 306 Byte / 136 ms / 14428 KB)

 提出 #15663806 (AC / 294 Byte / 118 ms / 14508 KB) ※無駄を省いて整理したもの

布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。

たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか

うん、これが解らない。

K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列７の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。

でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。

 Ruby によるすべての提出

他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え？ 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの？ (※桁が大きくなりすぎるので余りにだけ注目する必要はある)

たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に２回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。

 「おかしなこと」の説明をば

1. 与えられた K の１の位の数字を見る。
2. １、３、７、９なら掛ける数を(１から９から)選べば１の位に７が作れる。
3. 作りました。１の位の７はもう無視します。(K にある数を掛けてできた数の)１の位ではないところに７か７ではない数字が残ります。
4. 次はそれに、K に(０から９の)何を掛けたものを足せば末尾に７が作れるかを考えます。
5. 以下３へループ。
6. ３から５は要は K に何を掛ければ７の列になるのか、１の位から順に決定していこうという手順。筆算をイメージしながら。
7. たぶん、運が良ければ、もしくは不思議な法則に従って、掛けてできた数字のどの桁も７になることがあるでしょう。
8. 全部で７がいくつ作られましたか？ というのが答え。

 「7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた」

「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。

 逆元？

この問題の２つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。」

(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……

公式解説は累積和だね、横一列を1回の掛け算で済ます方法

僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた

抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う