2019-04-20

AOJ 2885 - 分割統治

解法

まず、問題の条件を満たすようなパターンについて整理します。1つめのサンプルを見てみると、例えば下のようなパターンがあり得ます。

f:id:emtubasa:20190419233339p:plain

青が太郎、黄色が次郎、緑が花子さんの統治している国になります。
結局のところ、

太郎君(花子さん)が統治している街に隣接している全ての街は、次郎君が統治している
次郎君が統治している街に隣接している全ての街は、太郎君(花子さん)が統治している

ということで、二部グラフです。
最終的にやることは、2つの頂点集合の個数を調べ、それぞれ、頂点の個数が偶数だった場合に、その半分が答えになります。
そもそも二部グラフになっていなければ、答えは存在しません。
頂点の個数がどちらも偶数だった場合は、その個数がどちらも同じであった場合は $K = 1$ で答えを出力し、異なっていたならば、 $K=2$ で、昇順に答えを出力すればよいです。
二部グラフの頂点の個数は、始点となる頂点を1つ決め、そこからBFSをして、始点からの距離の偶奇を見ればよいです。

感想

あまりICPCっぽくない気がしました(経験があまりないのでなんとも言えませんが)。
今回は、問題の条件を整理した時点で方針がパッと見えたので、すんなり解けました。とりあえず図におこしてみるとわかりやすいですね。

2019-04-18

AOJ 2825 - クイズ

未分類

問題
 提出コード

解法

最終問に必要な得点が最大になるとき、 $N$ の中で少なくとも1人は、その人が答えることができる問題に全て答えています。
同様に、少なくとも1人は、その人しか答えられない問題以外は全て答えられません。
ということで、それぞれの人について、全ての問題に答えたパターンの総得点、そして自分しか答えることができない問題のみに答えたパターンの総得点を計算し、それぞれのパターンについて、前者は降順、後者は昇順でソートをします。
そして、

ソートしたそれぞれの先頭の差+1

が答えになります。

しかし、ソートしたそれぞれの結果が、同じ人についての計算結果だった場合については別処理が必要です。例えば

のような入力例だと、最低点は3人目の0、最高点も3人目で2000となります。
このようなパターンでは、ソートした配列の前から2つをみて、最高点の1番目と最低点の2番目、最高点の2番目と最低点の1番目の差のうち大きい方を選んで、1加算したものが答えになります。

感想

この手の問題をバグなくさらっと解けるのはいいですね。
今回は貪欲が正しい確証をもって通したのでよかったと思います。
典型問題は基本このペースで通していきたいと思います。

2019-04-17

AOJ 2153 Mirror Cave

幅優先探索(BFS)

問題
 提出コード

解法

普段のグリッドに対するBFSが2次元ならば、今回は4次元です。
Len君が $(x_{L},y_{L})$ 、Ren君が $(x_{R},y_{R})$ にいるときに、そこから行くことができる4通りの方向に進みます。
そして、 $(x_{L},y_{L}),(x_{R},y_{R})$ に行くことができるかどうかを調べていき、それぞれがゴールのマスに同時にたどり着くならば、答えは"Yes"、そうでなければ"No"になります。
そして、ある方向に進むとき、進んだ先が壁"#"になっている、もしくは迷路の外に出てしまう場合、その場にとどまるような処理を入れ忘れないようにします。あとは、基本的なBFSと同じような処理をしていけば、答えを求めることができます。

解法

この手の問題をサクっと解けるようになりたいですね(って毎回言ってる気がしますが…)。
やりたいことはすぐわかる問題で、BFSをする問題はだいたいバグを生やしているイメージなのでなんとかしたいです。昔よりは綺麗に書くようになったので多少は減ったのですが、今回のように次元が増えるとまた汚くなりますね。

2019-04-16

AOJ 2021 - お姫様の危機

ワーシャル-フロイド法ダイクストラ法

問題
 提出コード

解法

町の数が少ないので、まずは任意の2つの町を結ぶ最短経路を求めます。これは、ワーシャルフロイドを利用すれば簡単に求めることができます。
あとは、スタート地点から、今いる地点から $M$ 分以内で行ける、冷凍施設のある町のみを経由してゴールの町まで行くことができるかどうか、そしてその場合の最短経路を調べます。これは、ダイクストラ法を利用することで求めることができます。このとき求まった最短経路を $D$ とします。
最後に、途中で冷凍する時間を追加してあげます。
最初の町にいる時点では、 $M$ 分間冷やさなくても大丈夫です。また、
$D \geqq M$ の場合は、目的地に着いた時点で、ちょうど残り時間が0になるようにするのが最適です。
これらを踏まえると、結局は
$D + max(0,D - M)$
が求める答えになります。

