のときに がすぐ理解できなかったのでメモ。 手順 あるを使って と書ける。これを変形して ここで明らかにで、または よって

コードが書きたい気分だった。一番遅いstart+periodのlcmまでシミュレートすればよい。 (一番遅いstart時点でのsleep) > (一番遅いstart+全部のperiodのlcmの時点でのsleep)の場合 どんだけ開始時のSleepが大きくても周期ごとに減っていくのでそのうち起きる…

AOJ1179から1182までを解きました(先日のICPCの問題) 1179 Millennium やるだけ。 xxxx/yy/zzから1000/01/01までの日数を求める。 ただし1年は10ヶ月で、うるう年もどき(mod 3 == 0)だと全ての月が20日、 そうでない場合は20と19が交互。(1月は20日) 1000/01…

Vol.12がだんだんきつくなってきたのでここらでVol.01の残りを掃除でもしようかと。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145 ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=385224 方針 solve(a,b):=a番目の山…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382422 方針 典型的なDP dp[i][j] := i回振った後にjマス目にいる確率を計算していけばよい。n番のマスに到達した場合それ以上の移動はせず、 答えとしては を出力すればよい。

AOJ上でソースを公開できるようになったのでそのテストも兼ねてソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=376363与えられたN(1 2^15以下の平方数は181個しかないのでDPで dp[i][j][k] := i番目の平方数まででj個使った和がkになるような…

いくつか通しました 1100 1132 幾何。幾何問題はcomplexを使うと非常に楽です。 1104 実装ゲー 1144 DFS。 10回の移動までなので最大でも4^10*20(盤面の広さ)なので間に合う。 結構実装戸惑った。しょぼい。

問題 xy平面上の(i,0)に高さh_i(i=1,2,...,n)のn本のビルがあるとき、あるビルから見える他のビルの屋上の最大数を求めよ 方針 あるビルに注目したときそのビルから左右方向に別々にループを回すのはめんどいので ビルiからビルjの屋上が見える場合その逆も…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1109 問題文通り。与えられたzについて z^3-max{x^3 + y^3| x>0, y>0, x^3 + y^3 を計算する。 方針 xを決めて条件を満たす最大のyを二分探索で求めて計算する。 二分探索は割とすぐ思いつけ…

方針 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; と…

久々に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で間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…

問題 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した。基本的にはやるだけ。以下ソー…

問題 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通りの 解が考えられる。 これらの候補に対し入力されたすべてのチェッカーからの移動距離(マ…