div2Bのレベルなの・・・？ 問題 n個の要素からなる数列aと整数mが与えられる。 空でない部分列の和がmで割り切れるような部分列があるかチェックし、あるならYES、ないならNOを返す。1 2 0 考え方 各a_iはmod mを取っておいても問題ない。なので、問題は「0…

問題 バス停からn台のバスが確率的に選ばれて1台だけ出発し、そのバスが戻ってくるまで他のバスは出発できない。 バスiは、戻ってくるまでtime[i]時間だけかかる。また、バスiはprob[i]/100の確率で選ばれる。 バス停に時刻sで訪れた時にバスの出発までに待…

英語の読解力が低い・・・ 問題 N人でマフィアというゲームを行う。 各ターン、N人全員が「弱いと思われる候補者」に投票し、投票数が最大の人が1人ならばその人が負ける。 投票数が最大の人が複数人いる場合、その人たちを「弱いと思われる候補者」の対象と…

むずい 問題 n*mのセルに0〜9の数字が書かれている。 あるセル(i,j)を選んだ時、p個の(i+x[k],j+y[k])に書かれている数字をすべて抽出し、その合計を得られる。(範囲外は0を抽出) 今、ある2つの異なるセルを選び、同じセルから1回のみ抽出できる場合、合計値…

問題 N人の友達をパーティーに招待する。 しかし、友だちiは友だちA[i]が嫌いなので、もし先にパーティーに招待されていたら来ない。 (嫌いな人がいない場合はA[i]=iとなっている) 呼べる友達が最大になるような順番で友達を招待したら、何人の友達を呼ぶこ…

問題 整数n,k,mが与えられる。 Σ_{i=1}^n {i^(2^k-1)}を求めよ。 1 1 2 考え方 i^(2^k-1)を考える。 k=400まであるので、愚直な方法では桁あふれしてしまう。 2^k-1というのは、ビットレベルで考えると2^kはk+1ビット目だけ立っていて、2^k-1は1ビット目〜k…

問題 N個の茶碗が並んでおり、茶碗iには豆がA[i]個と、整数C[i]が書かれている。 ただし、C[0]は書かれておらず、A[0]=0。2人のプレイヤーが豆を一つ選んで、その豆が入っている茶碗iから、茶碗(i-1)〜(i-C[i])のどれかに移す、ということを繰り返す。茶碗0…

問題 猿がK個のキー(同じ文字が存在するかもしれない)をS回押す。同じキーを何回も押すかもしれない。 押した順番に文字を並べた長さSの文字列ができあがるが、この中に、長さLの文字列Tが含まれる個数だけバナナを上げることにしている。 バナナは必要最低…

