naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 024

5/20(日) 21:00 - 23:10 (2時間10分)
3問解いた後眠かったけど頑張った。
3完で303位。パフォーマンスは2043で、レートは1699→1745 (+46)
f:id:n4_t:20180521001335p:plain:w400

A - Fairness (300)

S=A+B+Cとする
(A,B,C) -> (B+C=S-A, C+A=S-B, A+B=S-C) -> (2A+B+C=S+A, A+2B+C=S+B, A+B+2C=S+C) -> ...
みたいに (kS±A, kS±B, kS±C) な感じで推移するので
A-Bにあたるところは A-BとB-Aを交互に繰り返す。
AもBも1e9以内なので、その差は"Unfair"になることはない。
→AC (4:17)
https://agc024.contest.atcoder.jp/submissions/2532882

B - Backfront (500)

前に持っていく数と後ろに持っていく数、それ自体動かさない数、があって
それ自体動かさない数、は単調増加でかつ連続している必要がある。
動かさない部分(=単調増加でかつ連続している部分列)の長さが分かれば、(N - その長さ)の分だけ前なり後ろなりに移動するわけで、最長の部分列を見つければその移動分を最小化できる。
最長の部分列は、xi-1が既出かを調べて、そこまでの部分列の長さを記録していくことでO(N)で求めることができる。
→AC (20:13)
https://agc024.contest.atcoder.jp/submissions/2534698

C - Sequence Growing Easy (700)

0で始まらない場合は無理。
0で始まって0,1,2,3,...と連続していれば(後ろから)消していける。
連続していない部分で、上にジャンプしていると無理(例:0,1,2,3,5)。
下に落ちている場合(例:0,1,2,3,2)は、その間に0,1,...n-1を挟んだのと同じことになる。(=0,1,2,3,0,1,2)
で0以外の数の個数が答え
→AC (46:55)
https://agc024.contest.atcoder.jp/submissions/2536814

D - Isomorphism Freak (1100)

頂点が対称の中心になるケースと、辺が対称の中心になるケースに分けて
BFS的に埋めていく(というか数えていく)作戦
実装が間に合わず、残り5秒のところで手持ちのコードを記念submit→WA
https://agc024.contest.atcoder.jp/submissions/2540898
テストケースの半分ぐらいがACで残り半分ぐらいがWAだった。(どっちかが間違ってる?)

E - Sequence Growing Hard (1200)

問題は読んだ
暫く考えたけどそっ閉じ

F - Simple Subsequence Problem (2300)

開いてない