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

問題 風船がN個あり、それぞれ現在、高さH[i]にある。 各風船は秒速S[i]で上昇しており、1秒おきに1つずつ撃ち落とすことができる。 風船の高さを最小になるように撃ち落とした場合、風船が上がる最小の高さを返す。 N 1 考え方 高さを決め打ちし、二分探索…

問題 R*Cのマスに飴がN個置かれている。同じマスには2つ以上飴は存在しない。 あるマスに立った時、そのマスと同じ行と列にあるすべての飴を手に入れることができる。 獲得する飴がちょうどK個になるようなマスはいくつあるか。 1 K 考え方 行方向、列方向そ…

GCJ2015Round1A B問題に似ているかも？こちらもハマって時間を溶かした。 本番では数か所間違えててWA。 問題 N*Nマスの表があり、(i,j)の値はA[i]*B[j]である。 サイズNの配列A,Bが与えられるとき、表の中の数値を昇順で並べてK番目にくる数値を求める。N 1…

解いた問題と解けなかった問題書くのサボるのよくない。 oo oo -- 48pt 1689位 通過ならず。次で通過したい。 A. Mushroom Monster 問題 キノコが好きな人がいて、最初の状態と10秒おきのキノコの個数の情報が与えられる。 キノコは、適当に追加されることが…

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

だらだら参加してしまって非常によくない。けど、とりあえず通過。 oo oo o- o- 57pt 2369位 A. Standing Ovation 問題 立っている人がi人いたら自分たちも立つという人がSi人いる。 iは0〜(1+Smax)まであり、Siは0〜9まで与えられる。 このとき、自由にi人…

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

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

問題 H*Wのスライドパズルの状態が与えられる。 左上から 1,2,3,4,5 6,7,8,9,10 ... のように数字を埋めて、右下が0のようにするために必要な最小スライド数を答える。2 最小スライド回数は24回以下が保障される 考え方 両側bfs。 24回以下なので、ゴール状…

問題 整数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…

問題 n番目の正四面体数は、n*(n+1)*(n+2)/6に等しい。 Nが与えられたとき、そのNを複数の正四面体数の和で表現したい。(同じ正四面体数を何度も使ってよい) 組み合わせる正四面体数が最小になるようにNを表現したときの組み合わせ数を求めよ。 また、組み合…

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

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

問題 N頂点からなる、辺の重みが1の連結な木が与えられる。 M個のA,Bが与えられ、「頂点AとBから同じ距離に位置する頂点の個数」をそれぞれ返す。N M 考え方 任意の木では、個数の数え上げが難しいので、頂点1をルートとする根付き木にしておく。 考察すると…

問題 a〜zの26個のアルファベットの重みが与えられる。 ある文字列が与えられたとき、長さ1以上の部分文字列で「両端のアルファベットが同じ」かつ「両端を除いたアルファベットの重みの和が0」であるようなものがいくつあるか？ 10^5 文字列の長さ 考え方 …

問題 今、N人のプロとM人の初心者がいる。 3人でチームを作る際、(プロ、プロ、初心者)か(プロ、初心者、初心者)であるように作らなければならない。 何チーム作れるか？0 考え方 それぞれ(プロ、プロ、初心者)がAチーム、(プロ、初心者、初心者)がBチームで…

問題 n個の数字が与えられ、それからどこれか1つの数字を除いたn-1個の数字、さらに、それからどれか1つの数字を除いたn-2個の数字が与えられる。 それぞれ、なんの数字が抜かれたか？を返す。 考え方 n個の数字の合計値を求めておけば、n-1個の数字の合計値…

問題 いくつかのコマが配置されたチェス盤が与えられる。 各コマには重みが与えられており、各プレイヤーごとの重みの合計値が高いほうのプレイヤー名(White/Black)を返す。同点の場合はDrawを返す。 考え方 数えるだけ。 が、入力をよく見ると、knightの場…

問題 0〜9,?によって構成されるN文字の文字列が与えられる。 ニコニコ文字列を2525...5のように「25」が連続した文字列とすると、上記の文字列からニコニコ文字列を取り出す方法がX通り以上だったことがわかっている。 このとき、元の文字列として考えられる…

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

問題 無限に頂点がある根付きn分木が与えられる。 ある親頂点について、子頂点はn個あるが、それぞれ左からd[i]の重みになっている。 今、「根から頂点jまでの距離=根から頂点までの最短ルートの重みの和」とする。 距離xが与えられるので、距離がx以下であ…

問題 N台のロボットが1列に並べてあり、各ロボットはM種類の精密機械で構成されている。 各精密機械は何個か積まれており、ロボットiのj番目の精密機械はk個(a[i][j]=k)という情報が与えられる。 今、特殊な兵器によって、1回につき、すべてのロボットについ…

問題 a,b,cの3文字からなる、n個の文字列が与えられる。 次に、a,b,cの3文字からなる、m個の文字列が一つずつ与えられたとき、n個の文字列で以下の条件を満たす文字列がある場合YES、なければNOを返す。 ・同じ長さの文字列である ・ちょうど1つの文字が異な…

問題 K個のドーナツをN個の箱に詰めたい。箱は1つのドーナツをいれることができる。 箱のサイズが小さい箱があれば、大きい箱の中に入れる、ような入れ子にできるが、サイズの差分だけの緩衝剤を入れる必要がある。 必要な緩衝剤の合計の最小値を求める。 ま…

問題 N個の数字が与えられ、N-1個の数字の間には＋または-がはいり、その計算結果がN番目の数字になるような計算を考える。 前方から＋または-で計算して、負の数または20を超える途中計算になるような計算が許されない場合、何通りの計算方法があるか？を答…

問題 n段の階段を、各段で1〜3段のどれかを選んで上っていくことができる。 階段を上るパターンを考えるとき、1日10通りの方法で上ることができる場合、何年かかるか？ 考え方 dp[i]:=i段まで上ったときのパターン数 とすると、このパターン数はdp[i+1]とdp[…

http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL とりあえず、典型DPと呼ばれるであろう問題を一通り解く。 考えが違っていた部分をメモ。 Combinatorial A. Coin Changing Problem dp[i][j]と置くとき、i-1からi方向しか考えない場合が多かったけ…

問題 牛がN頭ならんでおり、各牛は1〜Kまでの番号が付けられている。 各牛の並びが与えられるので、先頭から適当に牛を選んでその番号を使って作ることができるの部分列をK+1進数の数字とみなした場合、作ることができない数字のケタ数を返す。N K 考え方 あ…

しばらくDPの問題を解きまくってDP脳になるために練習問題を解いていきたい。 @tatanaideyoさんに教えてもらった。一通り解いていきたい。 AOJ DP library http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL kyuridenamidaさんのまとめ http://d.hat…