競技プログラミングをやってみよう！ (Part 2)

競技プログラミングをやってみよう！ (Part 2)
本記事は U-TOKYO AP Advent Calendar 2017 の 13 日目の記事です。

13 日目が誰も書かないようだったのでせっかくなので競プロ布教のため、 10 日目の記事の続きとして競技プログラミングを全く知らない人に向けて記事を書こうと思います。
具体的には競技プログラミングの基本的な問題を 4 問紹介します。
問題を考える際、計算機は 1 secあたり $10^7$ $\sim$ $10^8$ 回の計算ができると考えてください。
じっくり考えて分からなければ、最後の解答を見てください。

##問題A PachiCockroach
パチコ君は虫が苦手で、その中でもゴキブリ(cockroach) はとても嫌いです。
今、時刻 $i$ ($1 \le i \le T$) にパチコ君の部屋に $a_i$ 匹のゴキブリが入ってくることがわかっています。
パチコ君は最終的に時刻 $T$ に部屋にゴキブリが 1 匹もいないようにしたいと考え、そのために毎時刻に $K$ 匹までのゴキブリを倒すことにしました。(上限 $K$ は時刻に依存しない数です。)
各時刻のイベントの順番は " ゴキブリが来る $\to$ ゴキブリを倒す " の順番とします。
パチコ君は毎時刻に倒すゴキブリの数の上限 $K$ をできるだけ小さくして時刻 $T$ に部屋にゴキブリが 1 匹もいない状態にしたいと考えました。
そのような最小の $K$ はいくつか？

実行時間制限 2sec メモリ制限 256MB
####制約
　$T, a_i$ は整数
　$1 \leq T \leq 10^5$
　$1 \leq a_i \leq 10^{12}$

####入力
以下の形式で標準入力で与えられます。
　$T$
　$a_1　a_2　...　a_T $
####出力
最小の $K$ を出力してください。

####入力例1
8
4 8 7 2 5 6 8 1

####出力例1
6
時刻 $T$ 以外ではゴキブリが部屋に残っていてもかまいません。

####入力例2
5
9 4 7 3 8

####出力例2
8

####入力例3
25
66 77 13 49 90 45 72 33 67 35 56 21 61 13 16 71 8 27 26 39 11 28 91 56 47

####出力例3
65

問題B PachiCook

パチコ君は新しい趣味として料理(cook) を始めることにしました。
パチコ君は料理を作るには食材として大根が $K$ g 必要であることがわかり早速スーパーで $N$ cm の大根を 1 本買ってきました。
しかし、この大根は密度が均等でなく $i$ cm $\sim $ $i+1$ cm の間の重さが $w_i$ であることが分かりました。
パチコ君は大根が多すぎても困るので、この大根から連続する部分を 1 つ切り出してきてその重さを $K$ g 以上で最小の重さにしたいと思いました。
ただし、切れる場所は (整数) cm とし、まったく切らない場合(大根全体)もよいものとする。
最小の重さはいくつになるか？

