[AtCoder 参加感想] 2019/05/04:AGC033

  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踏みましたw

しかし、問題Aに続いてTLE。問題Aでだいぶ精神削られてたので、すぐにC++に逃げてぎりぎり時間内にAC。

後日談。TLEしたコード修正後ACしたコード
一般に、短い処理をたくさん再帰呼び出しして実装するよりも、簡単に書けるならループで書いてしまった方が、関数呼び出しのオーバーヘッドがなくなるので定数倍改善になります。

タイトルとURLをコピーしました