情画プロコン#1 解説

サービス券
フィルタ
整理整頓
部分回文

各問題のねらい

Lv.1 サービス券

入出力処理
繰り返し構文
シミュレーションを行う

Lv.2 フィルタ

シミュレーションを行う
配列を使う。ソートを行う
メディアンフィルタの原理の理解

Lv.3 整理整頓

深さ優先探索
スタック、再帰
ビット演算

Lv.4 部分回文

状態を頂点、状態の遷移を辺としたグラフを作る
動的計画法

Lv.1 サービス券

入出力処理と、基本的な繰り返し処理を問う問題です。

持っているサービス券を出来るだけ使ったほうが良いのは自明ですね。
アルゴリズムとしては、できるだけサービス券を使った時に、行けるイベントの数を数えるという処理を書きます。
\(N\), \(M\)から直接答えを導き出す数式を建てるのは難しいので、処理をシミュレーションしましょう。

具体的には、

最初のサービス券の数\(N\)を現在のサービス券の数を表す変数xに代入する。また、答えを表す変数ansを0で初期化する。
x >= Mである間、xから\(M\)を引き、xに1を足し、ansに1を足す。（イベントに1回参加し、サービス券がM - 1枚減ったことを表す）
最終的なansが答え。

とします。これでも正解ですが、もう少し効率よく計算することができます。
サービス券がx枚あるとき、x / \(M\)回だけイベントに参加できて、サービス券の数は x / \(M\) + x % \(M\) となります。
（x % M枚手元に残り、x / \(M\)枚補充されるから。/は切り捨てです。また、%は剰余を表す記号です。）

最初のサービス券の数Nを現在のサービス券の数を表す変数xに代入する。また、答えを表す変数ansを0で初期化する。
x >= \(M\)である間、ans = ans + x / \(M\) として、　x = x / \(M\) + x % \(M\)とする。
最終的なansが答え。

こちらのほうが繰り返しの数が少なくて済みます。

また、再帰関数を使った方法もあります。
現在のサービス券の数がN、1回のイベントに参加するときに必要なサービス券の枚数がMのときの答えを
function(n, m)とすると、function(n, m)は以下の漸化式で表すことができます。

function(n, m) :=
- n < m なら 0
- それ以外なら n / m + function(n / m + n % m, m)

function(\(N\), \(M\))を呼んで帰ってきた値がそのまま答えとなります。

計算量は、

1個目の方法が\(\mathcal{O}(\frac{N}{M})\)
2個目、3個目の方法が\(\mathcal{O}(\log_M N)\)

となります。0≦N≦1000、2≦M≦1000なので、
今回の場合はどの方法を使ったとしても時間内にプログラムの実行を完了させることができます。

Lv.2 フィルタ

配列を使う問題です。

問題文のとおりに処理をシミュレートします。
アルゴリズムが書いてあるので、こちらのほうがLv.1の問題より易しいかもしれません。

基本的には問題文通り記述していきますが、中央値を求めるところで意外と苦戦します。

1つの方法としては、if文で丁寧に1つずつ見ていく方法があります。こちらは簡単にかけますが、要素が増えると難しくなっていきます。

また、A[i - 1]、A[i]、A[i + 1]を要素とする新たな配列Cを作り、
Cをソートして、Cの2番目の要素の値をmとする、という方法があります。
（もちろん、Cの要素が2つしかないときはその平均をmとしてください。）
こちらの方法は、中央値を取る対象の要素が増えた時にも対応できるという利点があります。

ここの処理を書くことができれば、答えを出力するのは簡単でしょう。

さて、題名にフィルタとありますが、このような処理（周りの要素の中央値をとる）を施すフィルタを「メディアンフィルタ」と呼びます。
このフィルタはとびぬけておかしい値（ノイズデータ）をいい感じに取り去ることができます。
最後の入力セット（3つ目の入力）がその場合に対応しています。

入力3

12
10 20 30 255 50 60 70 80 90 255 110 120

出力3

15 20 30 50 60 60 70 80 90 110 120 115

