競プロ日記

今回は最新問題。
解き始めたのは当日だが参加はしていない。
性格上コンテストに参加するのはかなり先になりそう。

コード①
https://atcoder.jp/contests/caddi2018b/submissions/3853552
コード②
https://atcoder.jp/contests/caddi2018b/submissions/3853928
コード③
https://atcoder.jp/contests/caddi2018b/submissions/3853945




一応解説は軽く目を通したが、初見で思い浮かんだ解き方と同じで嬉しい気持ちに。
ただ解説の書き方が難しすぎて一瞬こんな問題解けねぇと思った。


コード①
今回の挑戦は素因数分解のプログラムを探すことから始まった。
普通に2で割れるだけ割って・・・ってやってたら遅いでしょさすがに？って思いながら調べてたらまさかのこれが正解だった。
入力値大きいしこれだとTLEだろうと2で割るのをやめて2のn乗3のn乗と割っていく関数を作成したものの、ところどころ間違えたりTLEだったり。
回答例見るとみんな普通に素因数分解してるしn乗しなくていいや。

コード②
間違いが全く分からない。
他人のコード見て間違い探しするも分からない。
for文で最終的な答えを求めているコードを発見。
試しにその方式で書いてみるとあっさりAC。
？？？？？
割り算で誤差が出るのか？整数だぞ？切り下げじゃないのか？
むしろforの条件式にn入れるのって自然ではないのでは？
この方式思いつかないと答えでないってこの世界ついていけそうもない、なんて考えていた。

コード③
お前n乗じゃなくて×nしてるやんけ！！！
ということで、自分で思いついた書き方でACできた。
頭に思い描いたコードを間違いなく書けるようになってきた思ってたのにどこか間違ってるんだろうなぁ・・・、とそこそこ落ち込んでいた。
そういう次元じゃない間違いだったから少しホッとした。
自分らしいミスといえば自分らしい。


余談
最初に思いついたn乗で割っていくのを正しく書き直すとTLEだった。
条件式一緒な時点でそこそこ遅いpowを同じループ数繰り返すのは無駄。
条件式にn乗したものを使えばいけそうな気がするんだけど、うまい入れ方が分からなかった。
そもそも早くなる可能性が存在しない可能性まであるからとりあえず置いておく。


もう1つ余談。
この問題をやったのと同じ日にダイクストラ法を調べていて、初めてcontinueなんていう関数を知った。
この問題の他人のコードを調べている時に、素因数分解を行う関数でcontinueを使っているのを見て結構な未来を感じた。
もともとループ内で無駄な宣言を省こうと考えて書いていたのだが、continueを入れるだけでずいぶんとすっきり見やすくさらに速度アップと来た。
繰り返し文では積極的に使っていきたい。

同時に、参照渡しした引数に結果を代入する形式からmap型の戻り値を持つ関数に変更した。
どちらが早いかは知らないが、複数の値を持ち得る戻り値にできることを忘れていた。
しばらくプログラムを書いていなかったため、頭に学生時代のCの「戻り値は1個だけ。複数戻したかったらポインタ型引数。」しか残っていなかった。
どう考えても戻り値設定した方が見やすいから忘れないように・・・。


次回はyukicoder No1のリベンジの予定。
ダイクストラ法の関数は作成済み。