感想

ワーシャルフロイドとダイクストラを組み合わせる系問題でした(ダイクストラは2回目のワーシャルフロイドでも問題ない気もします)。この手の問題の考察をぱぱぱーっと解くことができると、昔よりは強くなったな、という気分になれます。
制約と、最短距離を求めたい雰囲気が出ている時点で、これらの手法が使いたくなりますね。

2019-04-16

AOJ 2002 - X-Ray Screening System

順列(next_permutation) 実装系

問題
 解法

解法

まずは、それぞれの文字が、隠れている部分を含めて長方形になり得るかを調べます。そして、その後で、重なっている部分が矛盾していないかどうかのチェックをします。

ということで、まずは長方形になりうるかどうかのチェックをします。いま、文字 $S$ について調べているとするとき、まずはすべてのマスの中で、文字 $S$ が存在する、上端、下端、左端、右端を洗い出します(それぞれ $u,d,l,r$ とします)。
その後、 $(u,l),(u,r),(d,l),(d,r)$ の4つのマス目で結ばれた長方形のマス目全てについて、.かどうかを調べます。もし、.が存在していたら、その時点で $S$ の品物が長方形になることはないので、答えは"SUSPICIOUS"です。
また、この時に、 $S$ 以外の文字 $X$ が存在していたら、その $X$ の品物は、 $S$ よりも $X$ 座標が近いことになります。これをメモしておきます。

続いて、重なっている部分の矛盾を洗い出します。
サンプルケースの4つめのように、 $A$ は $B$ より手前、 $B$ は $C$ より手前、 $C$ は $D$ より手前、 $D$ は $A$ より手前に存在していなければならず、これらを全て同時に満たすことはないので、このケースは"SUSPICIOUS"になります。このようなパターンを探し出します。
まず、品物は最大で7種類なので、その7種類について、手前からどのようにならんでいるか、のパターンを全て探索するには、 $7!$ パターン探す必要があります。そして、どの文字の品物が、どの文字の品物よりも手前に存在しているべきか、というのは、先ほどのメモを利用すれば $O(1)$ で調べることができます。
よって、全ての順列に対し、任意の2つの文字について、x座標で矛盾が生じていないかどうかを調べるのは、おおよそ $7! \times \ _{7}C_{2}$ 回ほど計算すればよく、これは十分高速です。
ということで、next_permutationを利用しつつ、矛盾がないような順列が存在するかどうかを調べ、1つでも存在していれば答えは"SAFE"、していなければ答えは"SUSPICIOUS"になります。

感想

サンプル4のコーナーケースが、はじめは何故"SUSPICIOUS"なのかを理解するのに時間がかかりましたが、やるべきこと自体はすぐに思いつくことができ、バグも少なかったので良かったかと思います。

2019-04-14

ABC124 D - Handstand

しゃくとり法

問題
 提出コード(1)
提出コード(2)

解法

1...(または0...)が連続しているとき、連続している部分は1つにまとめてしまいたいので、ランレングス圧縮のように、連続して何個続いているか、という情報に置き換えておきます。
今回の問題の場合、0...が続いている区間を $K$ 個以下1...に反転して、作成できる最大の1...の区間を求めればよいです。
0...1...0..のような区間を反転させても、結局そこを利用しつつ最適解にするには、初期の時点で1...であった部分をもう一度反転する必要があり、結局反転が必要な回数は変わりません(0...1...0...1...0...のように、入れ替わりの個数が増えても、結局は同じことです)。
ということで、1...0...の区間を連続で $K$ 個とり、その区間、そしてその右にある1...の区間を合わせた長さを求め、この長さの最大値を求めていけば、答えになります。
これは、しゃくとり法のように、左端と右端をやり取りしていけば、 $O(|N|)$ で求めることができます。
実装時は、もし入力された文字列が0...1...0...のように、両端が0で終わるパターンでも、'1'が0個つながった区間が存在すると仮定すると、端の処理でバグることが少なくなります。
と先輩がツイートをしていました。

