AtCoder Beginner Contest 011

 久しぶりの全完。

結果

 401/401 97:42(2) 34位相当

 

 開始時刻 2017/07/26 14:57:00 提出履歴

A: 来月は何月? - AtCoder Beginner Contest 011 | AtCoder

 0:52(AC)

 0-originで生きてるから1-originに思考を切り替えるのに時間がかかる(?)。(N%12)+1でAC。

B: 名前の確認 - AtCoder Beginner Contest 011 | AtCoder

 6:44(AC)

 stringにtoLowerCaseとかないのかなーと思って調べてtransformなるものを見つけた。でもこんなことせずにcharでゴリ押した方が早かった気がする…。文字列はこれだから嫌い。

C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder

 27:54(AC)

 この問題にすごく似ていたので、直感を信じてDPで組むことにした。結果としてはやっぱりいい方針だったと思う。条件分岐してたら面倒臭すぎる。

 でも、貰うDPより配るDPの方が綺麗に書けるな、と解説を見て思った。DPを組む時はすぐに貰うDPを組む癖があるけど、一回立ち止まって考えた方がいいかも。

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder

 84:39(WA)85:44(WA)87:42(AC)

 出たな確率。でも今回はうまく解けた。

 まず目標地点にどうやっても辿り着けないパターンは全て除外する。具体的にはXかYがDで割り切れない時とか、割り切れた上でもX/D+Y/DとNの偶奇が一致しないとき(無駄な動きを相殺する上下移動、左右移動が出来なくなる)。

 横にK回(X<=K<=N-Y)動くと仮定すると、自然と上下左右に何回動かないと行けないかが決まる。KはXから初めて+2ずつ増やす(さっき言った相殺のため)。確率はそれぞれ独立なので、全ての総和が答え。各確率は(N回中K回横に動く確率)*(K回中R回右に動く確率)*(N-K回中U回上に動く確率)で求められる。

 WAは負数の剰余に関連してのWA。どうしたらいいんだろうとは思ったけど、よく考えたら軸に関して反転させても確率は変わらないので、X、Yを代入したあと絶対値を取るように修正してAC。

感想

 持ち越しの課題が増えなかったのが嬉しいです(切実)。