AtCoder 第一回日本最強プログラマー学生選手権-予選- 参戦記
AtCoder 第一回日本最強プログラマー学生選手権-予選- に参戦しました。学生だったのははるか昔、本選参加資格もイベント参加資格もないですが、一コンテストとして参加しました。
結果は 46 分で ABD (1 WA) が取れ、D の 600 点問題が取れたのでパフォーマンス 2000 となりました。
500 点問題が取れなかったのが悔しいですが、600 のグラフをとれてまずまずの成功回となりました。
感想
A 問題
やるだけ...だが実装してみると手元 WA。よくみると各桁の数字が 2 以上だった。
B 問題
特定の Ai に注目すると、これの転倒数への寄与は
- A 中の転倒数 * K
- A の中の Ai より大きい数 * (K * (K - 1) / 2)
となるのでそれを実装。転倒数とかを求めるのは 2 重ループまわせばよい
C 問題
考えたがわからなかった。なにか見落としたのであとで解説 AC する。
D 問題
- 同じレベルの通路を行き来して戻ったら偶数回移動 ⇔ そのレベルの通路で長さが奇数の閉路が存在しない
- (おそらく) 同じレベルの通路を最大限埋めるのが最善
ということなので、
- グラフの各頂点を順番に 0, 1 でマークする
- 0 と 1 が違う頂点同士にそのレベルの辺をはる
- 0 同士, 1 同士でレベルを +1 して再帰
で実装して AC
E 問題
ちらっと見たが手をださなかった
