問題 与えられた偶数nに対して、以下の条件を満たすnxn行列を出力せよ。 対称行列である（a[i][j]=a[j][i]) 各行には0〜n-1が1度ずつ出現する 各列には0〜n-1が1度ずつ出現する 制約条件 n≦1000

問題 n項からなる数列a[i]とm項からなる数列b[i]が与えられる。 これら二つの数列に共通する（必ずしも連続しない）部分列で、かつ単調増加になっているもののうち、長さ最大のものを求めよ。 制約条件 n,m≦500

問題 レジスタがm個あるコンピュータを考える。 n個の出力をさせたい。 出力するためには、あらかじめレジスタにその値を代入しなければならないが、 レジスタに値xを代入するにはxの2進数で立っているビットの数に等しいコストがかかる。 （出力にはコスト…

問題 二進数を、 a1+a2+…+amという形で表したい。 ただしここで、aiはすべて±2^xという形をしているものとする。 与えられた二進数を、上の形で表すために必要な最小の項の数および、 その和の形を具体的に一例出力せよ。 制約条件 二進数の桁数≦10^6

問題 Logo Turtleを1次元で単純化したものを考える。 命令列はF（直進）およびT（反転）からなる。 与えられた命令列をちょうどn文字（同じ文字を2度以上変更してもよい）を変更して、 命令列を全て実行した後、亀が原点から最大でどれだけ遠くまで離れられ…

問題 整数の配列に対して以下の操作をする。 直前に出力した文字のASCIIコードの8ビットを反転（逆から読む）させる 上の結果（0文字目の場合は0とする）からi番目の配列の値をmod 256で引く 再び8ビットを反転（逆から読む）させて、そのASCIIコードをもつ…

問題 3本の線分があたえられる。これらが以下の条件を満たしているならYESを、そうでないならNOを出力せよ。 2本の線分が端点を共有する。（これを線分1,線分2とする） 線分1と線分2のなす角は0度より大きく、90度を超えない 線分3が、線分1,線分2の内部の点…

問題 点が(x[0],y[0],z[0])をスタートして、 折れ線(x[i],y[i],z[i])上を等速度vsで動く。 ハリーは、点(Px,Py,Pz)をスタートして、速度vpで等速で一直線上を動く。 ハリーは、点をつかまえることができるか。 出来るなら、YESと、その最短の時間および、そ…

問題 与えられた3つの点を頂点として持つような正多角形で、面積最小のものを求めよ。 制約条件 座標の絶対値≦1000 正多角形の角は100個以下

問題 Widgetを作るライブラリがあり、次のような命令をもつ。 Widget name(x,y) 名前がnameで幅x高さyのWidgetを作る Hbox name 名前がnameのHboxを作る Vbox name 名前がnameのVboxを作る name1.pack(name2) 名前がname1のウィジェットの中にname2のウィジ…

問題 n人の人が自分の色のカードa[i]枚ずつ持っている。 次のような条件を満たす「交換」を何度か行い、各人が持っているカードが全て自分以外の色になっているようにしたい。 それが可能であれば、Yesと、その交換手順を具体的に一通り出力し、不可能ならNo…

問題 数のペア(a,b)にを、(a+b,b)または(a,a+b)にかえる操作をすることができる。 (1,1)から始めて、ペアのどちらかの数がnになるのに必要な操作の最小回数を求めよ。 制約条件 n≦10^6

問題 n個の整数が与えられる。 このうちで、n個の整数の平均になっている整数の個数および、それらの番号を全て出力せよ。 制約条件 n≦2*10^5 a[i]≦1000

問題 円周上にn個の点が順に並んでいる。 これらにm本の辺を、互いに交差しないように引きたい。 それが可能なら、それぞれの辺は円の内側に引かれるか、外側に引かれるかを 具体例に対して一通り出力し、 不可能なら、Impossibleと出力せよ。 制約条件 n,m≦…

問題 nxmマスの長方形を、 1x2のタイルa枚 2x1のタイルb枚 2x2のタイルc枚を使って隙間なく埋めたい。 （使わないタイルがあってもよいが、タイルを回転させたり、重ねてはならない） それが可能なら、タイルの敷き詰め方を一通り出力せよ。 タイルの1マスは…

問題 数直線上にn個の足場があり、（1番目から数えて）k番目の足場は[(k-1)m,(k-1)m+l]の線分である。 0の点から、右に幅dだけジャンプして着地することを繰り返す。 足場がない場所に着地すると着地失敗であるが、足場の端に着地することはできる。 最初に…

問題 n個の頂点およびm本の辺からなる無向グラフが与えられる。 このグラフに含まれる閉路の個数を求めよ。 制約条件 n≦19

問題 26個のレジスタ(eax,ebx,……,ezx）をもつコンピュータがある。 lea x, [y] lea x, [y + z] lea x, [k*y] lea x, [y + k*z] （ただしx,y,zはレジスタ名、kは1,2,4,8の整数） の4つの命令を使い、いずれかのレジスタにeax * nの値を作りたい。 そのために…

問題 各桁の数字が全て4または7である数をlucky numberという。 例えば（4,7,477など） n項の数列に対してm個のクエリに答えよ。 add l r x 区間[l,r]の項全てにxを加算する count l r 区間[l,r]の項のうちlucky numberである数の個数を出力する 制約条件 n,…

問題 n冊の本がある。それぞれの高さはh[i]である。 この本から、 連続するa冊で 最も高い本と最も低い本の差がk以下 であるように本を選びたい。 aの最大値、そのときの本の選び方の数b、 具体的な本の選び方b通りを出力せよ。 制約条件 n≦10^5 h[i],k≦10^6

問題 n匹のうさぎがいる。 2種類のうわさをうさぎ全体に広げたい。 最初、knowledgeで指定されるうさぎが、2種類のうわさを両方知っている。 各うさぎは、 1日に、1種類のうわさを何匹にでも広めることができる 1日に何種類のうわさでも聞くことができる。 …

問題 nxmの板がある。 それぞれのマスは空白'.'またはコインが1枚載っている'o' 板を1つ横または縦に動かす操作が出来る。 操作の結果板からはみでたコインは落ちてなくなる。 操作を繰り返して板に載っているコインの数をちょうどk枚にしたい。 そのような…

問題 n個の都市があり、任意の二つの都市の間にそれらをつなぐ双方向に通行可能な道がある。 道にはそれぞれ相違なる自然数の通行料が定められている。 n個の都市を1周するとき、どのような順番で都市を巡っても、 通行料の総額が一定になる。 nが与えられた…

問題 3次元空間にn個の惑星があり、 1番の惑星から宇宙船が飛び立つ。 宇宙船は以下のような動きをする。 惑星から、他の全ての惑星に向かって一直線にn個の宇宙船が飛びたつ 他の惑星に着陸すると同時に他のn-2個の惑星に向かって宇宙船が飛び立つ 更にそれ…

問題 nxmのマスに1〜nの異なる数字を、 隣接するどの2マスの数字の差も2以上であるように入れたい。 そのような入れ方を1通り出力せよ。 不可能な場合-1を出力せよ。 制約条件 n,m≦100