実行時間制限 2sec メモリ制限 256MB
####制約
　$N,\ K,\ w_i$ は整数
　$1 \le N \le 10^5$
　$1 \le K \le 10^9$
　$1 \le w_i \le 10^4$ ($0 \le i \le N-1$)
　$w_0 + w_1 + ... + w_{N-1} \geq K $
####入力
以下の形式で標準入力で与えられます。
　$N$　$K$
　$w_0　w_1　...　w_{N-1} $ 　　　　　　　　　　　　　　`
####出力
最小の重さを出力してください。

####入力例1
8 16
4 8 7 2 5 6 8 1

####出力例1
17

####入力例2
5 15
9 4 7 3 8

####出力例2
18

####入力例3
25 483
57 84 54 37 97 17 76 12 61 67 51 73 14 94 26 53 2 22 30 48 47 55 49 8 54

####出力例3
488

##問題C PachiCountry
パチコ君はいろいろな国(country) を旅することが大好きです。
この世界には $N$ 個の国があり、時刻 0 にパチコ君は $s$ 番目の国にいます。
各時刻ごとにパチコ君は違う国に移動します。
ある時刻にパチコ君が国 $i$ にいるときに次の時刻に国 $j$ に行く確率は $p_{ij}$ であることがわかっています。
時刻 $T$ にパチコ君が国 $i$ ($1 \le i \le N$) にいる確率を出力してください。
ただし絶対誤差または相対誤差は$10^{-6}$までとする。

実行時間制限 2sec メモリ制限 256MB
####制約
　$ N,\ s,\ T $ は整数
　$ 1\leq N \leq 100 $
　$ 1\leq s \leq N $
　$ 0\leq T \leq 10^{9} $
　$ 0\leq p_{ij} \leq 1 $ ($1\leq i, j \leq N$)
　$p_{ii} = 0 $ ($1\leq i \leq N$)
　$p_{i1} + p_{i2} + ... + p_{iN} = 1 $ ($1\leq i \leq N$)

####入力
以下の形式で標準入力で与えられます.
　$N$　$s$　$T$
　$p_{11}　p_{12}　...　p_{1N} $
　 $\vdots$　　$\vdots$　　　　 $\vdots$
　$p_{N1}　p_{N2}　...　p_{NN} $ 　　　　　　　　　　　　　　`
####出力
パチコ君が国 $i$ にいる確率を出力してください。
####入力例1
5 1 5
0 0.25 0.25 0.25 0.25
0.25 0 0.25 0.25 0.25
0.25 0.25 0 0.25 0.25
0.25 0.25 0.25 0 0.25
0.25 0.25 0.25 0.25 0

####出力例1
0.19921875 0.20019531 0.20019531 0.20019531 0.20019531

####入力例2
5 3 10
0 1.0 0 0 0
0 0 1.0 0 0
0 0 0 1.0 0
0 0 0 0 1.0
1.0 0 0 0 0
####出力例2
0.00000000 0.00000000 1.00000000 0.00000000 0.00000000

####入力例3
5 1 1000000000
0 0.2 0.3 0.45 0.05
0.8 0 0.1 0 0.1
0.2 0.2 0 0.2 0.4
0.05 0.65 0.2 0 0.1
0.2 0.4 0.1 0.3 0

####出力例3
0.27202981 0.25832968 0.15767938 0.19041356 0.12154757

##問題D PachiCobue
パチコ君(Pachicobue) はゲームが大好きです。
今日も部屋でブエーステーション 4 のゲームを楽しくプレイしています。
気になったあなたはパチコくんにゲームの内容を聞いてみたところその内容は以下の通りでした。

• $N \times N$ の正方形の形にライトが並んでいます。
• ライトの状態は ON, OFF の 2 種類あります。
• あるマスのライトの ON, OFF を切り替えると、その上下左右のマスのライトも同時に ON, OFF が切り替わります。
  　(端のマスの場合は、上下左右のうち存在するマスのみ切り替わります。)
• 上の操作を繰り返してすべてのライトを ON にすればゲームクリアになります。

しかし、パチコ君は「どうすればいいか分からないぶえ〜」と困っていたのであなたは助けてあげることにしました。
現在の $N \times N$ にならんだライトの ON( 1 ) OFF( 0 ) の状態が与えられます。
そこからすべてのライトを ON の状態にするための最小の操作回数を答えてください。

実行時間制限 2sec メモリ制限 256MB
####制約
　$N, c_{ij}$ は整数
　$ 1 \leq N \leq 16$
　$ 0 \leq c_{ij} \leq 1$ ($1 \leq i, j \leq N$)

####入力
以下の形式で標準入力で与えられます.
　$N$
　$c_{11}　c_{12}　...　c_{1N} $
　 $\vdots$　　$\vdots$　　　　 $\vdots$
　$c_{N1}　c_{N2}　...　c_{NN} $
####出力
すべてのライトを ON の状態にするための最小の操作回数を答えてください。
もしどうやってもそのようにできない場合は "-1" を出力してください。

####入力例1
2
0 0
0 0

####出力例1
4

####入力例2
4
0 1 0 0
0 0 1 0
1 0 0 1
0 0 1 0

####出力例2
-1

