TCO2018 3A

開始前: touristいるやん!
easy:
自然な設定だな→
まあまず最後がAだったら流石にB負けるな→
まあd=1があるな(冷静)→
最後がBの場合は、d ≦ 10 ならBは絶対勝てるな、それ以外ならA勝ち?→
よく考えるとd=11,N=2はB勝ちだな→
d > 11 なら流石に最後から2桁目で無理なのを選べるな→
残りは d=11,N偶数. これはBが直前のAの数字を繰り返せば勝てる

med:
めんどそう→
どうせ0があると分けれそう→
分けれた→
各区間では、符号と大きさを考えて大きさの方はにぶたんとかすればいいかな→
値がでかすぎるので、logを取って累積和、実際の値はmodintで計算かなあ･･･→
log2(x) ≦ 30 とかにしないとmodでオーバーフローするけどギリギリすぎて怖いしやりたくない→
冷静に考えると累積積じゃなくてsegtreeに乗せればいいな→
書く→
符号周りの方を信じられないほどバグらせる

hard:
かなりmed遅れたので速く解きたい→
なんとなくgcjっぽい感じの設定、どうせ賢い解法があるんだろう→
2-regular subgraph を取ってきてなにかする? わからん →
全域木をとって全部0にすると、その葉3つで三角形が作られてしまうと終わる→
わからん→
全域木を取ったあとのcomplementを考えよう→
たかだか次数2なので、pathとcycleしかない→
pathしかなかったとするとそれを全部1にすればおわり→
サイクルがあったら1本除いて･･･→
･･････→
vertex disjoint な path集合を除いて残りが森になるようにしよう→
各タイミングでできるだけ極大なpathをとれば、サイクルが余ることはないな→
実装、提出、順位表を見に行く(残り8分?)→
冷静に考えると始点を固定しているので、まずいことに気づく(残り3分)→
書き換える、ギリギリまで悩んだあと、再提出

chal:
d=11をガン無視してるコードを一つ落とす、その後はhardの再提出前のコードが落ちるケースを作り、これで落ちそうなやつに投げる
→ 2 unsuccessful (どぼじで)
冷静になってコード読むと、dfsでbreakしていない→
じゃあ極大pathじゃなくてただのdfs木やんけ→
よく考えると僕のコードでもbreakしてないやん!(は?) 再提出の必要なかったね(結果論)→
悲しみに明け暮れながらmedの写経してたら取られた、おしまい

頭が悪いのでfull feedbackじゃないと無理。