問題 サイズNの文字列とサイズMの数列が与えられる。文字列は'A','B','X'の3文字で構成され、'A'と'B'には以下の操作する。 'X'には数列の要素が入る。 'X'に適切に数字を割り当てることで返される最大の数字を求めよ。 解法 与えられる文字列からASTを構成…

問題 ある文字列abcaのインデックスiに応じた接尾辞を考える。例としてs[0] = abca、s[1] = bcaとなる。 全ての接尾辞を列挙し、辞書順に並べ替えたインデックスをSAとする。abcaの場合は、SA = {3, 0 , 1, 2}となる。 SAとなる文字列の中で、最小の違う文字…

問題 N個の飴の売店がある。飴には、N種類の形とN種類の味がある。各店は1種類の形で違う味の飴をそれぞれN1、N2個ずつ売っている。ひとつの味には2つの形が必ず存在する。 N種類全部の飴を手に入れるのに必要な飴の数を求めよ。 解法 ひとつの味には2つの形…

問題 N個()のアラームが与えられる。各アラームは、にをの間隔で鳴らすようになっている。Alexは眠気指数Sを持っており、毎分Dずつ増えていく。これが0以下になると目覚める。Alexが起きることができる最大のSを求めよ。 解法 アラーム全体での周期を求め、…

問題 長さN()のケーキが与えられる。Nの割れる数の人数が来ることは分かるが、正確な人数は分からない。来る人数に対して平等にケーキを分配するためにはいくつのピースに分けてケーキを切ればいいか求めよ。 解法 割れる数の倍数の集合を求めると、その集合…

問題 サイズN()のグラフが与えられる。各ノードは2つの親を持つか、何も持たないかである。全ての親の性別が男性と女性で分けられる場合は、グラフはFamily treeとなる。与えらたグラフがFamily treeかどうか判別せよ。 解法 二部グラフ判定を行うことで、答…

問題 二人のプレイヤーがいて、サイズN()の数列が与えられる。交互に配列に対して操作を行い、操作ができなくなったプレイヤーが負けとなる。操作は以下となる。 2以上の値を持つ要素を選ぶ この要素を空ではない2つの要素に分割 最初に選んだ要素を含まない…

コード テスト

問題 (a, b)と(c, d)の2組の数字のペアが与えられる。任意のペア(x, y)を考える。可能な操作は(x+y, y)または(x, x+y)である。(a, b)と(c, d)が作れる(x, y)のペアを求め、その中でx+yが最大となるペアを求めよ。作れない場合は-1を返す。 解法 (a, b)または…

問題 平面の上に中心点が、半径がの円がN個存在する。平面の中心(0,0)から半径rの円を新しく描く。rは[0,Z]の中からランダムに選ばれる。この時、新しく描く円が既に存在するそれぞれの円と全く被らないか、全て被る場合は良い円とする。逆に、一部だけ被っ…

問題 N個()の頂点を持ち、dist[i][j]()のコストの一方向の辺を持つグラフが与えられる。それぞれの頂点からそれぞれの頂点への最短路を考えた時、T()より多い回数を通る辺のコストの総和を求めよ。 解法 d[i][j]は最短路のコストを表す。ある辺が最短路に含…

問題 N*Nの平面()に、AppleとPearが置かれている。空白のマスも存在する。ひとつのフルーツを取り出しそれを空のマスへ移動するという操作をK回()することができる。Appleで満たされる長方形の最大面積を求めよ。 解法 ある長方形をAppleで満たせるかを全探…

問題 サイズN()の数列が与えられる。任意の要素に数字を足していくことで同じ値の要素を増やしていく。同じ値の要素数をiとし、その要素数を作るのに必要な最小な値をとする。の全要素でのXORの値を求めよ。 解法 愚直に全探索を行うととなる。はある要素に…

問題 長さN()の文字列が与えられる。文字列の順番を入れ替えて新しい文字列を作成する。新しく作成した文字列の集合(最初の文字列も含む)からランダムに値を取り出す。その文字列が回文になっている確立を求めよ。 解法 文字列の集合の要素数は順列を用いる…

問題 AliceとBobがいる。Aliceはa個のb面あるサイコロを転がし、Bobはc個のd面あるサイコロを転がす。サイコロの目の合計が高い方が勝ちとする。Aliceが勝利する時のサイコロの目の期待値を求めよ。 解法 はじめに、スコアに対する確率分布を求める。 Alice…

問題 長さN()の文字列が与えられる。その中で違う文字同士のペアを取り出す。取り出すペアが無くなった時点で終了となり、この時に残っている文字をwinning letterと呼ぶ。winning letterの文字列を辞書順にして求めよ。 解法 サイズが小さいので一文字ずつw…

問題 割れる数を求める関数dを用いてとなる関数hを定義する。h(x)の値n()からxを求めよ。 解法 nの値が大きいので、xを全探索して答えを見つけることはできない。d(n)の値は十分小さいので、この値について全探索を行う。 を計算し、となることを確認する。 …

問題 横幅がW、縦幅がHの四角形の穴があり、それを埋めるための四角形の板がN個()与えれる。穴を埋めるの最小な板の数を求めよ。 ただし、以下の条件を満たさなければならない。 板の四隅は穴の外側(板の横幅か縦幅のどちらかが穴の横幅か縦幅より真に大きい…

問題 ノード数がN()の木(tree)が与えられる。各辺(edge)は双方向(bidirectional)であり、長さlength()が定義されている。互いに同じ距離となるノードの集合の最大要素数を答えよ。 解法 まずノードの数が1つである場合は1となり、2の場合は必ず2となる。 木…

コード 実装日 1回目:1/24 テスト POJ1258 関連問題 POJ1258

コード 実装日 1回目:1/24 テスト POJ1258 関連問題 POJ1258

コード 実装日 1回目:1/23 テスト POJ1258 関連問題 POJ1258

コード 実装日 1回目:1/19 テスト 関連問題

コード 実装日 1回目:1/19 テスト 関連問題

コード 実装日 1回目:1/19 テスト 関連問題

コード 実装日 1日目:1/19 テスト 関連問題

コード 実装日 1回目:1/19 テスト 関連問題

コード 実装日 1回目: 1/18 テスト 関連問題 AOJ0558

コード 実装日 1回目:1/18 テスト 関連問題 POJ2431

コード 実装日 1回目:1/17 テスト 関連問題 天下一プログラマコンテスト2013予選BのA問題