4/16

ARC 051に参加

ABの2完、Cはほとんど方針合ってたけどちょっとずれて多分オーバーフローさせてたっぽい、多分Pythonで書けばいけてたのかなあ...

4/17

4/18

imulan.hatenablog.jp

4/19

ARC 038 B - マス目と駒

ゲーム木を考える。その座標に駒がある状態でターンが回ってきた時に勝てるかをDPで埋めていく。その状態から遷移できる状態に１つでも負けの状態があればその状態に持っていくことで相手の負けを決めることが出来るので、自分の勝ちが決まる。どこにいっても勝ちの遷移しかできなければその状態は負けになるsubmission。

4/20

4/21

TTPC2015 D - 文字列と素数

next_permutaionを使って全探索。

4/22

4/23

4/24

SRM 689 Div1に参加

Easyの1完。最初に投げた回答が間違っていることに45分あたりで気づき、resubmitした。80点くらいになってしまったので、Challengeしないとやばいなーという感じでresubmitしたことで落ちなくなったやつで落とせるやつを見つけたので、1つ成功した。

CODE FESTIVAL 2014あさ Hard A - eject

$i$ 回トレイを開閉した後にエアコンがONになっている確率を $P_i$ とすると、OFFになっている確率は $1-P_i$ になる。また、そこから $i+1$ への遷移を考えることで漸化式 $P_{i+1} = (1-p)P_i + p( 1-P_i )$ が立てられ、これより漸化式を解いて $P_i = \frac{1-(1-2p)^n }{2}$ がわかる。あとは、 $n$ 乗の部分を繰り返し二乗法によって計算してあげればよい。