####入力例3
16
0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0
0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 1
0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1
1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1
1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0
1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1
0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1
0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1
0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1
1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1

####出力例3
99

##終わりに
　今回の記事では, 競プロがどういう感じのものなのかを伝えようという気持ちで書きました. ジャッジやテストケース等は用意していません。
　実際の問題を見たほうがより良いと思うので, ぜひ実際に過去に出題された問題を解いてみたり, コンテストに参加してみたりして面白さを感じていただければ幸いです。
　くれぐれも学業に支障をきたさないように気をつけてほどほどに楽しんでください。

##解説
問題A
$a_i$ ($1 \le i \le T$)の最大値を $A$ とします。
ここで、$K=0$ では条件を満たさず、また $K=A$ では条件を満たすことはわかります。
愚直に計算すると各 $K$ について時刻 T にゴキブリを 0 匹にできるかできないかを判定して、できる場合の最小の $K$ を返すことになるので計算量は O($TA$) になり到底間に合いません。

この問題の重要なポイントは「毎時刻に $x$ 匹までゴキブリを倒して条件を満たせるなら,毎時刻に $x$ より大きな数 $y$ 匹までゴキブリを倒した場合は必ず条件を満たす」ということです。
このポイントから $(0 ,A]$ の範囲に 「$K=x-1$ では条件を満たさず、 $K=x$ では条件を満たす」 というような $x$ がただひとつ存在することが言えます。
そして、そのような $x$ が答えになります。

入力例 1 からこのような $x$ を "二分探索" という手法を用いて求める手順を説明します。

$A=8$ なので答えは $(0,8]$ の区間に含まれていることがわかります。
次に 0 と 8 の中間の値 4 が条件を満たすか調べます。
条件を満たすかどうかは各時刻について上限 4 回以内で倒せるだけ倒して時刻 $T$ にゴキブリが 0 匹となっているかどうかを判定します。( 1 回の判定にかかる計算量は O($n$) です。)
すると 4 は条件を満たさないことがわかるので答えは $(4,8]$ の中にあることがわかります。
同様にして次は 6 を調べると条件を満たすので答えは $(4,6]$ の中にある。
5 を調べると条件を満たさないので答えは $(5,6]$ の中にある。
よって答えは 6 となります。
答えの存在しうる区間は半分ずつ減少していくので判定回数 O($\log A$) になります。
ゆえに全体の計算量は O($N\log A$) で解くことができます。

問題B
愚直にすべての区間を調べると O($N^3$) もしくは O($N^2$) の計算量がかかってしまい間に合いません。
すべての区間を調べるのは調べる必要のない区間も調べてしまっているので無駄な計算を行っていると言えます。
例えば, $l$ cm $\sim$ $r$ cmの区間の重さが $K$ 以上である場合それより大きな区間については調べても意味がありません。( $K$ との重さの差が広がる一方なので)
この問題はしゃくとり法という手法を用いることで、O($N$)で解くことができます。

入力例 1 を用いてその手順を説明します。

まず初めに $[0,1)$ の区間を見ます。重さの合計は 4 で $K$ より小さいので区間を右に伸ばします。
次に $[0,2)$ の区間を見ます。重さの合計は 12 でまだ $K$ より小さいので区間を右に伸ばします。
次に $[0,3)$ の区間を見ます。重さの合計は 19 で $K$ 以上になったので答えの候補として 19 が考えられます。
この後区間を右に伸ばしても重さの合計が増える一方なので、左から区間を縮めます。
よって次は $[1,3)$ の区間を見ます。重さの合計は 15 で $K$ より小さいので区間を右に伸ばします。
$[1,4)$ の区間を見ます。重さの合計は 17 で $K$ 以上になったので答えの候補として 17 が考えられます。
以降このような操作を続けて、$[2,4) \to [2,5) \to [2,6) \to [3,6) \to [3,7) \to [4,7) \to [5,7) \to [5,8)$
と見ていき、最小となる答えを更新していくことで答えが 17 であることがわかります。
(答えを求めるには上に挙げた区間のみを調べれば十分であることが示せます。)

