方針 N本のボトルを運ぶときの最小の本数==Nの立っているビットの数 なので、ビットカウントをしてそれがKより少なければ運ぶことができる。これを1本ずつ足していって調べてみればよい。 足す本数は、多く見積もっても2^k ビットカウントにO(logn)掛かると…

問題 整数nが与えられる。 0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。 ただし、i行目の箱の数a_はa_i>a_j(i 方針 要は下に行くほど少なくなっていけばよい。 n-1行は0個か1個なので dp[0][0] = 1; dp[0][1] = 1; と…

結果 o--(+0/-0) 157.5pts 461st(Div.1)レートは 1221->1256(+35) 何とか年越しを青で迎えることができました。 250 うなぎ切るよ！ 10nな長さのうなぎはn-1回切ると長さ10のうなぎがn本取れるのでお得、なので 長さが10の倍数のものを小さい順に、そうでな…

結果 oo- (+0/-0) 478.37pts 105th(Div.2) 1190->1221(+31)Div1復帰しました。 250 MagicStonesStore ゴールドバッハ予想を使うとちょっと楽になるらしい。 sieveしてから全探索、引数nに対して2*n個というのを初め忘れていて提出が遅れた。Passed System Te…

久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 方針 nが割と小さいのでDFSで間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…

結果 ooxo- 2576pts, 447th(Div2)レートは 1583->1547(-36) 内容 A,Bはまぁやるだけ C 数列{a_n}のいずれか1つを任意の数に変更して(変更しなければならない) ソートしたときのk番目の値としてとりうる値の最小値を全てのkについて求めよ。基本的には初めに…

[使い方] -単一始点の最短経路とその経路長 -重みが負のedgeがあると使えないvoid dijkstra(int s,vector &cost, vector &prev, vector > edges); s:始点ノードの番号(0-index) cost[i]:sからi-thノードまでの距離を入れるvectorを渡す。 prev[i]:sからの最…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155 方針 1 すべてのビル間の距離を計算して50以下ならedgeを張ってdijkstraすればよい。前々からdijkstraは書いておきたいなと思いつつも 下手なライブラリ書いて使っていくことにためらい…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203 方針 配るDP。貰うDPでも書けなくはないと思う。 下から二段目にジャンプ台がある場合に注意。以下ソースコード #include <iostream> #include <cstring> #include <algorithm> using namespace std; int dw[3] = {-1,</algorithm></cstring></iostream>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221 方針 シミュレートする。 (Fizz || Buzz || FizzBuzz)でないときの処理を自前tointに任せていると文字列のときにうまくいかないのに気づかず数回WAした。基本的にはやるだけ。以下ソー…

結果 ---(+0/-0) 0pts 1251->1191次回はDiv.2。 300 外側から切っていくということは残せるのは長方形なので、 任意の部分長方形についてその内側をカウントすればいいのだが、そこからそれを残すために移動する回数を求める方法を考えて迷走した。 任意の部…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181 方針 本棚の幅で二分探索。 あとはn冊の本を詰めるシミュレートをして、lb/ubを更新していけばよい。 判定は必要な段数のみでなく、本の厚みの最大値 計算量はO(n*log(本棚の最大値))だ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191 方針 i回目に選ぶものを決めるために影響するのはi-1回目に何を選んだかのみで、それまでにどういう選び方をしたかは関係ないので dp[i][j] := i回目にjを選んだ場合の最大の長さ とし…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 方針 左から円を並べていくと考えると、右端の円の大きさと追加する円の大きさによって増加する長さが変わることが解る。n dp[state][back] := state使った右端がbackであるものの長さ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082 元ネタが解りません… 方針 配る系のDP。 5種類音のある子音列はループするまでは あ->ああ->あああ あい ->い ->いあ ->う というように、最後にa音を1文字つけるor最後の文字を1つ進め…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079 方針 同一のマスに対するクエリは最後のものが有効であることに着目して クエリを逆順に見ていけばよい。逆順に見て既にクエリを処理したことがあればそのクエリは無視、 そうでなけれ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1078 佐天さん。 方針 加法標準形のSATなので1clauseでもsatisfiableなら全体としてsatisfiableである。 文字処理が若干めんどくさい。 mapでどの文字リテラルがtrueかfalseのどちらのassign…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1077 方針 問題は6種類あるように見えて実は3種類しかない。 Math or DP -> MD Greedy or Graph -> GG Geometry or Other -> GO とすると、 MD,GG,GOのコンテストを3回開くのはそれぞれ3問の…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076 [1,n]の整数のうちa_k(1 方針 包除原理。m 計算するものは選んだ数の公倍数の和とその個数。 公倍数の個数は n / lcm, 公倍数の和はlcm * (n / lcm) * ((n/lcm)+1)。nが大きいのでlong …

問題 無限に広がるマス上にn個のチェッカーがあり、そのうちi個(1 方針 解となるx,y座標は入力として与えられるx,y座標の中にあるはずなので、それぞれ50*50=2500通りの 解が考えられる。 これらの候補に対し入力されたすべてのチェッカーからの移動距離(マ…

結果 ooo-- 2302pts 269th(Div.2) 1622->1583(-39) A accumulateしてその偶奇で場合分けしてカウントするだけ B 問題文が読みにくい。 1人と結んでる奴を排除していき、何stepで終わるか。 隣接行列と結ばれている回数の配列を作って、 結ばれている回数が1…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056 方針 DP。誤差制限が緩いので dp[n][k] := n回目にゲットできる確率が2^-kである確率 として dp[i+1][0] += dp[i][k] * (1 - pow(0.5,k)) //取れなかったら次の確率は1 dp[i+1][k+1] …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020 方針 dp[second][pos]で i+1秒後に次の移動先next_posに移動できるなら dp[i+1][next_pos] += dp[i][pos] * 0.25; そうでなければ dp[i+1][pos] += dp[i][pos] * 0.25; とすればよい…

x-- (+0/-0) 0pts 467th Ratingは1371->1321 (-50) 250 初め upperBound 等差数列は計算で、等比数列の方は計算して等差数列とかぶってれば増やさない、 という方針でやったものの、多くの人と同じく upperBound を忘れててChallenge Suceeded. 500 DPむりげ…

落ちたくない一心で迎えたDiv1復帰後1回目のSRMox- (+0/-0) 234.09pts 197th(Div.1)Ratingは1276->1371(+95) 安全圏まで上がりました。 250 openした瞬間一瞬Grundy数とかそういう方向かと思ったけど問題を読む。 連続するA,Bは1つとしても同じなのでsample…

こどふぉであったやつ。oooooo---- 307th 1555->1595(+40)初めの方はやるだけゲーだったように思える ICPC形式は初で、初めFileIOであることに気づかなかった。A.若干問題文読みにくいけどやるだけ。B.やるだけC.結局最後までやるので並び替えは考慮しなくて…

予選はC-small/largeを通して通過しました。決勝は 15pts 49:31 204th…あああもう少し(4分ぐらい)でTシャツもらえたのになぁ… B-smallでsubmit debugするんじゃなかった…A-small/largeを通しました。 隣り合う2本の積の和を最大化すれば良いので、 長いもの…

oo-(+2/-0) 826.39pts 20th(Div2) 1151->1276(+125)祝！Div1昇格！ 半年かかりました…(8,9月はインターンのためあまり参加してませんでしたが)250i番目(0 始め0 直した。 同じミスしてる人を2人Challengeで落とした。500某社のインターンWebテストでありまし…

1ヶ月ぶりぐらいのSRMoo-(+0/-0) 598.87 48th(Div2) 1047->1151(+104)大幅アップ。250 降順ソート→自分の場所を探して部屋数で割るだけ。 初め(点数,index)のpairを作ってsortとかしようとしてたけど 必要ないことに少しして気づいた。500 明らかにLuckはHar…