MaximumCup2018

MaximumCup2018に参加しました！
旧版:
maximum-cup-2018.contest.atcoder.jp
beta:
https://beta.atcoder.jp/contests/maximum-cup-2018/beta.atcoder.jp

解けた問題だけ解説をしていきますー。

要項

Maximum-Cup 2018
unrated
4/7(土) 14:00 ～ 17:30 (210分)
100-100-100-100-100-100-100-100 (8問)
ペナルティ: 5分

方針

今回は全ての配点が等しいので、とにかく問題を読んで簡単な順に解く方が良さそうです。
ただ、A-Dが難易度順と書かれているのでA問題から挑む点は変えません。
また、この日はABC093/ARC094も開催されるため、余力は残しておく必要があります。

A - フィギュアスケート界の貴公子埼大選手

ぬいぐるみを取れる条件を考えます。
あるt[i]に対し、t[i]+10秒後にまだ選手がぬいぐるみの場所d[i]に辿り着いていなければm[i]個ぬいぐるみを取れます。
選手は1m/sで移動しているので、つまりt[i]+10≦d[i]ならぬいぐるみをm[i]個取れるわけですね。
後はこれをそれぞれのiに対して見れば、O(N)で個数が求まります。
簡単ですね

B - 駆け抜けろ！埼大山車部！！

まず、やけに与えられる値が小さいことに着目すると、総当たりが試せるのでは……と考えます。
だけど総当たりをやるにしても実装方法は？O(abhw)とかなら解けるけど……と考えたところで、dp[a][b][h][w]が使えないか考えられることに気付きますね。
ここで、dp[a][b][h][w]は左にa回、右にb回曲がった時に地点(h,w)に止まれるか否かを持つものとします。
そうすると、dp[a][b][h][w]はdp[a-1][b]～とdp[a][b-1]～が与えられていれば求めることができそうだと分かります。
後は、実際に1個前の曲がったデータと直進を組み合わせてdp[a][b][h][w]を求められるので、本当にO(abhw)で求められることが分かりました。

C - 嘘つきな天使たち

まず、天使と悪魔の二種類で、しかもそれぞれ自分でない種族を指さす、といったところでグラフ問題、しかも二部グラフ問題であることが分かります。
次に、実際に幾つか小さな例を試してみます。
すると、同じ対象を指ささないという制約条件から、全ての辺が枝分かれしない閉路であることが分かります。
この時、閉路の頂点数が奇数なら、1,2,…2n-2,2n-1,1……と繋がり、奇数番目を悪魔と定義しても天使と定義しても最後の2n-1→1で矛盾が生じるので、-1を出力します。
そうでない場合、つまり閉路の頂点数が偶数なら、半分が天使で半分が悪魔です。
よって、-1を出力していないならN/2が答えとなります。O(N)ですね。

D - Many Go Round

まず、幾つかのa[i]の和がL,L+M,L+2M……のどれかにならなければ辿り着けないことから、部分和問題ではないかと考えることができます。
また、休憩所は循環しているのでmodを取れそうだということ、和のmodはmodの和であることを利用すると毎回modを取ることでO(NM)の部分和問題に帰着できそうです。
ですが、そのままだと制約条件であるX週以内という条件が分かりません。
そこで、周回回数も覚えられないか考えます。
例えば同じ地点に5周と3周で行ける方法があった場合、どう考えても3周で行ける時に条件を満たすかだけ考えれば良いことが分かります。
そこから、最低何週で回れば良いか覚えれば良いのでは……？という発想が生まれますね。
実際、部分和は可能/不可能を示すbool型のdpで回せますが、代わりに最低周回回数を示すint型のdpを使って部分和問題を解けることが分かります。
なお、modの関係で通常の部分和のソースコードをそのまま転用するとバグるのでそこは微調整してください。O(NM)で解けます。

結果

ooooxxxx 4完(400点) 223:55(5WA)
74位

感想

B問題の方針ミス及び移動方向のミスで無限にバグらせたのが痛手で、4完という結果に終わりました……。
明らかに簡単なF問題(どう見てもdp)など実装したかったのですが、終わったものは仕方ありません。
速解きの大事さを実感しました。