なんだかんだで2ヶ月ぶりのCodeforces参加。部分点制が実験的に導入されてた。ABCDの4完。ほとんどレートが変動しなかったし、やっぱりもう1問解ける必要があるな、というかだから今のレートが妥当なのだなという気持ちになる。もう1問解いて500位くらいに入れればいいなと思う。4問まではなかなかスムーズに解くことが出来たので良かったのではないか。

5/7

ABC 037に参加

全完、Dに関してはそこの位置を最終地点とする経路の組み合わせをDPしていく感じで解いた。最初に初期化をしておいて、順次再帰を呼び出すようにすれば全ての組み合わせが列挙でき、かつO(HW)で計算できるので間に合う。これがなかなかすんなり思いつけたので、ちょっと嬉しい。13位は自己最高。

5/8

GCJ 2016 Round 1Cに参加

A-sl,B-slを解いた。Bは最初small解法しか思いつけなくてとりあえずそっち通した後にしばらくしてlargeの方も思いついて実装した。Round2にギリギリすすめた。初参加だし、ここまで行ければ満足かな...

5/9

imulan.hatenablog.jp

5/10

5/11

5/12

imulan.hatenablog.jp

dp[n]:頂点nを始点とするときに、探索できる素数洞穴の個数の最大値,last[n]=dp[n]がその値を取るときに経路上にある最後の素数を保存しながら、座標の下の方から配るDPをしていく(submission)。

そこにたどり着けるのは左上か真上か右上しかないので、その3方向に配っていく。そのときに最後に得られる素数もどんどん上に渡しながら更新していけば良い。

再帰で書く場合には、その頂点から行くことの出来る最大3つの子のうちで最大値を取るものの最後に得られる素数を受け継いでいくことで更新していくことが出来る(submission)。

5/13

TCO 2016 Round 2Aに参加

Easyむずい回(?)．出したけど撃墜された．Round2のヤバさを感じる...

TDPC C - トーナメント

dp[n][k]=番号nの人がラウンドkを勝てる確率としてラウンド(k-1)との関係をみることで漸化式を立てる。kラウンド目での対戦相手の人数は各人にたいして $2^{k-1}$ 人だけいるので、その相手xごとに(番号nの人がラウンド(k-1)で勝つ確率)(番号xの人がラウンド(k-1)で勝つ確率)(nがxに勝つ確率)と足しこんで行けば良い(submission)。

TDPC D - サイコロ

Dの倍数となるということは、Dの全ての種類の素因数の個数に対して、Dの素因数の個数よりも積の素因数の個数が多くないといけない。そして、サイコロで出る目は素因数に2,3,5しかない。Dがそれ以外の素因数を持つ時点でサイコロの出目の積がDの倍数には成り得ない。Dが素因数を2,3,5しか持たないときにはその個数に対するdp(dp[2の個数][3の個数][5の個数])をすればよい(submission)。

5/14

ARC 053に参加

ABの2完。Cはもうちょっとじっくり考えてみるべきだった...

5/15

AOJ 1174 - Identically Colored Panels Connection

dfs(染める色,現在の回数,現在のフィールド状況)で通した。メモ化しなくても余裕だった。けど、メモ化したらもっとはやくなったしメモリも余裕だった。

5/16

AOJ 1347 - Shopping

戻るべき区間を貪欲に決定していく。

AOJ 1020 - Cleaning Robot

確率漸化式を立ててdpをループで回して求める。

裏紙

ほぼ競プロ、たまに日記

2016/5 Solved(1)

5/1

5/2

5/3

5/4

SRM 690 Div1に参加

5/5

5/6

CF #350 Div2に参加

5/7