結果 ---(+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むりげ…