この処理を2次元に拡張することができます。
2次元に拡張すると、画像に対してメディアンフィルタをかけることができます。
アルゴリズムは、周りの8近傍のピクセルと自分自身の合わせて9個のピクセルの中央値を取る、という点を除いて変わりません。
(もう一回り大きく、自分自身を含めて25個のピクセルの中央値を取ったりすることもあります)
このようにすると、画像の大体の情報を残したまま、ノイズを除去することができます。

Lv.3 整理整頓

制約より、\(N\)が小さいので、すべてのブロックに対して、領域Aに置くか領域Bに置くかを試すことができます。
組み合わせは\(2^N\)通りとなります。
このすべての通りの中に、横の長さの合計が領域A, Bともに\(X\)以下になっているものが1つでもあれば"possible"となります。
1つもなければ"impossible"です。

すべての組み合わせを試すには、「深さ優先探索」（DFS; Depth First Search）を行います。

上図のような木を考えます。
この木を根（茶色の頂点）から深さ優先探索します。探索の途中で、葉（一番末尾の緑の頂点）を訪れた時、
「根からその葉への経路（辺のラベルの並び）」が、「各ブロックをどちらの領域においたのか」に対応します。
よって、葉に訪れるごとに、その時の並びで領域Aと領域Bの長さを計算し、どちらも\(X\)に収まっているかを計算すれば良いことがわかります。

このような探索を書くときの基本は再帰関数とスタックです。
新しい頂点に訪れるたびに、スタックにその時使った辺の情報をプッシュ（末尾に追加）し、
頂点から戻るときはその頂点を訪れるために使った辺をポップ（末尾から削除）します。
ある頂点を訪れるという処理を関数dfsに定義すると、dfsの内容は

もし頂点が葉なら、スタックの情報を使って"possible"か"impossible"かを計算する。
もしまだ訪れていない頂点があれば、その頂点に対してdfsを呼ぶ
- 呼ぶ前に、その時使う辺をスタックにプッシュ
- 呼び終わったら、スタックからポップ

となります。
このように頂点を「状態」、辺を「選択」とした木はよく出てきます。

この方法で探索を行った場合、計算量は\(\mathcal{O}(N2^N)\)となります。

あるいは、スタックを使わずにもっとシンプルに深さ優先探索を行うこともできます。ブロックの第n個目まで考慮した時、領域Aに置いたブロックの横の長さの和がsumとなるかどうか（なるならtrue、ならないならfalse）を dfs(n, sum)と置き、ブロックの長さの合計をS（これは事前に計算しておく）とします。すると

dfs(n, sum) :=
- n == \(N + 1\) なら
  - sum <= X かつ　S - sum <= X ならture
  - そうでないならfalse
- それ以外なら dfs(n + 1, sum + \(L_n\)) or dfs(n + 1, sum) を返す

or は2項演算子で、左と右のオペランドがどちらもfalseならfalse、それ以外ならtrueを演算します。

さて、これでも正解なのですが、このような再帰のプログラムを書くのは若干めんどくさいです。
今回のように全ての○○に対して、2択を行った場合を全列挙する、というシチュエーションはよく出てきます。
これを比較的簡単に書くことができる方法があるので紹介します。（ただし2択に限ります。）

まず、ある整数iを0から\(2^N - 1\)までインクリメント（1ずつ足す）して行きます。
このときのiのビット列に注目しましょう。

(例：\(N = 4\)の場合)

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

このビット列の1を「1つの選択」、0を「もう一つの選択」に割り当てることで、簡単に\(2^N\)通りの場合の列挙が完了します。
j番目の要素がどちらの選択であるかは、jbit目が1であるかどうかを調べれば良いので、

for(int i = 0; i < 1 << N; i++) {
    //このときのiのビット列がそのまま全列挙になっている。

    for(int j = 0; j < N; j++) { //0bit目からN-1ビット目まで順番に調べる
        if (i >> j & 1) {
            //j番目の選択で「1」を選択した場合にしたいこと
        }　else {
            //j番目の選択で「0」を選択した場合にしたいこと
        }
    }
}

とすれば全探索を簡単に行うことができます。今回のしたいことは、ブロックの長さの合計を求めることなので、
何らかの合計保持用に変数を用意して、「1」を選択した場合、それにj番目のブロックの長さを足していけばよいでしょう。
（反対側も同様に計算します。）
「1」を選択した場合を領域Aに割り当てるか、領域Bに割り当てるかは自由ですが、一度決めたら変更しないようにしましょう。
こちらの手法を使った場合も計算量は\(\mathcal{O}(N2^N)\)となります。

