CODE FESTIVAL 2016 予選A - rickytheta's blog

3完で通りました。全体順位120位。

開始前

100-200-400-800-1200のWAペナ無しレート変動あり。明らかにやばい。めっちゃ緊張した。

前4文字と後8文字の間にスペースを入れるやつ。

最近stringのsubstrを使っていたので結構すぐに書けたけどコンパイルとテストをしたので若干FAから遅れる。

相互リンクの数を探すやつ。

最初若干解釈をミスって逆写像が一意に定まると勘違いした(？？？)。

setに被リンクを突っ込んでおいて入ってるかどうかをチェック、相互リンクの数を数えて2で割った。

指定された回数ちょうどだけ文字を1個後ろ(A→B、B→C、…、Z→A)にずらして辞書順最小を作る。

前から貪欲にAにすればOK。調節は一番最後の文字で。

ここまでで6分24秒。通ったな(確信)

左上+右下 = 右上+左下になるように非負数でグリッドの表を埋めるやつ。動機が謎すぎる。

W*H<=10¹⁰ なのでなんかヤバそう。これは早解きセットだな勝った(確信)

一応Eを読む。

数列がいっぱいあっていじる。いかにもAGCのEあたりにありそうな問題。

操作には与えられた数列を使うように言われてるので、直感で逆から見るんだろうなぁと思った。

でも逆から見るんだろうなぁ系の問題を本番で通したことが無いのと、点数傾斜から敬遠。Dに戻る。

まず与えられた式を変形すると任意の長方形の四隅で成り立つことが分かる。

で変形するとある列と列の間の差が等しいということは分かった。行についても同じ。

なので式の条件を満たすには行間と列間が求まればいいことが分かる。ついでに座標圧縮しても問題は変わらないことも分かる。

ここで全てのマスを実際に埋めるという明らかなTLE解を思いついたが、階段状に数字が埋まったケースがO(WH)個のマスに影響を与えるため即却下。

行ごと、列ごとに見て、行間の差がいくらか、というグラフを作り、BFSである点からの差(距離)がどれぐらいかというのを埋めていく。矛盾が生じたら即終了。

で、後は負数のチェックで、これはあるマスから行の差を足していけばそのマスを含む行の最小値が分かるので、RMQみたいなことをした。

ここから提出を繰り返すけどWAが取れず終了。初期化をバグらせたり非連結を対処してなかったりで散々だった。

結局早解きでも通過できそうだった。

Dの解説を読んで、行と列の値を決めたらr_i+c_jで表現できるとか書いてあって感動した。

Eは予想通り逆から見るやつだったけどこっちの方が簡単そうだった。残念。

賞金欲しいので本戦までにもうちょっと精進する。