square869120Contest #5
square869120Contest #5に参加しました！
square869120Contest #5 旧版:
s8pc-5.contest.atcoder.jp
square869120Contest #5 beta:
https://beta.atcoder.jp/contests/s8pc-5/beta.atcoder.jp
形式が特殊なので、部分点込で説明をしていきますー
要項
square869120Contest #5
unrated
4/15(土) 20:00 ～ 24:00 (240分)
200-300-500-600-800-1000-1200-1400-1500 (9問)
ペナルティ: なし
方針
部分点稼ぎが最優先
A - Sushi 2
任意のiに対し、寿司i-1までの食べ終わった時間が分かっていれば寿司iを食べ終わる時間が分かるので1番目から順に求めていくことができます。
後は、今寿司i-1を食べ終わった時間をtとすると、t≦+kT(kは非負整数)を満たす最小の
+kTを次々tに突っ込んでいけばおｋ
B - Emblem
まず、最も小さい円の半径を最大化する時、その円は必ず他の円に接しています。
どの円にも接していないならまだ半径を大きくする余地があるからです。
ということで、まず任意の2円を選びましょう。ただし片方は必ず半径が定義されていない円にしてください。
片方だけが半径の不明な円の時、その円は明らかにもう片方に接するまで大きくするべきです。
また、両方が半径の不明な円の時、両方が接するように、つまり円同士の距離の半分まで大きくするべきです。
後は、この半径を見ていって、最小の半径に合わせれば良いですね。
C - Two Parentheses
結構難しいです。これを一発で思いつくのは無理かもしれません……。
まず、部分点の狙い方を考えましょう。
部分点の場合、文字列の長さが短いのでA,Bに対し実際に全通り生成して存在確認をするのが良いでしょう。実装ミスをしないようにね！
次に、完答を考えます。
先に、Sは十分に長い文字列であるとします。
まず、Aの文字列は普通の()の関係なので、こちらで考えてみましょう。
この時、まずAの最初の文字列は確実に'('です。
次に、2番目の文字列が')'だとすると3番目は必ず'('でなくてはいけませんが、2番目の文字列が'('ならば3番目は')'でも'('でも大丈夫です。
つまり、Aはなるべく'('の文字列を渡してあげたいですね。
そこで、最初の状態を0点、'('を+1点、')'を-1点とします。階層、というかネストの深さを点数にする感じですね。
その時、Aの点数は負数にならないようにしなくてはならず、しかも最後は0点で終わることが分かります。
同様にBは'('が-1点、')'が1点になります。
後は、先頭からSを見ていき、最後が0点になる可能性がある中でAとBの点数を常に最大化するように()を振り分けていくと解けます。
まぁ難易度は高い方ですね……。
D - Battle with E869120!
まず、(H,W)を取れば勝ちであることから、(H-1,W)及び(H,W-1)を取ると負けることも分かります。
ただ、それ以外のマスに駒を置いても幾らでも勝負が引き延ばせる気がします。本当にそうでしょうか？
実際に考えてみると、駒は各手番ごとに1個ずつ場に増えるので、いつかは置く場所が(H-1,W)か(H,W-1)しかなくなる状態が来ます。
マスの大きさが3マス以上の時、最初のマス、勝ちマスとその隣のマスを除いた全てのマスの数をNとします。
この時、Nが奇数ならば先手が丁度Nを埋めきるので後手は隣マスに置き、先手の勝ちになります。
逆にNが偶数ならば後手の勝ちになります。
つまり、自分はまずNの偶奇で先手後手を決め、後は(H,W)の隣に駒を置かないように駒を置きながら敵の自滅を待てばいい訳ですね。
なお、マスの大きさが2マスの時は例外処理としてとっとと(H,W)に駒を置いてください。
結果
oooo---x- 4完+4部分点(1825点) 239:22(3WA)
42位
