問題. 列 長さ の非負整数列 と整数 が与えられる． の連続部分列でその積が 以下となるものの長さの最大値を答えよ．制約： ，

問題. 三角形の分類 平面上にどの3点も同一直線上にない 個の点が与えられる． 番目の点 の座標を とする． 個の点の中から異なる3点を選び三角形を作る．その中で鋭角三角形，直角三角形と鈍角三角形の数をそれぞれ求めよ．制約：

問題. Subtree 頂点の木 がある．各頂点 に対して， を含む部分木の数を答えよ．制約：

問題. Permutation 各文字が '' からなる長さ の文字列 が与えられる． 上の順列 で次の条件を満たすものが何通りあるか求めよ． ・ が ' ・ が '>' ならば 制約：

ラベル付き木から prüfer sequence（プリューファ列）と呼ばれる整数列への一対一対応を説明します．

問題. Luigi's Tavern 人の勇者， 人の戦士， 人の聖職者と 人の魔術師がいる．次を満たすパーティを最大いくつ作ることができるかを求めよ．ただし，友達の制約は入力として与えられる． ・どのパーティにも勇者がいる ・パーティ内の勇者と戦士は友達 ・パ…

頂点被覆問題がNP完全であることを示します．頂点被覆問題のNP完全性から独立集合問題とクリーク問題がNP完全であることが導かれます．

問題. Routing a Marathon Race 無向グラフ ，2頂点 ，頂点重み が与えられる． から へのコスト最小の道を見つけそのコストを答えよ．ただし，道のコストとはその道に含まれる頂点の重み和と，道に少なくとも1頂点が隣接する道以外の頂点の重み和を足したも…

強多項式時間と弱多項式時間について紹介します．

問題. Lotus Leaves 縦 行，横 列の長方形の池がある．池にはいくつか蓮の葉が浮かんでおり，同じ行または列にある葉へは双方向に移動可能である．カエルが葉 から へ移動しようとしている．葉 以外の葉を取り除くことによって から へ到達できなくなるかを…

問題. お風呂は気持ちいい 人の魔法使いがいて，その内 人が魔導石に近い場所にいる．魔法使い から魔法使い へ最大 の魔力を受け渡すことができるという 個のリストが与えられる．魔導石からは無限に魔力が湧き出ており，魔導石に近い魔法使いは魔導石から…

問題. Sixth Sense 2つの整数列 が与えられる． 番目の要素が よりも大きくなるような要素が最も多くなるように を並び替えよ．そのような並び方が複数ある場合は辞書式順序で最も大きいものを求めよ．制約： ，

問題. Four-Coloring 無向グラフ の平面描画が与えられる．頂点 の座標を としたとき，各辺 に対して ， または が成立つ．このとき， の4彩色を求めよ． 制約： ， （整数座標）

命題論理式を充足可能性が等価な連言標準形に変換する方法であるTseytin変換（Tseytin Transformation）について紹介します．

有限オートマトンによって認識不可能な言語を非正規言語と呼ぶ．ここでは，ある言語が非正規言語となることを示すのによく用いられるポンピング補題について紹介する．

問題. 755 整数 が与えられる． 以上 以下の整数のうち，各桁が数字 '3', '5', '7' のいずれかで，かつ，'3', '5', '7' の数字が少なくとも1回以上現れるものの数を求めよ．制約：

問題. Shortest Common Non-Subsequence '0' と '1' からなる2つの文字列 が与えられる． と のどちらの部分文字列でもない '0' と '1' からなる文字列で最小の長さのものを求めよ．ただし，答えが複数ある場合は辞書順で最小のものを求めよ．制約：

問題. What Goes Up Must Come Down 非負整数列 が与えられる． の隣り合う2要素を交換するという操作を繰り返して を山型にしたい．ただし，数列 が山型であるとは，ある要素 が存在して， となることである．数列 を山型にするための交換回数の最小値を求…

問題. Silver Matrix 自然数 が与えられたときに次を満たす Silver Matrix を1つ構成せよ． 1. サイズ の正方行列 () 2. の各要素 3. 各 に対して， 制約： （サイズが のときは解が存在することが保証される）

巡回セールスマン問題 (Travelling salesman problem; TSP) を高速に解く Concorde のインストール方法のメモ．

問題. 全チームによるプレーオフ チームで引き分けのない総当たり戦を行う． 試合の結果が確定しているときに，残りのすべての試合を行い，すべてのチームの勝利数が等しくなる試合結果（プレーオフ）の組合せ数を求めよ．制約： ，

問題. HSI 個のテストケースを解くプログラムを書いた．どの提出でも， ケースはそれぞれ確率 で正解して各実行時間が 1900 ms となる．残りの ケースではそれぞれ必ず正解して各実行時間が 100 ms となる．すべてのテストケースが同時に正解するまで提出す…

問題. FT Robot 二次元平面上の原点に 軸の正方向を向いているロボットがいる．命令列 s を先頭から順番に実行していく．現在見ている命令が 'F' ならば今向いている方向に1だけ進み，'T' ならば時計回りか半時計回りに向きを変える．命令列 s を実行して へ…

問題. 半分 非負整数列 と非負整数 が与えられる．数列にちょうど 回の操作を行ったあとの数列としてありうるものの個数を求めよ．ただし，各操作とは 番目の要素を 2 で割った商の小数点以下切り捨てた値に置き換えることである．制約： ， ，

問題. 自然数列の整列 要素数 以下の 個の自然数列 が与えられる．これらを辞書式順に昇順に整列せよ．ただし， であるとは， が の先頭部分に一致するか，または， を となる最小の添字としたときに となることである．制約：

問題. Two Sequences 2つの長さ の非負数列 ， が与えられる． を求めよ．ただし， はビット単位の排他的論理和である．制約： ，

問題. Worst Case 人が2回コンテストに参加した．各コンテストでの順位は1位から 位と全員が異なった順位となった．参加者のスコアを2回のコンテストの順位の積としたとき，次の 個のクエリを答えよ． 番目クエリ はある参加者の1回目と2回目の順位の組であ…

問題. Ruined Square 平面上に正方形があり，頂点は時計回りに である． が与えられたときに を答えよ．

問題. Ribbons on Tree 頂点の木が与えられる．木のどの頂点もちょうど1つの頂点対に割り当てられるような 個の頂点対への分割を考える．そのような分割で，どの辺もある組の最短経路上にあるような分割が何通りあるかを求めよ．制約：

問題. Median of Medians 整数列 が与えられる． の連続部分列 の中央値を とする．このとき， の中央値を求めよ．ただし，長さ の数列の中央値とは，数列を昇順にソートしたときの小さい方から 番目の要素の値である．制約： ,