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

裏紙

ほぼ競プロ、たまに日記

2016/5 Solved(1)

5/1

imulan.hatenablog.jp

5/2

(なにもしてない)

5/3

5/4

SRM 690 Div1に参加

Easyの1完。今回も時間はかかったがEasyで得点出来てよかった。Easyが毎回できていれば黄色にはなれるんじゃないだろうか(次回なりたい)。

貪欲に木を植えられる場所に植えていく。

パスが被らないようにできるだけ多くのパスを選ぶには、葉を全て選ぶのが最適であるので、葉の個数を数え上げれば良い(親→子への有向辺をつくれば、辺が1個も出てないところが葉になるのでわかりやすい)。

dp[現在地][010..が連続している個数][1つ手前が0か1か][現在のbeauty level]=beauty levelがcntに一致する文字列の数を保存しながら再帰していく(Submission)。

5/5

5/6

CF #350 Div2に参加

なんだかんだで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のヤバさを感じる...

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

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

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

5/16

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

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