いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ACPC2017Day3参加記

AIZU ONLINE JUDGE

起床ACした、もう勝ったも同然

Yazaten氏(@Yazaten)とらてあ宅で二人で出ました
チーム名は某氏のaotenjouを意識してyazatenjouで出ました
ABCD4完16位でした


Aを僕が、DをYazaten氏が、その後は随時って方針で
これ結構よかった説

A.A-Z-
文字列の大小比較をして現在のマス<=次のマスならインクリメントしといた
こんな簡単でええんかホンマか?って思って不安だったけど投げたらAC、まあはい

B.えびちゃんと数列 - Ebi-chan and Integer Sequences -
三角形みたいなの書いて反転分を2倍して同じ数字を加算して求めようとしてた
三角形が微調整が必要とか頭を抱えていた
Yazaten氏がDを通してくれたので相談すると、なんか別の方針を投げてくれてそれなら解けそうだと思う
とても辛いが、何とか等差数列で表せることが分かった
しかし愚直に求めるとTLEが見えるので考えて、適当に等差数列の和をググって式を作る
僕は辛いので途中まで考えて、コーナーケースとか投げてYazaten氏にお任せ

C.たったひとつの部分列 - Unique Subsequence -
簡単そうって思ったけどわかんない
全探索をするより良い方法が思いつかなくて、辛い
多分全探索のループ回数が10^5-1までの和とか、おわおわり
うーんうーんって悩んでたらYazaten城がB問題をWAしており、問題概要を伝えた
しばらく虚空を見つめ霞を食べた
唐突にYazaten城から解法が降ってきた
f:id:ratetion:20170921015932p:plain
前から取ったインデックスと後ろから取ったインデックス比較すればいいとの事、聞いた瞬間ACした、もちろん嘘だ
実装を任せてくれるとの事で、フォローもらいつつ実装、スタックを久々に使ってツライだね
なんとかなったのでAC

Bに戻って2人でツライした
コーナーケース探して、式を見直して、mod確認とかして、場合分けし直して
こんなケースはどう?って投げまくってたらmod取れてないケースがあった
場合分けした時の数値がそのままだった
modを取ったらAC

残り時間は45分で、後半の3問を眺めてどれもどうとか話してた
G問題が無茶苦茶楽しそうだったので考察でも練り続けたい
お疲れさまでした