解答に必要なことを一つも考えつけてなかったorz 最適分割の部分の理解が怪しいが、理解したと思う範囲でまとめておく。 問題 体積Sのスライムがある。 1回の操作で、今あるスライムの塊を一つ選んで、2つに分解することができる。 このとき、体積Aのスライ…

問題 バス停から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…

半分以上が赤で、日本人も激強の3人がいる圧倒的威圧感の部屋で、がんばって解いたのにunratedでツラい。ratedになった。 問題 要素がN個の配列mが与えられる。 ここで、f(x)=(((x mod m[0]) mod m[1]) ... mod m[N-1])とするとき、f(1)+...+f(R)の値を求め…

問題 整数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は素数)が成り立つ(中国…

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

参加人数が少なくて、正の点数を取れば通過という・・・ o--でとりあえず通過。 250. Similars 問題 整数a,b(a!=b)について、その類似度S(a,b)は、どちらの整数にも出現する数字0〜9の種類数の合計、と定義される。S(112,1234)は1と2がどちらにもでているの…

問題 N個の頂点があり、有向辺がN本各頂点からでている。(多重辺や自己ループもありえる。) このとき、トークンを0〜N枚から好きな枚数を選んで、N個の頂点上に置く。ただし、同じ頂点には2個以上置けない。 今、トークンをそれぞれ同時にK回有向辺にそって…

さぼってるからできるようにならない。 問題 N*Nのセルが与えられる。 各セルにはBまたはWが書かれている。 各セルがすべてWの状態から初めて、K*Kの正方形の形でBまたはWで塗りつぶすことを繰り返し、与えられたセルの状態にすることができるか、できないか…

問題 整数Nが与えられる。 1〜Nまでを並び替えて得られる任意の順列pについて、i回目の数値をf(i)とすると、 ・f(1)=p[1] ・f(m)=p[f(m-1)] (m>=2) で定義される操作をx回行った値が1になるようしたい(すなわちf(x)=1)。 このようなxのうち、最小となるxをmo…

問題 無限に大きなマスのボードが与えられる。 M匹のきつねがいるマスの座標が与えられる。 集まるとは、すべてのきつねがいるマスが隣接しているような状態を指す。 このM匹が集まりたいとき、全員の移動距離の最小値を答える。M -10^9 考え方 きつねのx座…

問題 W*Hマスのボードが与えられる。 各マスは、空か、スタート位置か、壁か、の三通りが与えられている。 今、ロボットがスタート地点から上下左右の組み合わせのコマンドによって動くが、以下のような挙動をする。 ・コマンドに従い動いて、動く先が空マス…

問題 整数N,Kが与えられる。 次の条件を満たす文字列が作れる場合、そのような文字列の一つを返す。なければ空文字を返す。 ・文字長はN ・各文字はAまたはBのどちらか ・i 考え方 memo[i][j][k]:=文字長iで、Bをj個含み、(i,j)のペア数がk個になっている文…

問題 1〜Nの番号が付けられた建物を直線状に順番に並べて建てたい。 ただし、以下の条件が与えられる。 ・1の建物の高さは0 ・隣り合う建物の高さの差は高々1となるようにしたい。 ・x[i]の建物の高さがt[i]以下 このとき、建物の高さの最大値を求める。 N x…

問題 2次元グリッドの原点にいて、グリッドに沿って動ける。 毎秒、その場にとどまるか、上下左右に1単位だけ動けるが、いくつかの格子点が通行禁止になっている。 k秒間で、x座標が最大となる点でのx座標の値を求める。通行禁止の格子点数 -10^3 1 考え方 …

問題 n個の整数numbersが与えられる。 各数字を1回につき、1ずつ増やしたり減らしたりできる。 少なくともk個の連続した整数がある状態を作るための最小回数を求める。 -10^7 n k 考え方 与えられた数字から、ある整数集合z,z+1,z+2,...を作ることを考える。…

問題 兵士が(x1[i],y1[i])にいる。 塔が(xt[i],yt[i])に配置されており、塔を起動すると、その塔を中心にすべての兵士が点対称に移動する。塔は何度でもどの順番でも起動することができる。 すべての兵士を(x2[i],y2[i])に配置することができるか？ -10^6 塔…

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

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

0pt Rate: 1243->12631年半ぶりの参加らしい。が、0完でつらい。 250. JanuszTheBusinessman 解けなかった。 出会える人のグラフを作って、そのグラフの中で頂点集合を選んで、その頂点と隣接頂点がグラフすべての頂点をカバーしているような最小の頂点集合…

マラソンマッチに参加した。

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

問題 上流からうなぎが流れてくる。 うなぎiは、長さがl[i]で、最初に-t[i]にいて、原点方向へ向かって流れてくる。 すべてのうなぎは1単位時間に1だけ動く。 ある時刻で、原点に来たすべてのうなぎを捕まえることができるが、2回までしかその行為を行えない…

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

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

問題 テキストエディターを操作している。 結果表示画面、テキストバッファ画面、アンドゥ履歴画面から構成される。 今、結果表示画面に表示したいテキストが与えられる。 1行単位で処理していくとき、テキストバッファに入力し、エンターを押すことで結果表…

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