Memo

Twitterに書くには長すぎることを書きます。Opinions are my own.

AtCoder Grand Contest 035 感想

戦略

Aだけ通してもレート上がらないのでまずBとCを読みます

B

わからない

葉になっているところは自明だから、葉を決めて葉につながる辺を削除を繰り返し、葉が存在する間は自明に定まるなぁと思ったけど残りをどう構成すればいいかわからない

C

4k+3 の場合は (1-2-3-1-2-3-4-5-6-7-4-5-6-7- ... - 4k+3) のような感じで1直線の木が構成できる -> 投げたらWA

よくよく考えてみると 4k+1 の場合も構成できるので投げる -> WA 「これは偶数も構成できるやつだなー、だけど構成例が思いつかないなー」と思っている間に潜伏が失敗していることに気づいたのでAを通す (51:15, a^b==c を書いてしまい1WA)

n == 2k の場合が自明にアウトで、それ以外の偶数も構成できたのでごり押す -> 雑をしすぎてTLE+WA -> 修正すると通る (94:31, 3ペナ)

Cが解けなかったら超絶冷えるなーと思ってたけど、時間をかければ通せそうだったのでそこまで不安に思っていなかった

D

軽く読んだけど残り時間で解ける気がしない

B

葉が存在しない場合は適当に1つ決め打ちする、という嘘解法を書いている間に時間終了。 嘘解法が仕上がって投げたけど通らなかったので、テストケース強いなーと思った

結果

2完(o-o---)の310位でレートは微減ですんだ。今のレートだから微減で済んだけど、もっとレートが上がってからこれをやるともっと冷えるのでもっと頑張りましょうという感じです。