探索
問題 日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_05) 変数がn, 節の数がm以下の乗法標準形の論理式が与えられる。 (よくある2-SATの(x1 or x2) and (~x3 or x4) and ...みたいな形という意味) この式に対して変数の割り当…
問題 長さがnの数列 1 2 3 4 ... n-1 nがある。 この数列に対して3回以下、以下のような操作を行った。 l, rを選びaの区間[l, r]の順番を反転させる。 結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。 制約条件 n≦1000
問題 4x4のグリッド上に風船がおかれている。 風船には1〜4の数字がついている。 風船をクリックすると、風船の数字が1増える。 数字が5以上になった風船は、破裂して、上下左右の4方向に水滴が飛び散る。 割れた次の秒から、水滴は1秒に1マス進む。 水滴…
問題 hxwのグリッドで表される部屋がある。 Sのマスから下向きにレーザーが出る。 このレーザーを、部屋の適切なマスに鏡を置くことでGのマスに誘導したい。 鏡は'.'のマスにのみ置くことができる。 レーザーは'#'のマスは通ることができないが、Sのマスを通…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0132) 制約条件 パズルの幅, 高さ≦20 ピースの個数≦10 各ピースの幅, 高さ≦20
問題 n個のまんじゅうがあり、それぞれの重さは1〜9の整数である。 重さがちょうど10になるようにまんじゅうを選びたい。 重さがちょうど10のまんじゅうのグループは最大でいくつできるか、求めよ。 制約条件 n≦100
問題 h x wのグリッドのそれぞれがR, G, Bのいずれかの色で塗られている。 (0, 0)のマスと、そこから上下左右に連続している同じ色のマス全てを、 R, G, Bののうち好きな色ひとつに変えるという操作が出来る。 グリッドの全てのマスを同じ色に変えるために必…
問題 日本語なので本文参照。 制約条件 h, w≦12
問題 最初A個の0とB個の1が並んでいる。 この中から、異なるちょうどK個の数字を自由に選び、0と1を反転させる操作を行うことができる。 最短でこの操作を何回行えば全ての数字を1にすることが出来るか、求めよ。 操作をどのように行っても1にすることができ…
問題 8-パズルの初期盤面が与えられる。 これが解けるならその手順を、そうでないならunsolvableを出力せよ。
問題 w x hのグリッドであらわされる部屋がある。 それぞれのマスは金塊が落ちているか、壁か、何もない床か、落とし穴のいずれかである。忍者がスタートのマスからスタートして、金塊を回収する。 回収できる最大の金塊の数および、そのときの移動量の最小…
問題 ある素数k0を次のように分解する。 数の(要素の重複を許す)集合をCとする。 rを決める。 Cにrを入れる。 k0以下のr-1個の素数k1, k2, ..., kr-1を決める。 kiに対して、kiをそのままCに入れるか、ki = a0 + a1 + … + am(ただしaは任意の自然数列) …
問題 6面が、赤、白、青に塗られた立方体が8つ並んだパズルがある。 このパズルの初期局面および、目的の局面が与えられたとき、 目的の局面に至るための手数の最小値を求めよ。 30手以内に目的の局面に至れない場合は-1を出力せよ。
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017) 制約条件 H≦16 W≦50 部屋の最も外側のマスは壁である。
問題 xy平面上の点Aから点Bまで移動したい。 レーザーが、a秒間のチャージの後でb秒間照射される、その後またa秒間のチャージの後でb秒間照射される という規則で照射される。 レーザーがチャージ中の時間は、1単位時間あたり1単位距離の移動が可能であるが…
問題 h x wの長方形の領域に、1x1, 2x2, ... mxmの正方形のタイルを敷き詰める。 使わないタイルがあったり、タイル同士が重なったりしてはならない。 タイル同士には隙間があってもよい。 このとき、最大のmを求めよ。 制約条件 h, w≦30
問題 1番から順に番号のついたビリヤードの球が、下図のようにn段に並んでいる。 [ 5] [ 2][ 3] [ 4][ 1][ 6] [ 7][ 8][ 9][10] [11][12][13][14][15]1の球に対して、上下に隣接する球のいずれかと入れ替える操作を行うことができる。 [ 1] [ 2][ 3] [ 4][ 5…
問題 w x hのグリッドであらわされる部屋がある。 部屋の各マスは0(ふつうのマス)または1(破損したマス)のどちらかである。 今、正方形のカーペットを何枚か敷いて、0のマスは一切覆わずに1のマスを全て覆いたい。 カーペットは好きな大きさのものを何枚…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2355) 制約条件 n≦8 -10^5≦f≦10^5 -10^5≦xi≦10^5
問題 hxwのグリッドが与えられる。 グリッドのそれぞれには1〜9の数字が書かれている。 このグリッドの(startRow,startCol)を出発して、(goalRow,goalCol)へ行きたい。 一回の移動では、上下左右に何回か動くことができる。 ただし、一回の移動中に通ったマ…
問題 3種類の硬貨があり、それぞれの価値はvalue[i]である。 先手がi枚目のコインをlennysCoins[i]枚もって、 後手がi枚目のコインをfredsCoins[i]枚もって、次のようなゲームを行う。 ポットに手持ちから一枚コインを入れる 入れたコインの価値より小さい額…
問題 数字に対して次の操作が好きなだけ出来る。 0でない桁を二つ選び、それぞれから1を引いたあと、それぞれを交換する。 Nが与えられたとき、操作を0回以上して得られる数のうち、最大のものを求めよ。 制約条件 N≦1000000
問題 n個の数が与えられる。 これらのうちの最小値をm,最大値をMとする。 この数のうち、3個以上がその項となっているような等差数列のうち、 (初項-d)がm以下、(末項+d)がM以上となっているようなものを考える。 この等差数列の項数をq、q個のうちn個の数の…
問題 hxwのマスで表される迷路がある。 それぞれのマスは 'A'は壁が四方にないこと 'B'は壁が四方全部にあること 'C'は壁が左右方向にだけあること 'D'は壁が上下方向にだけあること を意味する。 左上のマスを出発して、右下のマスまで辿り着きたい。 1ター…
問題 n種類の質問をした。 何回か同じ質問をしたかもしれないが、質問に対しては"Yes"または"No"の答えが返る。 それぞれの質問に対する答えが与えられるとき、質問の仕方は何通りあるか求めよ。 制約条件 n≦9 質問の個数≦9
問題 数字からなる文字列の積を、その各桁の積とする。 数字からなる文字列がcolorfulであるとは、 (空でない)連続する部分文字列の積が、全て互いに異なることを言う。 n桁のcolorfulな文字列のうち、k番目に小さいものを求めよ。 n桁のcolorfulな文字列…
問題 番号のかかれたくじがある。(leading zeroがある場合がある) このくじは、書かれた数が0または、約数の個数が奇数なら当たりである。 くじの番号を何桁か書き換えて当たりにしたい。 最小で何桁を変えなければならないか、求めよ。 制約条件 くじにか…
問題 nxmのグリッドがある。 グリッドの一部のマスは障害物'#'で埋められている。それ以外のマスを、ブロック2個〜ブロック5個の塊(縦または横につながったもの。形は自由)で埋めることができるか。 できるなら埋め方の一例を出力し、そうでない場合は-1を…
問題 100x100のスライドパズルがある。 最初(emptyRow,emptyCol)のマスが空白である。 (carRow,carCol)のマスを(0,0)に移動させるのに最小で何手かかるか求めよ。 スライドパズルは、ピースと空白を入れ替える操作のみが出来て、 ピースを外に出したり、重ね…
問題 nxnのチェス盤と二つの駒を使って二人が次のようなゲームをする。 最初先手の駒は(y1,x1)の位置に、後手の駒は(y2,x2)の位置におかれている。 二人は交互に、駒を上下左右の好きな方向へ、先手は1歩、後手は1歩または2歩動かす。 相手の駒を取ったプレ…