はじめに
Atcoderでは「構築」というジャンルの問題が出されることがあります。
例題(AGC021-C) N*Mのマス目と1*2のタイルA枚と2*1のタイルB枚が与えられる。タイルを全て置けるか判定せよ。可能なら1つ例を示せ。
見ればわかるように、パズル要素が強く、「運ゲー」や「天才パズル」などと言われがちです。
そこで、私がこのジャンルの問題を解くときに使っている汎用性の高い考え方をまとめようと思います。
練習問題は難易度が高いのもあるので、解くのは後回しでも構いません(最後にはヒントも載せてあります)。
ちなみに、構築問題のDifficultyや点数は個人差があるので、だいたい信用できません。
ですので、それらが高い問題でも少しは考えてみるのをオススメします。
考え方1 条件の言い換え/可能な限り最適化
与えられた問題に対してどういった構築をすれば正解できるかという言い換えは非常に大事です。
具体的な条件を抽象的に言い換えたり、その逆をするのも役に立ちます。
例えば、文字列や数列に何回か操作した後のもので辞書順最小のものを求めるなら、先頭が小さくなるように操作した方が良いのではないかと言い換えてみるのもよいでしょう。
また、直接答えが導けることはなくても思考の手助けになることは多いです。
ここで重要なのは構築をするだけならば、必要十分条件を考える必要はないこともある、ということです。
例題(キーエンス-C) 整数N,K,Sが与えられるので、長さNの数列でX≦Yかつ第X項から第Y項までの和がSを満たす整数の組(X,Y)がK個存在するようなものを構築せよ。
X=Yでも問題ないのでSがあればあるほど良さそうです。そこで、条件を言い換えると、問題文は「整数SをK個含む長さNの数列を作れ。」と同値であることが分かります。
練習(ABC165-E) M個の対戦場に被りがないように数字を1個の対戦場につき2つ割り当てる。1からNの番号を持つN人の人が対戦場に自分の番号があれば行き、もう一人と対戦、その後全員の番号に1を足す(Nなら1になる)という動作をN回行う。N回の対戦で2回以上戦うようなペアが存在しないような割り当てを構築せよ。
問題文を読むだけでは動作が分かりにくいですが、番号Xの人と番号Yの人が戦うための条件を言い換えると考察しやすいと思います。
練習(AGC002-C) N本のロープがあり、N-1個の結び目で一直線に結ばれている。ひと繋がりのロープのうち、長さがL以上のものがあればそのロープの中の結び目を一つほどく。全ての結び目をほどくことができるか。可能ならほどき方を、不可能ならその旨を示せ。
条件の言い換えをすると、可能か不可能かの判定が簡単にでき、シンプルな問題にすることができます。
練習(AGC006-B) ある数列に対し、連続する3要素の中央値を順に並べることを繰り返して新たに数列を作る。これを数列の要素数が1になるまで繰り返す。整数X,Yが与えられるので1からXまでの数が使われた長さXの数列で、最後の数列の要素がYになるものを構築せよ。不可能ならその旨を示せ。
中央値がAになったとき、3つの数はどういうものだったかを考察すると、中央値をAにするための条件も自ずと見えてくると思います。
考え方2 場合分け
問題の内容を細分化してそれごとに考察するという考え方は有効である場合が多いです。
場合分けでベターなのは偶奇(mod2)での場合分けです。問題に詰まったらとりあえず偶数(奇数)の場合を考えてみるというのは悪くない手法です。
ある場合分けの考察に違う場合分けの考察で得られた結果が役に立つということもあります。
例題(ABC164-F) N*Nの行列で各行,列の論理和(論理積)が与えられた数字になるようなものを構築せよ。存在しない場合はその旨を示せ。
これはbit系の問題を考えるときには頻出のテクニックですが、bitごとに場合分けするという考え方が上手くいきます。これに論理和,論理積が指定された値になるという条件の言い換えを加えると後は実装メインになります。
練習(AGC032-B) N頂点のグラフで各頂点について隣接している頂点の番号の合計が一定になるようなものを構築せよ。
Nを偶奇で場合分けして考察すると、和がこうなればよさそうという考えに持っていきやすいと思います。
練習(AGC021-C) N*Mのマス目と1*2のタイルA枚と2*1のタイルB枚が与えられる。タイルを全て置けるか判定せよ。可能なら1つ例を示せ。
同じ向きのタイル2枚を並べると2*2のマス目が完成するという自然な発想から場合分けしてあげると考えやすいです(ちなみに、結構気づきにくいコーナーケースがあります)。
考え方3 小規模/大規模なものを考えてみる
「例えば条件を満たすN*Nの行列を出力せよ。(1≦N≦1000)」という問題があったとき、いきなりN=1000の場合を考えるのは無謀な場合もありますが、N<8程度の場合を考えるのは手作業でもなんとかなりますし、それこそ全探索が可能な場合もあります。
またこのような問題の場合、1000*1000で条件を満たす行列を作り、左上からN*N要素を出力するという考え方が有効な場合もあります。この考え方は場合分けをしなくてよく、大きさが固定されるので考えやすいです。
例題(AGC041-C) N*Nのマス目に1*2もしくは2*1のタイルを置く。各行,列に載っているタイルの数が同じになるような置き方を構築せよ。不可能ならその旨を示せ。
小規模な置き方をいくつか構築すれば、それらの和で大規模な置き方を作成することが可能な場合があります。例えば、4と5の和で表せない数字は1,2,3,6,7,11のみです。
練習(AGC027-D) どの要素も相異なるN*Nの行列で、取り出し方に関わらず、隣接した2つの数のうち、大きい方を小さい方で割った余りが一定になるようなものを構築せよ。
N=500の場合を構築できればどんなNでも問題ない場合が分かります。条件の言い換え(考え方1)をすることで、考察がしやすくなります。
小技/テクニック
ここでは、常に使えるわけではないが、たまに使える技法を紹介しようと思います。
①制約に注目する
制約が考察のサポートになることもあります。
例題(AGC022-B) 異なる正整数の集合で、どの要素についても、その要素とそれ以外の要素の総和が互いに素でない集合を特別な集合とする。要素数がNで全要素の最大公約数が1かつ全ての要素が30000以下である特別な集合を構築せよ。
制約を見ると「N≦20000」とあります。要素数が20000で30000以下の集合ということからmod3で考えてみると上手くいきます。
練習(AGC004-C) H*Wのグリッド上に連結な図形を2つ作り、両方の図形に含まれているマスを塗った。塗った結果が与えられるので、元の図形2つを構築せよ。
最も外側のマス目は塗られていないという情報から、最も外のマスを使った汎用性のある図形の構築法を考えるとよいかもしれません。
②構築が不可能という旨を出力してみる(あまりオススメしない)
Yes/No問題やゲーム問題でもありますが、構築が不可能という旨を出力して、どれだけACが返ってくるかで必ず構築できるか否かを判断するというテクニックがあります。
例題(AGC041-C) N*Nのマス目に1*2もしくは2*1のタイルを置く。各行,列に載っているタイルの数が同じになるような置き方を構築せよ。不可能ならその旨を示せ。
この問題では-1を出力するコードを提出すると、1つのテストケース以外WAが返ってくるので必ず構築できると考えることができます。(テストケースよりN=2なら構築不可能と分かるので)
ただし、コンテスト中にこれをするならある程度の順位や点数を確保してからやらないと悲惨なことになるので気を付けてください。(Unratedならともかく)
③マス目を斜めから見る
マス目において、縦横で構成される行/列を見るときに詰まったときは斜めにしたときに行や列を作ったりするとうまくいくことがあります。
これは構築以外でも役立ったりします。
おわりに
今回では構築問題に対して汎用性のあるテクニックを紹介しました。頻繁にでるジャンルではないからこそ例題や練習問題が難しめのになりがちで、初投稿でもあるので読みやすいかは不安ですが、みなさんのお役に立てたならば嬉しいです。
この下に練習問題のヒントも載せてありますので、詰まったけど解説は見たくないという状況ならぜひご活用ください。
練習問題のヒント
考え方1 条件の言い換え
練習(ABC165-E) 例えば10人いて、対戦場に1,3と書かれていれば、2数の差が2であるペアはそこで対戦します。なので、1,3と書かれている対戦場と2,4と書かれている対戦場があったら、条件を満たす割り当てとは言えません。
練習(AGC002-C) 2本のロープがあり、その長さがL以下なら、その結び目がほどかれることはありません。
練習(AGC006-B) A,A,Bという3つの数があったら、Bの数に関わらず中央値はAになります。
考え方2 場合分け
練習(AGC032-B) 例えばN=6なら、1は6以外と辺を結ぶ、2は5以外と...とすれば条件を満たします。
練習(AGC021-C) 2*3のマス目なら、2*2と2*1の合計と考え、2*1のタイルがあるならまず2*1のマス目に入れた方が場所を節約できそうです。
考え方3 小規模/大規模なものを考えてみる
練習(AGC027-D) あらかじめ小さい数にする部分と大きい数にする部分を分けたとき、大きい数を小さくするにはどうすればよいでしょうか。大きい数の回りに小さい数を置けば良さそうです。
小技/テクニック
練習(AGC004-C) 一番上の行は赤いマス、一番下の行は青いマスとすれば連結にしやすそうです。
