こいついっつも敗退記書いてるな
0日目
普通に学校に行ってAGCを解いた。改名後初AC
https://atcoder.jp/contests/agc014/submissions/10023735
家で17本選のバチャをやるが、なんと1番も2番も解けず0完太陽をしてしまった。☀☀☀
1番はordを見るという頭がなく、大小比較とGCDだけで解こうとしていたのが間違いだった。
数論の三種の神器(ord,mod,gcd)使いこなしたい
— 破滅* (@Rho4913) 2020年2月10日
2番はどうせ後の方が定数になるとわかっていたが、証明できなかった。
当日
10時30分くらいに起きて適当に会場に行く 会場でb2563125と握手した あと久々にcn449に会った
No.1
手でnを13くらいまで実験すると、あまりに大きいnだと不可能そうなことに気づく。隣り合う平方数で挟むやつをやるだけに気づくが、不等式評価で真面目に証明を書いたので1時間くらいかかった。
No.2
とりあえず作図だけしたが何もわからない。角度を多少追っても何も嬉しくなかった。3や4を解く間にときおり見に来たが相変わらずわからなかった。
No.3
mとnをswapして引いてみたがよくわからない。数値代入はもっとよくわからない。なぜかこれに1.5時間くらい費やした。
No.4
問題文が長いので言い換える。 「3n個の白い頂点があります。先手のA君は辺を1本貼ります。後手のB君は頂点を一つ黒く塗ります。n回操作後の盤面で、片方の頂点が白でもう片方が黒である辺の数をスコアと定義します。スコアが(n-1)/6以上ならA君の勝ちです。A君が勝つ戦略を出力してください。」
貪欲に黒と結ぶと最大スコアが1しかv出ないことはすぐ見えた。適当に手元で実験したうえでエスパーをすると、このような構築が思いつく。
- 最初に2n/3個の白ー白ペアをつくる。
- 黒と白―白ペアの端点を結ぶ。
これでいけそうなことがわかったのでそこまで書いたが、証明の時間が足りずあえなく終了。
No.5
見てない もえがら氏によると自明なケースはすぐ見つかるらしい
総括
記述力がないので1完できたか怪しい。得られた教訓は
- 自分の得意分野が何かを見極める
- 並列考察をしない
予選に通ったのが完全に問題セットと運なので、来年も同じように行けるかはわからない。