問題 バラとユリが何本か入った箱が与えられる。箱iについて、バラの本数とユリの本数がわかる。 この箱をいくつか使って、R*Lのグリッドの各グリッドに花を植えるために使う。 ただし、各グリッドについて、隣接する4つのグリッドはそのグリッドに植えた花…

問題 文字列がいくつかと、文字列a,b,cが与えられる。 各文字列が以下の条件を1つ以上満たすとき、悪い文字列であるという。 ・接頭辞が文字列a ・接尾辞が文字列b ・接頭辞と接尾辞以外の部分文字列にcを含む いくつ悪い文字列があるか数える。 考え方 実際…

問題 チェスボードと、複数のナイトかポーンがある。 初期配置と最終配置が与えられる。 1手で1つのコマを1回動かせる。各コマの動きは以下。 ・ナイトは、ボードからはみ出ないように全方向の桂馬飛びで移動できる ・ポーンは、1マス進める。一番端まで移動…

問題 ぴったりXの距離だけジャンプできるカエルがいる。 数直線上を原点からスタートして、距離D以上になるまでジャンプを繰り返す。 間に、L[i]からR[i]までの幅の穴がいくつか空いている。(L[i],R[i]の端点は穴に落ちない) 穴に落ちないようにする場合、最…

問題 グリッドのマスに数字が書いてあり、一番小さい数字と一番大きい数字の差が1になるようにしたい。 1回の操作で、どれかのマスの数字に1足すか1減らすことができる。 最低何回の操作で実現できるか？ 考え方 全探索する。ある数値を決め打ちし、 ・それ…

問題 N本のブロックのタワーがあり、0からN-1の番号が振られており、それぞれの高さheightsが与えられる。 このタワーを横一列に並べる。 このとき、あるタワーが倒れても横のタワーが倒れないように、2つのタワー間の距離は、その2つのタワーの高いほうの高…

問題 要素が0または1のH*Wの配列が与えられる。 配列の周りを罫線で囲んだものを考える時、左上の部分から右下の部分まで最短距離で結んだ線を引き、その線の下側になるすべての要素の0と1を反転することができる。このとき、すべての要素を0にするために必…

問題 整数値の配列aが与えられる。 配列x[0..N-1]が 1=2*x[i] を満たす場合、convexである、という。 与えられた配列aに対し、次の操作ができる。 ・iを一つ選び、そのa[i]を1引く 配列がconvexになるまでにかかる最小の操作回数を求める。 考え方 要素が10^…

問題 毎晩、毛の色を変えられるオオカミがいる。 色はN色あって、便宜上0〜N-1の番号で扱う。 colorMapという2次元配列が与えられる。 もし色iから色jに変えることができればY、そうでなければNが書かれている。 色は、変化させられる最小の番号の色に変わる…

問題 1*1*1〜1*1*kのレゴブロックが無数にある。 土台が1*1*wのところに重ねていき、高さをhにしたい(土台は高さに含めない)。 条件として、ブロックを重ねるとき、重ねるブロックからはみ出ないようにする必要がある。 そのような重ね方の組み合わせは全部…

問題 ロボットがあり、「right X」「left X」「forward X」「backward X」の命令がいくつか与えられる。 rightとleftの時はXに角度、forwardとbackwardの時はXに距離が与えられる。backwardは向いている向きに対して(向きを変えずに)反対方向へ移動する。命…

問題 N個の1列に並んだセルからなる真っ白なボードがあり、これに色をつけたい。各セルの色は赤、青、緑の3色。 各セルの塗りたい色desiredColorが与えられ、R,G,Bならばその対応した色、*ならばどれでもよい、を表す。 色をつけるときはL個分の隣接セルをま…

問題 あなたはQBで、普通の少女を魔法少女にできる。 n人の普通の少女と、少女iが少女jを好き(非対称)、というリストが与えられる。 ある普通の少女iが魔法少女になったとき、その少女が好きな女性をプロテクト状態にでき、プロテクトされた少女の好きな少女…

問題 Xが非負の整数であるとき、以下の性質を持つ無限列をXのKleofas tailという。 数列の最初はX 偶数の数字の次の要素は、その数字の半分にしたもの 奇数の数字の次の要素は、その数字から1引いたもの 例えば、X=60の場合は、60,30,15,14,7,6,...となる。 …