問題 整数a,b,cが与えられたとき、(a*x^2+b*x+c) mod 10^9 = 0となる整数xを返す。 ただし、0 0 考え方 法Mが合成数の場合、「f(x)=n mod M」は、Mを素因数分解した場合「f(x)=n mod p^a」「f(x)=n mod q^b」(M=(p^a)*(q^b)*..., p,qは素数)が成り立つ(中国…

問題 D種類の異なる金額を表すコインがある。 各種、C枚までしか使うことができない。 1〜Vまでの金額をすべて払えるようにしたい。 あと最低何種類追加すればすべて払えるようにできるか？ T Small C=1, 1 Large 1 考え方 全探索(small) 与えられたD種コイ…

問題 敵機がN機いる。 各敵機はHP[i]で、1ターンの攻撃で最大3機までに対し、以下のような攻撃を行える。 ・最初のターゲットには9ダメージを与える ・次のターゲットには6ダメージを与える ・最後のターゲットには1ダメージを与える HP[i]が0以下になった敵…

http://d.hatena.ne.jp/phyllo_algo/20150215/1423985061Codeforces 514のD問題をかなり微妙な解法で通ってしまっていたけど、テストケースが35個ぐらいでそんなに悪意のあるケースがないためたまたま通ってしまっているようにも思われる。 http://kmjp.hate…

問題 (0,0)から(x,y)へ移動したい。 ただし、i回目の移動距離はlen[i]でなければならない。 (i回目の移動で整数の座標に移動する必要はない。) ちょうどn回分の移動距離が与えられるとき、n回ちょうどで(x,y)にたどり着くことができるか？ 考え方 移動する座…

問題 ホテルにN人泊りに来る。 i番目の人は、arr[i]日に到着し、dep[i]日に出発する。 ある人にプロモーション活動をすると、その人のレビューはGOOD判定になる。 さらに、プロモーション活動した人が滞在中にホテルに滞在した人(到着日、出発日を含む)もGOO…

問題 高さの違うN個の積み木が並べてある。 隣り合う2つを交換する操作を何回か繰り返して、h_1 h_i+1 > ... > h_Nとなるようにしたい。 そのようにする最小交換回数を返す。N 積み木の高さ 考え方 高さの小さい積み木から左右のどちらかにその積み木より高…

問題 各頂点が整数点の多角形と線分Lが与えられる。 多角形を線分が分断し複数の多角形に分割するとき、分割後の多角形の数を返す。 線分は多角形をちゃんと分割するように与えられる。 考え方 よく考えると(←)、「線分によって分割される切断面の数＋1」が…

問題 n頂点の有向グラフが与えられ、各頂点にはアルファベット1文字が書かれている。 任意頂点から進んで、アルファベットを順番に回収して長さkの文字列を作る。 頂点にたどり着いたとき、アルファベットを回収してもしなくてもよい。 このとき、可能な辞書…

問題 無向木が与えられる。 クエリとして、頂点a,bが与えられるとき、aとbに辺を追加したら閉路ができる。このとき、閉路を形成する辺の数を返す。V Q 考え方 Qが10^5まであるので、O(n)な解法だと間に合わない。 頂点aから頂点bまでの距離がわかっていれば…

問題 2人が2つの「石が積まれた山」から交互に好きな方を選んで取っていく。 石には数字が書かれており、取った石の数値の合計が最終得点となる。 両者が最善を尽くしたとき、先手の得られる最終得点を答える。 考え方 ゲーム木の探索(先読み)。 ゲームの状…

問題 プログラミングコンテストの部屋割りをする。 N人の登録があるとする。 Nが20で割り切れるなら、部屋数はN/20。割り切れないならN/20+1(/は、整数割り算を表す)。 レートについて降順にならべ、R人ずつ、ランダムに部屋がかぶらないように部屋を割り当…

問題 店がN個あり、0からインデクスがふってある。 0〜M-1の店に興味があり、そこで商品を買いたい(1度だけ購入することができる)。 興味のあるお店については、開店時間、閉店時間、買い物にかかる時間が与えられる。 また、いくつかの店間には道があり、そ…

問題 n個の非負の整数a1,a2,...,anが与えられる。 これを2^a1,2^a2,...と書き直して総和を求める。 これに2^b(b>=0)形式のものをいくつか加えて、その総和が2^{v}-1(vは任意)になるようにしたい。 いくつ加えればよいか。 1 0 考え方 各ビットで考えられる。…

問題 n個まで連分数展開されたa0+1/(a1+1/...)の配列aと、分数p/qが与えられる。 この連分数展開されたものと分数p/qが等しいかどうかを返す。1 1 考え方 多倍長があれば、それを使って連分数をpp/qq形式に直して、pp*q == qq*pかどうかを判定。 または、p/q…

問題 非負で100以下の異なる整数がいくつか与えられる。 このとき、「任意のペアが、それらの各桁について少なくとも0を含む」ようにサブセットを作る。 2つの整数を同時に、1の位、10の位、100の位で見て、どちらかが0になるようにする。サブセットは満たす…

問題 2つの文字列X,Yを考えたとき、前方からどちらかを選んぶことを続けてマージした文字列Sを考える。 ここで、YはXを並び替えたものとすると、Sが与えられたとき、Xとしてありうる文字列の辞書順最小を答える。 考え方 一文字ずつ残りが可能かどうかチェッ…

問題 赤玉がr個、緑玉がg個、青玉がb個あり、以下のルールを上から順に繰り返す。 ・赤玉が残っていれば、赤玉を1つ取り除く ・緑玉が残っていれば、緑玉を1つ取り除く ・青玉が残っていれば、青玉を1つ取り除くしかし、合計数r+g+b=n個だったこととk回目に…

問題 w*hのチェスボード上をチェスのナイトが動く。 ナイトツアーとは、任意の場所からスタートし、スタート地点に戻ってくる経路のことを言う。 ここで、同じ場所は何度も通ってよい。 ナイトサーキットのサイズとは、1度でも訪れたチェスのマスのuniq数を…

問題 (0,0)から(X,Y)まで移動する。 各ターンで、上下左右に動けるが、iターン目にはiだけ移動する。移動方法をNSEWを並べた文字列で返す。 考え方 (0,0)から(X,Y)までtターンで移動できるかどうかを考える。 移動するための条件として、 1+2+...+t >= abs(X…

問題 アルファベットの文字列Sと整数nが与えられる。 長さLは、0 考え方 dp的に考える。文字列の0〜iまでの、求めたい個数をdp[i]とする。この値を求めたい。 dp[i-1]がすでに計算されているとして、今考えなければいけない文字列は、 部分文字列0〜i、1〜i…

問題 白黒の円を交互に描きたい。 同心円で、半径rの白い円の外に半径1の黒い丸を描き、その外に半径1の白い丸、その外側に半径1の黒い丸、のように描いていく。 白い円は今回描く必要はなく、黒い丸を描いていきたい。 今、tミリリットルの墨があり、1ミリ…