PKU
問題 文字列に対して自然数を一意に割り当てる。 割り当て方は、文字列を短い順に並べ、その中で辞書順で並べて、頭から1,2,3という規則で行う。 文字列または自然数が与えられるので、 文字列と対応する自然数(3桁ごとにコンマで区切る)を出力せよ。 制約…
問題 x,y,zがN以下であるようなピタゴラス数(x^2+y^2=z^2を満たす自然数)のうち、 互いに素なものの個数および、N以下で、(互いに素ではないピタゴラス数も含む)どのピタゴラス数の1つにもなっていないような自然数の個数を出力せよ。 制約条件 N≦1000000
問題 n個の買い物すべき商品のリストが与えられる。 商品はリストに登場する順に、全てを買わなければならない。 m個の棚の情報が与えられる。 棚には一つの商品が置かれていて、値段が決まっている。 棚は、与えられた順に見るものとし、戻ることはできない…
問題 変数の集合と、変数の大小関係が与えられる。 大小関係を全て満たすような、変数の順序を全て、辞書順に出力せよ。 制約条件 変数の数≦20 制約条件≦50 答えの数≦500
問題 自然数aが与えられる。 arctan 1/a = arctan 1/b + arctan 1/cを満たす、ような自然数b,cに対して、 b+cの最小値を求めよ。 ただしarctan (p) + arctan (q) = arctan [(p + q) / (1-pq)]が成り立つ。 制約条件 a≦60000
問題 '0','1'のHxWマスのグリッドで表される星空がある。 '1'のマスが上下左右斜めにつながっている部分は一つの星座とみなす。 それぞれの星座にアルファベットの小文字を割り当てて出力せよ。 ただし、回転、反転をさせると重なる星座には同じ文字を割り当…
問題 A/Bという分数が与えられる。 この分数に対して、次のような分数列を求めよ。 分母が前の分数より常に大きい 前の分数よりもA/Bに対する良い近似を与える 項数が最大 近似が同じ分子が二通りある場合、分子の大きいほうを採用する 例えばA=5, B=4の場合…
蟻本復習中。 問題 N組のカップルが同じ日に結婚式を挙げる。 i番目の結婚式は時刻s[i]からt[i]の間に開かれ、その最初か最後のどちらかのd[i]分間特別な式典を行う必要がある。 (s[i]〜s[i]+d[i]かt[i]-d[i]〜t[i]のどちらか) 式典には司祭の出席が必要で…
蟻本復習中。 問題 N頭の牛が、順に一直線に並ぶ。 牛には好き嫌いがあり、ML個の好きの関係およびMD個の嫌いの関係がある。 好きの関係は3つの整数AL,BL,DLにより指定され、 ALの牛とBLの牛が距離DL以内にいなければならないことを表す。 嫌いの関係は3つの…
問題。 数列が与えられる。最長増加部分列の長さを求めよ。
問題 自己交差のない多角形が、頂点の座標(時計回りまたは反時計回り)として与えられる。 面積を最も近い整数に丸めて求めよ。
問題 整数N, Cが与えられる。 T(C - TN)を最大にするような整数Tを求めよ。 複数ある場合は最も小さいものを求めよ。
問題 長さ3の数列が与えられる。 単調増加または単調減少になっているかを判定せよ。
問題 数列が与えられる。 2つ以上同じ数が連続していたら、それを一つに置き換えた数列を返せ。
問題 じゃんけんの二人の手が与えられる。 それぞれが何回勝ったか出力せよ。 方針 シミュレーション。
問題 nxmのグリッドで表されるウィンドウの図がある。 このうち最前面にあるウィンドウを全て答えよ。 制約条件 n,m≦100
問題 全ての辺と頂点に重みのついた、頂点数nの完全グラフが与えられる。 このグラフの部分木で頂点数がmのもののうちで、以下の値が最小になるようなものの頂点を小さい順に出力せよ。 Σ(部分木に含まれる頂点の重み)/Σ(部分木に含まれる頂点の重み) 複数あ…
問題概要 正n多角形のうち3つの頂点の座標が与えられる。 正多角形の全ての頂点を含み、各辺が座標軸に平行で面積最小の長方形の面積を求めよ。
問題概要 Martians族と会談するのに、ある人の祖先はある人の子孫よりも先に会談しなければならない。 人ごとに子供の番号のリストが与えられるとき、会談する順番を(どれか一通り)出力せよ。 そのような答えがあることは保証されている。 N≦100を満たす。
問題概要 nの順列とは、1〜nの数字が一度ずつ表れる数列のことを言う。 P(i)を順列のk番目の文字とする。 P1(i)=P(i),P2(i)=P(P(i)),P3(i)=P(P(P(i)))…と定義する。nの順列が与えられるとき、 Pk(1),Pk(2),…,Pk(n)がもとの順列に一致するような最小のkを求め…
問題概要 チップの山S1,S2を、S2の最も下のチップを取り、新たな山S12に置く。 S1の最も下のチップを取り、S12の一番上に置く。 S2の最も下のチップを……と繰り返して山S12を作る。 山S12が目標の配列ならばシャッフルは終了で、そうでないならS12の下半分を…
問題概要 長方形をしており、上の辺の左側に突起がl個、中央に突起がm個ある板がある。 板の下の辺には同じ位置に同じ個数だけくぼみがあり、板を並べることができる。2枚の板の突起の数をl,m,l',m'とすると、l≧l', m≧m'のとき板を並べることができる。 n枚…
問題概要 20個の国があり、それぞれの国の隣接関係が与えられる。 スタートの国からゴールの国まで辿り着くのに越えなければならない最小の国境の数を求めよ。
問題概要 座標平面上の点がn個与えられる。 一直線上に乗る最大の点の数を求めよ。 n<700,点の座標は全て整数とする。
問題概要 文字列が与えられる。この文字列の連続する部分文字列で、長さがnのものはいくつあるか求めよ。文字列の文字の数はncで、部分文字列の数は1600万を超えない。
問題概要 h階建で、各フロアにl台の駐車スペースのある駐車場がある。 それぞれのスペースに止まっている車が、何番目に出るかが与えられる。 ただしスペースが空の時は-1が与えられる。 このとき、全ての車が駐車場から出るまでにかかる時間を求めよ。 車は…
問題概要 カードの列がある。それぞれのカードの表と裏にはアルファベット一文字で表わされる色が塗られている。今、色の列Sが与えられる。 カードの列のカードを、好きなようにひっくり返して列を作り、その列の(連続するとは限らない)部分列としてSを含…
問題概要 白と黒の正方形のタイルがw,b枚ずつある。 このタイルを使って市松模様の正方形を作りたい。作れる最大の正方形の一辺の長さを求めよ。そのような正方形が作れない場合はImpossibleを出力せよ。 0≦w,b≦10000とする。
問題概要 座標平面の原点から、(x,y)まで、格子点を通り移動する。 1回の移動は座標軸に平行に、ちょうど1の距離だけ動ける。 座標平面上には、m個の泥の点があり、それらの点には移動することができない。 ゴールまで辿り着く最小の移動回数を求めよ。 500≦…
問題概要 幼稚園にはB人の男の子およびG人の女の子がいる。 男の子同士、女の子同士は全てお互いに知り合いである。 また、M組、お互いに知り合いの男女のペアがある。この中から任意二人が知り合いであるようなグループを作るとき、そのようなグループの最…