読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

2016/4 Solved(2)

4/16

GCJ Round1Aに参加

Aしか解けなかった...Round2への参加権は1Bと1Cにかける...

ARC 051に参加

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

4/17

4/18

imulan.hatenablog.jp

4/19

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

4/20

4/21

next_permutaionを使って全探索。

4/22

4/23

4/24

SRM 689 Div1に参加

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

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乗の部分を繰り返し二乗法によって計算してあげればよい。

JAG 2016 模擬国内に参加

ABDの3完。3人で同時に同じ場所でやって、とりあえずチームとして4問解ければいいねみたいな感じだったので、その目標は達成できたのでよかった...Cは復習しとこう。

4/25

4/26

4/27

木の直径を求める過程で、任意の点から最も離れている点は直径をなす端点のどちらかと一致するということを利用する問題。これは確かに証明の仮定で使われていて、なるほど...となった。

4/28

4/29

4/30

GCJ2016 Round 1Bに参加

A-sl,B-s,C-sで1191位。やっぱ2完しないと厳しい...Bは桁DP、Cは二部グラフについてもうちょっと理解したい。