DDCC2020参加メモ

忘れないうちにメモ

コード部門

A

Grundy数を愚直に求めてXORした。ここでGrundy数は素因数の重複を許した個数になっていることが解説に書いてあって、少し考えると確かにそれはそう

B

よくわからなかったので、パス

C

ずっと睨んでいると、後ろから順に [i, i+1) 区間を作っていって、区間の中の要素を比較して前にある区間のほうが小さいなら後ろの区間にマージ、という処理をし続けると、1番前にある区間の右端が答えになる気がします。区間の値を全て愚直に持たせながらマージするとalmost_sameの2ケースでTLE。もう少し睨むと、マージさせるときに必要なものは区間の左端と右端だけでいいことがわかったので書き直していたけど、バグらせて5分27秒遅れでAC。計算量はたぶん $O(N \log{N})$ 。Suffix Arrayを知っていますか？僕は知りません。勉強します。

あんまり同じことしてる人がいなさそうなので提出も貼っとく: https://atcoder.jp/contests/ddcc2020-final/submissions/9706271

装置実装部門予選

とりあえず0点ACを狙います -> WA -> 0点AC (7:27)
座標が固定されているCで補給して戻るだけの実装を書く -> WA -> WA -> 4198018点 (33:00)
次の補給で溢れさせないため、60000msで全て排出しきれない場合は排出しきるまで繰り返す -> WA -> 4227938点 (39:50)
Cの次はAに行って戻る。Aのアームの角度は90度にしようとしたがWA
アームが間に合ってないのかなと考えてスタート位置のまま0度で固定 -> 8783825点 (45:34)
このあたりで決勝進出できるのでは? と思い始める
Aに行って戻った後に、Cに行く実装を貼る -> 12178788点 (47:05)
この後Bに行こうとしてとりあえず50000個素数列挙しようとするが、急ぎだったのでうっかり $O(N \sqrt{N}) (N=10^{6})$ になってしまいTLE (は?)
最初にBに行けば素数列挙サボれる! -> 15111211点 (59:28)
結局12位で通過。最後の伸びがなくても20位でぎりぎり通ってたっぽい
昼休みは食事をしながら速い素数列挙について考えていた