問題 N人で弱いと思う人に投票しあう。 もし、投票数が一番多い人が1人ならばその人が決定し終了する。 もし、そのような人が複数人いる場合、それらの人だけについて投票しなおす。投票は、あらかじめ投票する人を決めている人が何人かいて、その人たちが先…

問題 数字が書かれたカードが与えられる。 カードのうち1枚を引いて、その数字と、その数字の前後のカードがもしあればそれらを取り除く、 というのを繰り返す。 このとき、より多くのカードを引けるようにした場合、何回引けるか。 考え方 連続している数字…

問題 2次元座標平面上に格子点がN個与えられる。 その中から4点選んで、長方形を作る。ただし、各辺は軸に平行でなければいけない。 このとき、長方形内部に点を含まないような長方形で最大の面積となるものの面積を返す。 考え方 N個の点から2点(x1,y1)と(x…

問題 N個の街をつなぐM個の道の情報が与えれる。道の情報として、移動元の街、移動先の街、かかる時間が与えられる。街番号0から街番号N-1まで最短時間で移動したい。ただし、ゴールするときの時間は4か7で割り切れるようにしたい。 最短の到達時間を返す。 …

問題 7 2 3 1 5 3 のような数字の三角形が与えられる。一番上からスタートし、その地点から真下か右下に移動することができる。 一番下の段まで移動したとき、それまでの経路上の数値の合計値の最大値はいくらか。 考え方 DP。 その地点までの経路の合計値の…

問題 家の見取り図が与えられる。 部屋、壁およびスタート地点、ゴール地点、計算機のおいてある地点の情報が与えられる。 壁へは移動できない。 スタートから計算機の部屋へ寄り、ゴール地点までにかかる単位時間を答える。 部屋間の移動は1単位時間ででき…

問題 文字列がN個与えられる。その中から2つ以上選んで、任意の順番でつなげたものの中で、辞書順最小になるものを答える。 考え方 「2つ以上」となっているが、辞書順最小となるものは常に「2つつなげたもの」になるので、2つ(AとB)選んで、A+BとB+Aを候補…

問題 2012年の日付が2つ与えられる。 日付が何日離れているか答える。 考え方 早いほうの日付から1日ずつ足していって、もう片方の日付になるまでカウントする。

問題 円形テーブルにN人座っている。ただし、隣り合わせたくない2人組というのがM組存在する。 適当に2人を選んで場所を入れ替える動作をK回繰り返したときに、隣り合わせたくない2人組が隣り合っていないような確率を求める。 考え方 シミュレーション。制…

問題 NxMの格子状の区画とスタート地点、ゴール地点、各区画の明るさが与えられる。 各隣り合う区画は1秒で移動できる。 区画の明るさはスタートした時刻からt秒立つと、「元の明るさ*0.99^t」になってしまう。 なるべく、スタートからゴールまでの経路中、…

問題 単語の後ろ方向からの辞書順にならべたさかさま辞書を作りたい。 複数の単語が与えられるので、そのさかさま辞書を返す。 考え方 単語を逆順に並び替えて、辞書順ソートし、単語を元に戻す。

問題 評価(A,B,C,D,F)を点数(4,3,2,1,0)に換算した平均値を求める。 考え方 やるだけ。全部足して評価の数で割る。

http://ijpc2012pr.contest.atcoder.jp/tasks/ijpc_ijpc

問題 正の整数の集合Sが与えられる。和が等しい異なる部分集合2つを見つけよ。無い場合は「Impossible」を返せただし、集合に同じ数字は2つ以上現れない。例えばS={1,2,3,4}ならば、{1,2}と{3}。 考え方 Small N=20なので、集合Sの要素をいれるかいれないか2…

問題 N人が審査員およびオーディエンスによって審査される。 各人は審査員からのポイントJ[i]が与えられる。 オーディエンスからのポイントは、その人への投票の割合Y[i](0〜100%)を審査員ポイントXの合計にかけたものX*Y[i]になる。 すなわち、その人のポイ…

問題 デカルト座標のxまたはyが整数のところをN匹の蟻が動いている。 各蟻はNWESの方向へ一定速度で動いている。 もし衝突した場合は互いに消滅してしまう。各蟻の初期位置と方向が与えられるとき、最終的に消滅せずに残っている蟻の数を返せ。 考え方 一定…