2018-12-01から1ヶ月間の記事一覧

Tseytin変換

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

ポンピング補題

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

ABC114 C問題 : 755

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

ICPCアジア地区横浜大会2018 D問題 : Shortest Common Non-Subsequence

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

ICPCアジア地区横浜大会2018 G問題 : What Goes Up Must Come Down

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

ICPCアジア地区横浜大会2018 B問題 : Arithmetic Progressions

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