JAG 2017 day1 (snukeセット)

Programming 参加記 ICPC

Tasks - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder


A:しりとり
適当なオイラー閉路を考えてその途中までを取るとか考えると正当性がわかりやすい

B:リス
ちょっと迷走仕掛けたが、「最終的な場所」で考えればいいことがわかる

C:すごろく
動的FFTみたいなやつ(segtreeっぽい といってもいいかも)
左からDPを埋めるとして、ある区間を正しく計算する関数calc(l,r) を用意する.
calc(l,r)では、分割統治っぽく、まずcalc(l,m)を呼んで、次に[l,m) から[m,r) への全ての遷移をFFTでやって、最後にcalc(m,r)分を追加する とやればよい.

コンテスト中は面に出てくる値の種類が多い時は速く終わるからモンテカルロ とかやってました(カス)

D:くさかべ
ま、幾何ライブラリ写経したんですけどね(ここらへんもはやタイトルが全く関係ない)

E:ベクトル式
BNFを書き換えたほうがいい みたいな問題はたまにあるので、これLLじゃないよ～とか思ったら考えたほうがいいと思います

F:逆から見てにぶたんすると片方向きだけでいい.左から貪欲に取ると右方向には極小(そ)

G:2リストらしい.頑張ってグラフを作ると一般の場合でも解けるが、H=2だとサイクルができちゃうケースが限られているのでそれだけやればOK

H:

過半数がどうこう、よりまず自由度3で条件2だから一つ決めればすべて決まるというのに気づくのが重要

イベルタルってこんな動き方するんですか?(いいえ)

I:
フローに必要な辺 のやつ
正当性は簡単.
あるフローFを固定する.Fの残余グラフの(有向)サイクルに含まれない→確定(Fに含まれてる⇔かならず使う,含まれてない⇔必ず使わない)
含まれてるならそれにそって流せばその辺は消せるので、どっちもありうる.
x→y があるサイクルに含まれている ⇔ sccでa,bが同じ成分 なので余裕

J:
2WA(ha?)

K:パンプキン
一応式を書くとa+bがデカい順でOK.

ちゃんと「ん」で終わってしりとりが終了している.
最近始めたので読解がすんなり出来た.裁きの光ってカードが好きです.