Dは端が0の時は、1が0個あると思うと楽
— 鍋食べたいbot (@__imulan__) 2019年4月13日

この処理をしたのが提出コード(2)になります。(1)はとくに何もしてないです。
この処理をすることによって、1...0...を問答無用で1つのセットとみなすことができます。
あとは、いつもの尺取り法のように、区間の両端 $l,r$ を用意して、0...の区間の個数が $K$ 個になるように、 $r$ を増やして区間を広げたり、 $l$ を増やして区間を狭めたりして、答えとなる区間の長さを求めていけば良いです。

感想

尺取り法はいつも雰囲気で書いているので、forを使ったりwhileを使ったりとパターンがバラバラになっていて、少し実装に時間がかかっているイメージがあります。
統一すると、テンプレ化できてスピードがはやくなったりするのでしょうか。
解法は、まず、この問題っぽいなぁと思ったのですが、特に関係してなさそうなので、最善手をひたすら考えました。

2019-04-13

AOJ 2741 - インビジブル

動的計画法(DP) メモ化再帰

問題
 提出コード

解法

ゲーム系で、ぱっと貪欲な解法がなさそうだったので、メモ化再帰をすることにしました。6次元DPです。
$dp[i][j][k][l][p][q]$ とし、それぞれの添え字が
$i:$ 先手が次にスタックにカードを置くとき上から何枚目のカードを置くか
$j:$ 後手が次にスタックにカードを置くとき上から何枚目のカードを置くか
$k:$ 次にパスが行われたとき、先手は直近で出した何枚分のカードが得点になるか
$l:$ 次にパスが行われたとき、後手は直近で出した何枚分のカードが得点になるか
$p:$ 次のターンはどちらか(0なら先手、1なら後手)
$q:$ 直前のターンまでで何回連続でパスをしたか
の状態のときに、これ以降のゲームで得られる得点の値とします。
$p = 0$ ならば、これ以降の遷移の中で値が最大のもの、 $p=1$ ならば、これ以降の遷移の中で値が最小のものをその時点での値にすればよいです。
初期値は、スタックが空の状態で、2連続パスが行われた場合にゲーム終了なので、
$dp[i][j][k][l][p][3] = 0$
としておけばよいです。スタックが空じゃない状態からパスを連続で行うことになるので、 $q=3$ になります。
また、 $a_{i} , b_{j}$ は0-indexedになおしておきます。

$p=0$ のとき
先手のターンです。まず、スタックにカードを置くパターンから考えていきます。
このパターンを考慮するのは、 $i$ が $n$ を超えていない、つまり山札がまだ存在している場合のみです。
もし、次に出すカードが妨害カード、つまり $a_{i}=-1$ の場合は、それ以降で次にパスした場合に後手が手に入れることができる得点は、今出した妨害カード以降の得点カードになります。よって、 $l=0$ になります。
よって、この行動による遷移先は、
$dp[i+1][j][k+1][0][1][0]$
となります。
もし、得点カードだった場合は、相手の得られる得点に変動はないので、
$dp[i+1][j][k+1][l][1][0]$
となります。
次に、パスするパターンです。
まず、スタックが空になるので、見るべき遷移先は、
$dp[i][j][0][0][1][q+1]$
となります。
加えて、 $(直近k枚の先手のカードによる得点) - (直近l枚の後手のカードによる得点)$
が加算されます。
この合計と、最初の2パターンのうちの片方(先手の山札が切れていたら存在しません)のうち、より大きい方が $dp[i][j][k][l][p][q]$ の最終的な得点になります。

$p=1$ のとき
後手のターンです。先ほどとほぼ同様なので、遷移先だけ書くと、
$b_{j} = -1$ のとき
$dp[i][j+1][0][l+1][0][0]$
$b_{j} \neq -1$ のとき
$dp[i][j+1][k][l+1][0][0]$
パスするとき
$dp[i][j][0][0][0][q+1]$
このパターンは、先ほどと同様 $(直近k枚の先手のカードによる得点) - (直近l枚の後手のカードによる得点)$ が加算されます。
こちらも、これらの中で最小値を求めると、 $dp[i][j][k][l][p][q]$ の値になります。

これらを利用して計算していき、 $dp[0][0][0][0][0][1]$ を求めれば答えになります。

感想

考察自体は結構はやかったのですが、例によってバグらせました。
この手の問題はよく見かけるので、パパっと解きたいところです。