ARC113の感想

AtCoder Regular Contest113に参加しましたのでその感想を書いていきます。問題はこちらから。

結果はこんな感じでした。

1完(1wa)
順位：3162 / 3923
パフォーマンス：293

なんかすごいことになりました。これは失敗ってやつです。A問題の数え上げで見事に嵌って時間を使いすぎました。思ったより難しいなーって考えながら順位表を見ると、みなさん解いてる解いてる。どんどん焦りが大きくなりました。そこそこショックを受けていますが、気持ちを落ち着けるためにもコンテスト中に思ったことを書いていきます。こういうのって失敗したときに書く内容の方が重要だと思います。たぶん。

ではいきます。

A問題

A * B * C <= K 以下になる A, B, Cの組み合わせを求めます。

この問題でとっても時間を使いました。まず、愚直にやってみることを考えましたが、制約が10^5でしたので、その3重ループはダメそうですね。少しばかり工夫します。まず、Kの素因数分解を考えました。入力例1なら、２だけですね、これを使う使わない、また、A,B,Cのどこに入れるかで場合分けができるなって考えました。

ただし、ここで思考が止まってしまいました。どうするんだこれ？

そのあと、for文を2つ回してans += k / abとすることで、cを消しました。ここでいったん提出。ただ、TLEでした。終了後に答えを見ると、bの範囲でk/ i 的な感じで範囲を絞ればよかったみたいですね。

結局、acしたのは次のようなやり方です。

rb = k / iとする(iはaのインデックス)。rc = rb / j (jはbのインデックス)ってやると、cに関してO(1)で個数が求まる。また、jを増やしていくと、ｃは単調減少するから、どこかで1が出現するタイミングがある。1が出現したのちは1しかでてこないので、残ってるbの要素分を一斉にansに加算する。

といった感じです。なんというか、よくないですね。こんなことしてたらデバッグが大変なのもうなずけます。

B問題

a^b^cの1の桁の数を求めます。

1の桁って、循環するのでのそれを使おうとすぐに決意しました。こんな感じです。

0→0
1→1
2→4→8→6→2
3→9→7→1→3

こんな感じ、数字によってループ長が決まるので、それに対応したmodを設定しました。modの世界では割り算以外は好きなようにやっても計算結果は変わりません。それを考慮して、まずはb^cを考えました。bとcにそれぞれmodを取ってあげて計算。その結果b'を用いて、1桁目の循環のどの場所にいるかを求めれば答えになります。

と思ったのですが、2waが取れず。時間切れでした。

C問題

せめて到達したかった。

あとがき

正直とても悔しいですね。もう少しなんとかできたなーっていう思いが湧き出ます。でも、終わったものはしょうがないです。最近調子が良かっただけに、よいお薬をいただいたことにしましょう。また、今回は焦る中でもA問題をなんとか通したことを褒めておきます。明日から頑張ります。楽しんで頑張ります。