さらに、Lv.4で紹介する手法「動的計画法」を使用すると、\(\mathcal{O}(NX)\)のプログラムも書くことができます。
(「i個目まで考慮した時、領域Aに入るブロックの長さの合計がjとなるか」をdp[i][j]と置く。（なるとき1、ならないとき0）)

先ほどの「スタックを使わない再帰」の解答で、同じ引数に対する返り値は常に一定なので、
「その引数に対する答え」を一度計算したらstaticな配列に記憶させておき、2回目以降はその配列の値を返すだけ（再帰しない）
というプログラムを書くと、その計算量は引数に対する回数しか計算しないので、\(\mathcal{O}(NX)\)となります。
この解法は「動的計画法」の解答と本質的に同じです。
このように、再帰関数において、引数に対する返り値を配列に記憶させておき、
2回目以降の計算を配列の値で代用するアルゴリズムを「メモ化再帰」といいます。
一般に、「動的計画法」と「メモ化再帰」は互いに書き換えられることが多いので覚えておきましょう。

誤解法について

ソートして大きい/小さい順に領域Aに入れる。領域Aに入らなかったら領域Bに入れる。領域Aにも領域Bにも入らないブロックができたら"impossible"、そうでなければ"possible"

この解法は例えば次の入力の時に正しい答えを返しません。

入力例

11 33
2 2 2 4 5 6 7 8 9 10 11

出力（誤）

impossible

本来は、"possible"となるべきです。なぜなら、領域Aに6m、8m、9m、10mのブロック、領域Bにそれ以外のブロックを詰めることでピッタリ収めることができるからです。
しかし、このような解答を予想していなかったため、このアルゴリズムを誤りと判定できるテストケースを用意していませんでした。
なので、このような解答を送信しても、仕様上満点がもらえます。
申し訳ございません。

Lv.4 部分回文

まずは、「\(S\)が部分回文であるかを効率的に判定する方法」を考えましょう。
「全ての\(S\)の部分文字列のうち、一つでも回文が存在したら\(S\)は部分回文」というアルゴリズムは、
正しいですが、実装がそこそこ面倒で、判定に\(\mathcal{O}(|S|^3)\)の時間がかかってしまいます。

S[i]を\(S\)のi番目(\(0≦i≦|S|-1\))の文字とすると、以下の事実が成り立ちます。

i≧1を満たす全てのiの中で一つでもS[i] = S[i - 1]を満たすiがあったら、\(S\)は部分回文　…(条件1)
i≧2を満たす全てのiの中で一つでもS[i] = S[i - 2]を満たすiがあったら、\(S\)は部分回文　…(条件2)
(条件1)と(条件2)共に該当しない場合、\(S\)は部分回文ではない

証明は帰納法によって行われます。n = \(|S|\)とすると、

n = 1 のとき、一文字の文字列なので、部分回文ではない。
n = 2 のときとn = 3 のとき、自明である。
n = k のとき、上記の判定法が成り立つとすると、
1. n = k + 1 のとき、\(S\)の中にある部分回文は「末尾の文字を追加したことによってできる」ものと「そうではない」ものに別れる。
  1. 末尾の文字を追加したことによってできる」ものについては、
    1. 末尾の文字を追加する前は部分回文でないものが末尾の文字を追加することによって部分回文になる。
    2. よって2文字、または、3文字の部分回文が末尾の文字によって生成される場合を考えれば十分。(4文字以上の部分回文は1文字取り除いても残った文字列に部分回文が含まれる)
    3. したがって、末尾を含む部分が(条件1)か(条件2)を満たすかどうかを判定すれば必要十分である。
  2. 「そうではない」ものはn <= kのときの判定で分かるため、n = k のときの仮定より上記の判定法で判定できる。
2. よって、n = k + 1 のときも、上記の判定法が成り立つ
以上より、上記の判定法は正しい

この判定法を使うと、一回だけiをループさせればいいため、O(\(|S|\))で判定することができます。

