AtCoder Grand Contest 013

参加しました。

問題A　Sorted Arrays

長さNの配列Aを何箇所かで区切って、すべての部分列を単調非減少or単調非増加列にするには最低何箇所必要かという問題。

前から見ていって貪欲で取っていく。単調非増加か単調非減少かを判定し、そうでなくなるところで区切って同じことを繰り返す。

→なんかサンプルが合わない。

よく見ると、最初の方は同じ数が連続するようなものに対して、非増加か非減少かをちゃんと判定できていなかった（2,2,2,1...と2,2,2,3...の区別ができていなかった）。

直してok。

問題B Hamiltonish Path

連結かつ単調なグラフに対して、

・2個以上の頂点を通る

・同じ頂点を2度以上通らない

・パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

の3条件をみたすようなパスを一つあげよという問題。

適当にflag[n]とかで訪れたかを確認して、頂点1から行けなくなるまでパス取ればいいんじゃね？と思って適当にパスを取る。→WA

問題を勘違いしていて、このような場合一番下の条件を満たさない。

→頂点1から限界までパスを取ったあと、flag[n]をそのままでもう一回頂点1からパスを取ってくっつけた。→AC

問題C Ants on a Circle

蟻本の蟻が動くやつの円状バージョンってことでいいよね（？）

蟻本読んでないから正しいかは知らないです。

長さLの円状にN匹の蟻がいてそれぞれ座標が小さい順に1,2....Nと名前をつける。どの蟻も1秒に1ずつ進み他の蟻とぶつかると反転して動き続ける。最初の位置と蟻の向きが与えられた時、T秒後の蟻の位置を名前順に答えよという問題。

反転せずにすり抜け合っても動きは変わらないので、名前順じゃなければ、蟻の位置は簡単に求まりそう。

位置をどうしようかという話。

・反転するだけなので、1,2,3...,nという蟻の順番は変わらなそう。

・最初1がバトンを持っていると考えて、ぶつかるたびにバトンを渡したと考えればバトンは1→2→3→... もしくは　1→n→n-1→...のどっちか。

1が左回りか右回りかで場合分け（しないほうが良かった気がする）。

バトンが何回受け渡されるかは、最初の位置情報からいけそうだったので計算。

バトンを持ってる奴の動きはひたすら一方向にグルグル回っていくだけなので、最終的なバトンの位置は容易に求まる。バトンを誰が持っているかを求めて、そこからどの位置が誰かが決められる。

頑張った結果、微妙に対応関係がずれる。最終的に同じ位置にいる奴らの区別が原因。直したら通った。

問題DもDPっぽいから頑張っていい感じのところまでいったと思ったら、途中で間違いに気づき終了。

順位 70位(!?)　パフォーマンス 2651 新レート2075(+94)

ついに黄色くなりました、やったぜ！