計算量ですが、右に伸びる or 左から縮めるという操作を O($n$) 回しか行っていません。(操作の際、区間の和は保持しておきます。)
よって全体で計算量は O($n$) で解くことができます。

問題C
マルコフ連鎖の問題です。マルコフ連鎖は計数っぽい？イメージがしたので選びました。
与えられている $p_{ij}$ は推移確率行列と呼ばれるものです。
$P = (p_{ij})$ とし、時刻 $k$ において国 $i$ にいる確率を $x_i^{(k)}$ と表すことにします。
また $x_i^{(k)}$ を $i$ について横に並べた $1 \times N$ ベクトルを $\mathbb{x}^{(k)}$とする。
このとき、

\mathbb{x}^{(k+1)} = \mathbb{x}^{(k)} P

と表すことができます。
また上式から、

\mathbb{x}^{(T)} = \mathbb{x}^{(0)} P^{T}

となることもわかります。( $T$ はトレースではなくべき乗を表しています。)
ここまでは競プロではなく確率の話なのであまり深くは述べません。

さて以上より、$N \times N$ 行列 $P$ の累乗を求めれば答えを求めることができるとわかりました。
しかし、愚直にすると計算量は O($N^3T$) で、 $T$ が最大 $10^{9}$ となので到底間に合いません。

ここで例えば行列 $A^{16}$ を速く計算する方法を説明します。

普通に計算すると 16 回行列のかけ算が必要ですが、
$A$ と $A$ を掛ける $\to$ $A^2$ が求まる
$A^2$ と $A^2$ を掛ける $\to$ $A^4$ が求まる
$A^4$ と $A^4$ を掛ける $\to$ $A^8$ が求まる
$A^8$ と $A^8$ を掛ける $\to$ $A^{16}$ が求まる
以上のようにすると 4 回のかけ算で求めることができます。
2 のべき乗以外でも例えば、 $A^{20}$ なら上と同じ計算を行ったあとに $A^{16}$ と $A^{4}$ をかけると求まります。
この手法は "べき乗高速化" と呼ばれる手法でかけ算の回数を $\log$ に落とすことができます。
漸化式の高速計算にも用いることができます。 ( $10^{18}$ 番目のフィボナッチ数を求めるときとか)
よってこの問題は O($N^3logT$) で解くことができます。

問題D
この問題はアルゴリズムというよりは"考察"、つまりこの問題の特徴をうまく見つけることが大切になります。
まず初めに基本の２つの特徴を説明します。

• ライトの ON, OFF を切り替えるという操作はどの順番で行っても結果は変わらないので順番を考慮する必要がない。
• ライトの ON OFF を 2 回以上行うことは意味がないので各ライトについて "ON, OFF を切り替える" もしくは "切り替えない" のどちらであるかを考えれば良い。

この特徴からすべてのライトについて ON, OFF を切り替えるか切り替えないかを考え、そして最終的にすべてのライトが 1 になっているかどうかを判定する O($N^22^{N^2}$) のアルゴリズムができました。

しかしこれでは到底間に合わないません。ですが、以下の方法を取ることで計算量を落とすことができます。

「それは一番上の行のすべてのライトについて ON, OFF を切り替えるか切り替えないかの組み合わせを全探索する」ということです。

一番上の行のすべてのライトについての操作を決めると一番上の行のライトの状態( ON, OFF ) が決定します。
その次に 2 番目の行について考えます。
上( 1 行目) のライトが 0 になっているような列にあるライトは必ず ON, OFF を切り替える操作をしなければいけません。(そうしないとすべてのライトが ON の状態にならないので)
同様に、上( 1 行目) のライトが 1 になっているような列にあるライトは必ず ON, OFF を切り替える操作をしてはいけないということもわかります。

つまり、一番上の行のライトについて ON, OFF を切り替えるか切り替えないかを考えれば、それ以降の行については行うべき操作が一意に決まるのです。

よって一番上の行のライトについて全通り試すことで、最小の操作回数がわかります。
ゆえにこの問題の計算量は O($N^22^N$) となり解くことができます。
これはライツアウトという実際にあるゲームで有名 ? なので知っている人もいるかも知れません。