しかし、これだけでは十分ではありません。
この問題は、\(S\)が部分回文であるかどうかを判定する問題ではなく、
部分回文でない文字列が何通り作れるかを求める問題だからです。

さて、何通りあるかを調べるために、*となっているところ全てに、1～9の数字を入れて\(S\)を作り、
先ほどの判定法で\(S\)が部分回文であるかどうかを判定して、部分回文でないと判定された数を数える、というアルゴリズムを考えたとします。
このアルゴリズムは、Lv. 3の問題と同様に深さ優先探索を使用して実装することができますが、*の数は最大で\(|S'|\)あるため、
判定も含めると全体で、\(\mathcal{O}(|S'|9^{|S'|})\)の時間がかかってしまいます。
\(|S'|\)は最大で1000なので、どうやっても計算を終わらせることはできません。

ここで次のような3次元のグラフを考えます。　　

graph1

座標(i, j, k)にある頂点は「全体のk文字目まで数字を埋めていったときに、k文字目がj、k - 1文字目がiである状態」を表します。
(このような「状態」を考えたのは、先ほどの判定法から、1個前と2個前に選んだ数字さえわかれば、
それより前に選んだ数字は今後選べる数字に影響を与えることはない、というマルコフ性から来ています。)
状態から状態の遷移を辺で表しますが、今回は部分文字列でない文字列の数を数えたいので、
先ほどの判定法から次のような辺を作ればよいと分かります。ただし、遷移先のjをj'とします。また、遷移先のiをi'とすると、i'=jです。

「j'≠j かつ j'≠i であり、しかもS[k]が*であるか、S[k]とj'が等しい」を満たすj'について、(i, j, k)と(i' = j, j', k + 1)間の辺を作る。

「j'≠j かつ j'≠i」は、1つ前と2つ前に選んだ数字は次に選ぶことはできない、ということを表します。
「S[k]が*であるか、S[k]とj'が等しい」は、
S[k]が*ならどんな数字でも入れられて、数字が指定されていたら、その数字しか選ぶことができないことを表します。

このような条件を満たすj'について、(i, j, k)と(i' = j, j', k + 1)の頂点間を結びます。
ただし、k = 0のときは、前に選んだ数字が定まらないので、絶対に選ばれない数字である0を使い、特別にi = 0とします。

i = 2, j = 1, k = k'の頂点から他の頂点に向かう辺を下に示します。
黄色の頂点から、緑の頂点の向きへ辺が結ばれます。

graph4

(S[k' + 1] = *のときのグラフ。(2, 1, k')の頂点からは、(1, 3～9, k' + 1)の頂点に向けて辺が結ばれる。)

graph5

(S[k' + 1] = 3のときのグラフ。(2, 1, k')の頂点からは、(1, 3 k' + 1)の頂点のみに向けて辺が結ばれる。)

さて、このように状態を頂点で表し、その遷移を有向辺（向きのある辺。弧とも言う）で表したグラフができました。
この時、「ある状態からある状態に遷移する場合の数は何通りか」を効率的に求める方法を考えましょう。

有名な問題で、「格子状の道路からなる街があり、東か北かにしか進めない時、
一番南西の交差点から一番北東の交差点に移動する手段は何通りか」という物があります。
この問題は、何らかの座標を交差点に振り、その座標に到達する行き方は何通りあるかを記録していくことで解くことができます。

graph2

この図をグラフとして考えてみましょう。
交差点を頂点として考えると、頂点は「座標(i, j)に居る状態」を表し、
辺は「東か北のみに進める」（状態を(i, j)から(i + 1, j)か(i, j + 1)にしか変化させることはできない）ことを表しています。
すると、ある頂点への遷移の場合の数は、調べたい頂点につながっている遷移前の頂点の値を全て足したものとなります。

graph3

この性質を今回も利用するわけですが、利用するには、調べる順番が重要です。
上図を見て分かるように、ある頂点への行き方の場合の数を調べるときは、
その頂点に遷移する前の頂点全てが調査済みでなければなりません。
このような調査の順番を求めることを「トポロジカルソート」といいます。
トポロジカルソートによって得られる順番は１つとは限りません。

今回のグラフは、k = k'の頂点はk = k' + 1の頂点にしかつながらないので、閉路の無い有向グラフとなっています。
このようなグラフをDAG(Directed Acyclic Graph)といい、DAGは必ずトポロジカルソートすることができます。
今回のグラフは、「kの昇順」がトポロジカルソートによって得られる順番の一つです。
kの昇順ならプログラムに組み込みやすいので、これを使いましょう。

この方法は、O(状態(頂点)の数 * 1つの頂点に対する処理)の計算量がかかります。
今回の場合は頂点が最大で10 * 10 * 1000、一つの頂点に対して、最大9個の遷移先の頂点を見るので、
\(\mathcal{O}(10 * 10 * 9 * |S'|)\)程度の時間がかかります。選べる数字の種類を\(K\)とすると、\(\mathcal{O}(K^3 |S'|)\)程度です。
10 * 10 * 9 * 1000 = 900000なので、これなら制限時間内にプログラムを実行することができます。

このように、部分問題の答えからもう一つ大きなサイズの問題の答えを、
それまでの答えのメモを利用しながら求めていくアルゴリズムを「動的計画法」(DP; Dynamic Programming)といいます。
動的計画法の問題を考えるときは、状態を頂点、状態の遷移を有向辺としたDAGを考え、
トポロジカルソートの順番で頂点を調べていくとうまくいきます。
求めるものとしては、場合の数や最小、最大があります。最小、最大は、その頂点（＝状態）での最適解を頂点に記録していけばOKです。

状態として何をとるかは難しいですが、おおむね

「何個目まで考えたか」
「合計は何であるか」
「操作の回数は何回であるか」
「座標はどこか」
「考えている範囲の端はどこか」
「マルコフ性を決定する状態」

辺りを考えると良いです。今回は、「何個目まで考えたか」「マルコフ性を決定する状態」などから状態を考えました。

まとめると、以下の様なアルゴリズムで答えを導き出すことができます。ここで、dpという名前はDynamic Programmingから来ています。

配列dp[i][j][k]を用意し、すべて0で初期化する。(0≦i≦9, 0≦j≦9, 0≦k≦1000)
dp[0][b][0](1≦b≦9)は1とする。ただし、S[0]が数字で、b≠S[0]の場合はdp[0][b][0]は0にする
k = 0 から k = \(|S'|\) - 1まで以下を繰り返す。
1. 全てのa, b(0≦a≦9, 1≦b≦9)について、以下を繰り返す
  1. 全てのc(1≦c≦9)について、以下を繰り返す。
    1. aがcと等しい、またはbがcと等しい場合は、次のcを調べる。
    2. dp[b][c][k + 1]にdp[a][b][k]を足す。ただし、S[k + 1]が数字で、c≠S[k + 1]のときは足さない。
    3. この時、dp[b][c][k + 1]が1000000007以上になったら、dp[b][c][k + 1]は1000000007で割った余りにする。
全てのa, b(0≦a≦9, 1≦b≦9)について、dp[a][b][\(|S'|\) - 1]の合計を算出する。この合計が答え。
1. ただし、合計が1000000007以上になったら、合計は1000000007で割った余りとする。

このアルゴリズムで、a, bは現在調べている頂点のi, jを表していて、cはj'を表しています。
また、足し算を行うごとに余りをとらないと簡単にオーバーフローするので注意してください。

しかし、0≦k≦1000の範囲の配列をとるのは無駄が多いです。
k = k'の頂点はk = k' + 1の頂点にしかつながっていないことを利用して、dp[10][10][2]の配列を用意し、
領域を再利用しながら動的計画法を行う方法もあります。
しかし、一応全ての要素をint型（4byte）でとったとしても、10 * 10 * 1000 * 4 = 400000byte = 400kbyteなので
メモリ制限には引っかかりません。
提出スピードが重視されるコンテスト等で動的計画法を使うときは、メモリがあふれないかを確認して、
あふれそうなときのみ改良を行うのがよいでしょう。

また、この問題でも、「動的計画法」と「メモ化再帰」は互いに書き換え可能です。
どちらかが書けたら、もう一つのほうも書いてみると理解が深まると思います。
（動的計画法からメモ化再帰に変換するポイント：グラフの形がそのまま再帰呼び出しの形になる。）