2012-06-01から1ヶ月間の記事一覧
問題 日本語なので本文参照。 制約条件 h, w≦12
問題 幅h, 高さwのグリッドがある。 グリッドには 0 1 2 ... w-1 w w+1 w+2 ... 2w-1 ... のように数字が書かれている。 このグリッドの長方形の部分で、書かれている数字の総和がSであるような部分のうち、 最も面積が小さいものの面積を求めよ。 そのよう…
問題 最後からk個のアクセスのメモリをキャッシュするコンピュータがある。 このコンピュータに次のようなクエリが来る。 ADDR x : xの番地にアクセスする。 RANGE b y n : bの番地から、0≦i<nとしてb + i * yの番地に順にアクセスする。 STAT : 前回のSTAT…
問題 n x nマスの盤の上にいくつかコマが乗っている。 コマの乗っているマスは'C'であり、乗っていないマスは'.'で与えられる。 初期状態において、i行目に置かれているコマの数をrow[i]とする。 コマを、一つ選び、上下左右の空いているマスへ移動させると…
前の記事の問題で、SRM300以降のDiv1 Medium全問解きました! (300以前のは、質が悪い問題が多かったり、今と傾向が違いすぎたりであまりやる意味がない) これからはHardを埋める練習をしていきたいと思います。 Hardは難易度が桁違いなので苦戦しそう…… H…
問題 tについての方程式at^2 + bt + c = 0であって、 係数a, b, cが-k以上k以下の整数で、 t = (x + y * √d) / zを解の一つとして持つようなものはいくつあるか、求めよ。 制約条件 0≦k≦10^6 -1000≦x, y, z≦1000 zは0でない 1≦d≦1000
問題 n個の文字列が与えられる。 それぞれの文字列は、文字列の中で文字の順序を自由に入れ替えてよい。 入れ替えた後で、trie木を作る。 文字の順序を最適に入れ替えたとき、trie木の頂点の数は最小でいくつか、求めよ。 制約条件 n≦16 各文字列の長さ≦50
問題 次のようにしてフラクタルな図形を描く。 第一世代: (0, 0)から(0, 81)の世代 第二世代: 前の線分の上1/3を三つに枝分かれさせる((0, 54)から、(0, 81), (-27, 54), (27, 54)に) 第三世代: 枝分かれした三つの枝を、更に同様に三つずつに枝分かれ…
問題 次のように定義される数列aがある。 a[0] = first a[1] = second a[i] = | a[i - 1] - a[i - 2] | (i > 1) このとき、aのx番目の要素を求めよ。 制約条件 first, second≦10^18 x≦10^18
問題 二つの異なる数字が書かれたドミノがいくつかある。 このドミノを全て使って、全体がちょうどいくつかの輪になるように並べる。 ドミノが輪になっているとは、 左右に隣合うドミノの、隣り合う側の数字がすべて等しく、 かつ、最初のドミノと最後のドミ…
問題 中心からn本の通路が伸びた建物がある。 それぞれの通路の長さはcorridors[i]である。 0番の通路の端からスタートして、 「中心へ行き、今来た通路でない通路を等確率で一つ選んでその通路の端まで行く」 ということを繰り返して、全ての通路を一度以上…
問題 y軸に平行な線分がいくつか与えられる。 これらのうち、好きなものと、任意のx軸に平行な線分を使って、辺が全て座標軸に平行で、 自己交差のない単純多角形を描きたい。 描ける多角形のうち、もっとも辺の多いものの辺の数はいくつか、求めよ。 制約条…
問題 n行m列の行列が与えられる。 それぞれの成分の値は0以上50未満の整数であり、全ての行は異なっていて、 なおかつ可能な全ての行が含まれている。 この行列の行を以下のような手順でソートする。 それぞれの列ごとに、1〜50の順列を作成する。この順列は…
問題 半径5の円がある。 この円周上から三点を、それぞれのx軸から半時計周りに見た角度が区間[angleFrom[i], angleTo[i]]のいずれかに入っているように選ぶ。 このとき、三角形ABCの面積の最大値を求めよ。 制約条件 angleFromとangleToの要素の数は等しい …
問題 n x mのグリッドで表される地図が与えられる。 'x'のマスは陸であり、'.'のマスは海である。 島とは、'x'のマスが上下左右斜めにつながった塊であり、 海は上下左右のマスとつながっている。 島のlevelとは、島に対して以下のように定義される量である…
問題 A〜Zのアルファベットで表される物質がある。 最初initialで表される物質を持っている。 錬金反応を何度か起こして物質Xを作りたい。 錬金反応は最低何回起こさなければならないか、求めよ。 錬金反応は、 原料の物質->目的の物質の形式で与えられる。 …
問題 いくつかのwebサイトのリンクの関係が与えられる。 websiterankとは次のような値である。 最初、全てのサイトの値は1. サイトAからサイトBへリンクがあるとき、サイトBの値にサイトAの値を足す。 ただし、サイトBからサイトAへ直接、または間接的にリン…
問題 k人がn個の石を使って次のようなゲームをする。 k人は時計回りに並び、1番の人から時計回りに順にターンをまわす。 ターンの人は山から石を取る。このとき取れる石の個数は下の条件を満たす必要がある。 山の石がなくなったときゲーム終了。最後に石を…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp) 制約条件 クエリの数≦200000
問題 nチームが何試合か試合をした。 同じ組み合わせのチームが何回か対戦した、または一度も対戦していないチームの組み合わせがあることがある。 試合で勝ったチームにはw点が入り、試合が引き分けだと両方のチームにd点が入る。 全てのチームの得た得点が…
問題 次のような携帯の文字列入力がある。2-9のボタンに次の文字が対応している。 2 a,b,c 3 d,e,f 4 g,h,i 5 j,k,l 6 m,n,o 7 p,q,r,s 8 t,u,v 9 w,x,y,z 携帯は次の三つの内部状態を持つ。 D: 今まで入力した数字 U: 未確定の文字列 F: 確定の文字列 辞書…
問題 同じ色のぷよがL匹くっつくと消える。 筒にぷよぷよを一匹ずつ、合計N匹いれる。 全てのぷよを入れ終えたときに、筒の中が空になっているような、 ぷよの入れ方の場合の数を求めよ。 制約条件 2≦L≦20 N≦1000
問題 hex座標で表されるNxNのフィールドがある。 フィールドのいくつかのマスは埋まっている。 埋まっていないマス全てに、1x2のブロックを敷き詰める。 ブロックは重なったり、フィールドの外に出たりしてはならない。 ブロックの置き方の場合の数をmod 2 *…
問題 凸多角柱で表されるn個の建物がある 太陽がx軸から反時計回りにθの角度の方向で、高さφの角度にある。 m本の道があって、それぞれの道は線分である。 スタートの点(sx, sy)からゴールの点(gx, gy)へ、道を通って行く。 道のうち太陽の当たっている部分…
問題 n本の相異なる直線が与えられる。 n本の直線の集合の、点対称の中心の個数を求めよ。 無限にある場合は-1を返せ。 制約条件 n≦50 直線はその直線が通る2点の座標により与えられる。 点は全て格子点である。
問題 ある数列がk-monotonicであるとは、数列を連続するk個の区間に分けて、 それぞれの区間が全て単調数列(真に単調増加または単調減少)にできることを言う。 与えられた数列a[i]とkに対して、a[i]の要素を一つ選び、 その要素を+1または-1する操作を何回…
問題 start以上end以下で以下の条件を満たす数の総和を求めよ。 2進法で書いたときに1の数がmaxone個以下 2進法で書いたときにIdeal Numberと違う桁がk個以下 制約条件 全ての入力は10^9以下の正の整数
問題 n x mのマスのそれぞれにコインがa[i][j]枚置いてある。 これを使って次のようなゲームをする。 先手後手が交互に手番を持つ。 手番のプレイヤーは、コインが一枚以上置いてあるマスを選び、コインを好きな枚数だけ選ぶ。 選んだコインを、下または右の…
問題 power Aのcool numberを以下のような数と定義する。 数字を連続するA個に区切って、 それぞれの区間において、一つ一つの桁の数字が等差数列になっているようにすることができる。 power Aのmega cool numberとは 各桁の数字が非減少列になっていて、 p…
問題 最初A個の0とB個の1が並んでいる。 この中から、異なるちょうどK個の数字を自由に選び、0と1を反転させる操作を行うことができる。 最短でこの操作を何回行えば全ての数字を1にすることが出来るか、求めよ。 操作をどのように行っても1にすることができ…