命題論理式を充足可能性が等価な連言標準形に変換する方法である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要素を交換するという操作を繰り返して を山型にしたい．ただし，数列 が山型であるとは，ある要素 が存在して， となることである．数列 を山型にするための交換回数の最小値を求…

問題. Arithmetic Progressions 非負整数からなる集合 が与えられる． の部分集合で等差数列となるものの中で要素数最大のものを見つけ，その要素数を答えよ．制約： ，

問題. 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 で割った商の小数点以下切り捨てた値に置き換えることである．制約： ， ，

海外ドラマで英会話力をUpする方法に英語音声を，「内容理解 → 英語字幕有り → 英語字幕無し」の3段階で耳を慣らすのが良いと聞き，情報系の動画で，英語字幕と日本語字幕の両方がある英語音声のYouTube動画をまとめました．主に1つのモノや出来事を数分で紹…

問題. Garbage Collector 数直線上に 個 のゴミが左から順番に の場所にある．ゴミ箱は原点にあり，すべてのゴミを捨てたい．各動作についてコストがかかり，1つのゴミを拾うのに ，いくつかのゴミを捨てるのに ，ゴミを 個持っているときに1移動するのに ．…

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

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

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

問題. All Your Paths are Different Lengths 整数 が与えられるので次を満たす多重有向グラフ とその弧重み を構成せよ． ・ ，かつ，頂点のラベルは互いに異なり ・ ，かつ，任意の弧 に対して， ・ 任意の弧 に対して， ・頂点1から までの互いに異なるパ…

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

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

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

問題. ゲーム 2人で交互に行うゲームを考える．2つの山にはそれぞれ 個と 個のブロックが垂直に置かれており，上からそれぞれ ， の価値がある．交互にどちらかの山の上から1個のブロックを取る．互いに選択した価値の和が最大となるような最適な戦略を行っ…

問題. コンテスト 問の問題があり， 問目の配点は 点である．考えうる得点は何通りかを求めよ． 制約： ，

問題. 毎日が誕生日パーティー（勝手に命名） 1年が365日の世界に， 人の社員がいる．各社員の誕生日は365日の間に等確率で分布する．このとき，どの日にも少なくとも1人の社員が誕生日となる確率を求めたい（誕生日の人がいるとパーティー）． (1) が 365 …

問題. グラフ 頂点からなる単純有向グラフ が与えられる． の2つの有向道の頂点の和集合のサイズが最も大きいものを求めよ． 制約：

問題. DAGの最小道被覆問題 DAG が与えられる． の最小道被覆を求めよ．

問題. 0-1ナップサック問題(0-1 Knapsack Problem) 個のアイテムからなる集合が与えられる． 番目のアイテムは価値 と重さ を持っている．アイテムをいくつか選び，重み和が 以下で価値の和が最大となるようなものを選べ．

比較可能グラフが理想グラフであることを示します．

グラフを描画するためのツールをまとめておきます．他に知っている方は教えてくださると喜びます．

問題. Parallel Lines 2次元平面上に 個の点がある．どの点もちょうど1つの対に含まれるように，すべての点から 個の対を作ることを考える．ここで，各対を対に含まれる2点を通る直線として考えると，いくつかの平行な直線に分割される．その分割の各部分の…