| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ||||
| 結果 | AC | AC |
全体感想
問題AとCの2完でした。どちらも実行制限時間がきつめで、pythonでの攻略難易度が高かったです。
結局コンテスト中は、C++で書き直して通す。これも久しぶりのC++だったので、「セミコロンが足りません」「型が宣言されていません」と無限にバグを食らいながらの実装。
AtCoder環境で使える高速化手法に十分な知見がないため、はまりまくりました。まぁこれも良い経験ということで。
後日、コンテスト外でpythonでの高速化を頑張る。実行速度で不利というのは知っていながら、練習、勉強のためにpythonで参加しているので、アルゴリズムは合っているのに定数倍でTLEを食らう問題は、逆に勉強したいことのど真ん中という感じです。「分かっている」のに点数に繋がらないのが悔しいところではありますが、ひとまずレート上げることを重視しているわけではないので、勉強に役立てましょう。
問題A – Darker and Darker
幅優先探索をやるだけ、10分かからずpythonで実装は出来ていたのですが、TLE。
結局C++で書き直して90分かけてAC。
後日pythonで高速化の検証。
距離の近い点からqueueに突っ込んでいくアルゴリズムですが、今回は
・そもそも距離順に生成されるから、heapq等による並べ替えは不要
という特性があります。これ定数倍改善じゃなくて$\log N$倍ですね。そこで、dequeを試します。左から処理していって、タスクを右に積んでいきます。
こういう事情で、タスク一通り走査する場合、popしていくよりも普通に見ていく方が良い。そこで、動的にタスクを積んでいく実装は止めて、追加タスクを別リストに積んでいって、popせずにタスクを走査します。また、番兵を置いてif判定の回数を減らすなどの些細な努力も行って…
こうなった。まだTLE。これをさらに、こうする。これでAC。
4種の移動を、for文でなく分けて書くことで、定数倍改善になったようです。
この定数倍改善は、あまり褒められたものではないと思うけれど、一応手段として覚えておく。
問題C – Removing Coins
ノートにたくさん実例を書いていると、グラフの最長路（直径）が$-1$か$-2$の2通りであること、それをプレイヤが選べることに気づく。すると、よくある石取りゲームの簡単な場合と同じことになった。実装も簡単。
ノートに、$N=1$が例外だってことが赤文字で大きく書かれていたのに、きっちりWA踏みましたｗ
しかし、問題Aに続いてTLE。問題Aでだいぶ精神削られてたので、すぐにC++に逃げてぎりぎり時間内にAC。
後日談。TLEしたコード → 修正後ACしたコード。
一般に、短い処理をたくさん再帰呼び出しして実装するよりも、簡単に書けるならループで書いてしまった方が、関数呼び出しのオーバーヘッドがなくなるので定数倍改善になります。
