07/

README

日本情報オリンピック過去問 難易度6まとめ

Last Change: 2020-11-22 17:18:29.

B. お菓子の分割 ★★★

わからなくて解説を読んだのにオリジナルの実装で非常に苦労した。

DPでやりたいなぁと思いつつ、遷移はおぼろげながらイメージが付いても状態の持ち方がわからず、解答を漁った。

kutimotiさんのブログが参考になったが、微妙に実装はオリジナルに変えた。

「1つ1つ区切られたお菓子を片方の人に配り続け、コストを支払うことでもう片方の人へ分配をチェンジできる」 と問題文を読み替えることが最重要。 そうすると、「以前どこで切ったのか？」というような情報を持たずに済む。

「ステートレスに考える」 とも捉えられそう、な気もするし、そういう言い方は不適切な気もする。

結局、自分の場合 [M][M][Y][Y][M]... のようにブロックを分けるように考えて、 dp[i][j][M or Y] := i番目まで観たとき、自分がj個お菓子を獲得しているときの、コストの最小値 として考えた。

ただし、初期化と遷移が微妙に難しい。 コストを考えるポイントはお菓子に相当するブロックではなく、ブロック間の「仕切り部分」であることから、慎重に進めなければならない。

B. IOI列車で行こう ★★★★★

DPの発想すらできなかったので完敗だった。
「とりあえず考えられる並びを全探索して、そこで出来上がる部分文字列で最大のものを取ろう」というのがベースの考え方。
なので、弱い制約では愚直な全探索ができるし、中程度の制約では値がbool値の「（やや）自明なDP」が通るようになっている。

満点回答は dp[i][j][flag] := Sからi文字分, Tからj文字分とって作る文字列の最大長、ただしフラグによって末尾が変わる というような状態を考えることで計算できる。
これはLCSのような貰うDPを考えるのが簡単だが、なんか初期化方法がよくわからなくて無理やり配るDPを書いてしまった。

※あとで貰うDPでも解いてみたが、この場合はLCSとは違って、 dp[0][0~m] と dp[0~n][0] の初期化が最初に必要となることに注意する。

E. 魚の生息範囲 ★★★

3次元の座標圧縮。

この問題では、 x-1, x, x+1 のように、一点あたり3つの座標を放り込むとなぜか（体積計算が）うまく行かなかった。
また、そもそもこのような点の増やし方はメモリがめちゃくちゃ増えてしまうので、むやみやたらにやるのはやめたほうがいいと思われる。

※追記: 普通に最後のforループの上限を変更し忘れていたからだった。

C. バームクーヘン ★★★★

二分探索だが、この形は始めてで面白かった。

分割して出来た値の最小値の最大化を考えるとき、 「すべての分割してできたオブジェクトが x 以上かどうか？」という判定問題の二分探索を行うことで解ける 、というのは初めて出会うタイプの問題だった。

この問題では、判定問題を解く中でも更に2回二分探索をする必要があり、全体の計算量はlogが2つつく形になる。

※尺取法を使ってlogを1つ削ったり、全体で尺取法しか使わずに定数オーダーで解くことも出来てしまうらしい。

C. JOI公園

難易度7の中でようやく自力で解けた。というか今の所これだけぶっちぎりで簡単だった。

とりあえずダイクストラ法すれば単一最短経路の距離はわかる。
結果をIDを保持しながら昇順ソートすれば、広場1に近い順にスキャンできる。
ここで、ベースの値を「舗装すべき全ての道路の長さの和」として、これを地下道を作ることで緩和していく方針で考える。
ソート結果から x を0から離散的にすべて調べることが出来、また、ある広場を調べるときに、 その隣接リストをスキャンすれば、すでに相互接続されている広場が確認できる。
この部分の計算量は O(n + m) になるので、実装上二重ループになっても全く問題ない。

M. ストラップ

これも自力で解けた。1WAしたけど。。

DPなのはすぐわかる。
dp[i][j] := i番目までみたときに残りの穴数がj個の場合の最大 とすれば良い。
j が普通にやると 10^6 になってしまうが、ストラップの付け方から、穴の数は n 個アレば十分なので、 j <= n までで十分。

WAの原因は、穴の数で降順ソートしていなかったため。
ソートしておかないと、途中でストラップの穴がなくなってしまう可能性がある。
厳密には、ソートしなくても、穴が0個のストラップさえ後ろに回せば、それ以外の順序は問題ない。

E. 砂の城

ちょっと迷ったが、わかってしまえば簡単だった。

愚直に考えると、ドットの位置から強度分削っていきたい気持ちになる。
一見すると計算量が爆発してしまうように見えるが、1ドットあたり1回しかその処理をしないように考えると、 普通に1ドットに付き周囲の8マスをデクリメント、とするだけでよい。

あとはQueueを使ってFIFOで処理していけば良い。

C. JOI国の買い物事情 ★★★

道路の中点に街を増やした状態でダイクストラ法するだけかと思ったが、全然違った。

まず、道路の中点に街を置く方法は間違い。
ショッピングモールから最も遠い街がそこになるとは限らない。
すぬけさんのブログにある通り、 すべての道路について (dp[x] + dp[y] + e(x, y)) / 2 を計算してやれば、その道路に関しては最も遠い距離がわかる。

Goで四捨五入を初めてやった気がするが、やはり実数を使わなくて済むなら、偶奇性で場合分けして整数型に閉じるべき。

E. 尾根 ★★

ちょっと難しく考えてしまって迷走してしまった。

自分が最初考えた手法は、標高が小さいところ、特に周りに自分寄り高い標高しかないような場所は尾根にならず、 そこを起点として有向グラフを作る。
低いところから高いところへと有向辺を張ると、閉路が出来ないためトポロジカルソートが出来、DPを考えられると思った。
具体的には、起点を dp[i] = 1 として、そこから値を加算していけば、雨がたまる地域の数が求まり、これが2以上となる地域の数が答え、とした。

しかしながら、これは雨が溜まる地域を重複して数えることがあるため、嘘となる。
重複を省くことを考えなければならない。

ここは回答を観てしまったが、大事なのは雨が溜まる厳密な数ではなく、つまるところ「尾根かどうか？」が判定できれば良い。
このためには、最終的に雨がたまる地域が「1つ以下か2つ以上か」ということさえわかれば十分となる。
言い方を変えると、重複を省くために、雨がたまるエリアの情報はほしいが、「それは最大でも2個までで十分」といえる。
よって、DPテーブルをスライスとして、遷移先のスライス長が1つ未満の場合のみ、遷移元のスライスとマージする、という処理を行えば良い。

。。一応通ったが1300msecぐらいかかったし、メモリ量も大きかったのであまりいい実装ではなかったかもしれない。
でも、グラフで考えるとノード数は 10^6 だし、他のC++の回答とかも見渡すと400msecぐらいはかかっているので、どのような実装を選んでも大して変わらないかもしれない。

F. ヘビのJOI君 ★★★

いわゆる拡張ダイクストラ。苦労の末一応実装できたと思うが。。

自分のダイクストラライブラリに適用しようと、最初に完全なグラフを作ってしまうと、どうあがいてもMLEしてしまう。
通してる人をざっと見渡すと、どうやら「グラフは素の状態で持っておいて、各状態ごとに最適値を管理し、遷移を逐次処理する」という方法をとっている。

ライブラリを弄ることでなんとか通せた。
グラフ自体はもとの形のまま保持し、遷移を考えるところを調整した。
すると時間は200msecほど、メモリは60MBほどでだいぶ余裕を持って通せた。

拡張ダイクストラで考えられる辺を予めすべて張る方法は非推奨かもしれない。
メモリ1GBなら心配なさそうだが。。
経験値がまだまだ足りないので、これから問題を経験していきたい。

D. 水ようかん ★★★

なんか色々と迷走してしまったが、自明なDPから詰めていくのが面白い問題だと思う。

dp[i][j][k] := i番目でカットするようなi番目までの切り方で、最小値j、最大値kを達成できるかどうか をまずは考える。
制約的にこれでは満点にならないので、次に以下のようにDPテーブルを修正する。
dp[i][j] := i番目でカットするようなi番目までの切り方で、最小値jのときに達成可能な「最大値の最小値」

区間DPのような遷移を dp[i] に対して i=0,1,..,i-1 まで片側で考えるようなイメージ。
そこまでわかっていてもちょっと遷移が特殊で難しい。
また、初期化の仕方もちょっと特殊だと思うので、また忘れた頃に解き直したい気がする。

E. 森林伐採 ★★

なんとか自力AC。

これも拡張ダイクストラ。。かと思いきや、答えは普通のDPで考えていた。
一応、グリッドとそこへ至る経路長の情報があれば、拡張ダイクストラできる。

B. 美術展

変数分離で割とすんなり解けた。

E. イルミネーション ★★

結構難しい問題だと思うんだけど、なんか自力で解けてしまった。偉い。

dp[i] := i番目までの最大値 というふうに持っておくと、 i 番目の木を選ぶ場合は、 その木の属する区間全てに関して、区間の左端の一つ左から dp[i] に集めてやれば、最適値を計算できる。
ただし、これは O(n * m) なので、部分点しか得られない。
よって、貰う遷移をへらすことを考える。

各木について、「自身を含む区間のうち、左端が最も小さいもの」というのを事前に計算しておく。
おそらく、これはもっと素朴な方法があるのだろうが、わからなかったので遅延セグ木を使った。
区間の左端を大きい順にソートして、その左端を l としたとき、対象区間を l-1 で区間更新してやると、そのようなデータが得られる。
また、いずれの区間にも含まれない木については、自身の一つ左で埋めてやる。

これによって得られるデータは、 i 番目の木を選ぶ場合の貰う id を示すものとなる。
また、 i 番目の木を選ばない遷移も忘れないように注意する。
これは dp[i-1] からもらってくれば良い。

B. 展覧会 ★★★★★

自分で考えた解法はLISをイメージしたものだったが、それではうまく行かず嘘解法を提出することになってしまった。

難しいと思う。復習が必要な問題。

部分点解法のDPがまず難しい。
LCSっぽい雰囲気のあるDPをする必要があり、まずこれを考えることで勉強になるはず。

そこから「逆に考えて必要な遷移しか考えない」というのが解説で説明されていたが、そこに行き着くのは難しい気がする。
結局は、大きな箱から観ていく貪欲法なんだけど、自分が考えた「小さい箱から見るのでは駄目」なしっかりとした納得がしたい。

B. 愉快なロゴデザイン

難しそうと思ったけど簡単だった。
ほぼ累積和の問題。
円環は2回繰り返して2倍の長さにすると見通しが良くなる、多分。
再帰関数を実装すれば意外ときれいな実装で終わる

B. JJOOII2

ちょっと実装が大変だったが、ひたすら二分探索を頑張って解いた。

模範解答は尺取法だった。
各文字種ごとに「左端を固定したときのK番目のその文字の位置」というのは、しゃくとり法で O(N) で前計算が可能。
たしかにこの方が実装がシンプルになってバグりにくそう。。

D. 最悪の記者

一見すると嫌な問題に見えるが、よくよくみるとDAGになるのでトポロジカルソートを出力すれば良い。
ただし、複数の順序が考えられる場合のチェックはちゃんとする必要がある。
自分は最初なぜか「最長経路の種類が2種類以上」というものしかチェックしていなかったが、 翌々考えたら、途中の経路が二手に分かれる場合なども、複数の経路が考えられることになる。

D. テンキー ★★★★★

大嘘な解法を投げてしまったが、実際には幅優先探索による最短経路問題、あるいはDPと捉えられる問題。
とても大事な問題。

自分の取った解法は全探索の「ような」もので、 M*y + R をある程度たくさん見て、 それらを入力するのに要する最短の操作回数を考えた。
しかし、これは M = 100000 固定の場合にしか適用できない。
その他のケースでは、探索しきれない可能性がある（もしかしたら 10^18 まで見れば十分？証明方法は不明）。

答えは、状態を (現在のカーソル位置, 現在のあまり) として、それぞれの状態への最短経路を求める、というもの。
考えられる状態数は最大でも 10*M なのと、遷移もたかだか定数個なので、全体として O(M) で完了することがわかる。

グラフ的に考えるところまでは良かったが、こういった発想は全く思い浮かばなかったので、覚えておきたい。

未だにやってしまうが、BFSのテーブル更新タイミングには本当に注意が必要。
ダイクストラとは違い、キューに突っ込んだタイミングが更新タイミングになる。

E. 最軽量のモビール ★★★

最小公倍数とDFSの問題。

なんかこういうのはエスパーして解いてしまうのがいいんじゃないかという気がしてきてしまう。
ちゃんと理解しきれていない。

「各部分木で取ることができる重量の総和は色々なパターンがあるが、それは最小としなければならない」というのが 重要な観察になるかも？

B. Fermat ★★★★★★★★★★

数学と数え上げ。難しすぎる。

一応、理論的な部分には逆元の知識が含まれるが、難しい。
定理を知った上で実装しようとしても、数え上げ部分も結構ややこしい。

この解説が一番参考になる？
個数の部分の証明が正直良くわからなかった。。

B. 象使い ★★

(直前のid, 今のid) を状態にまとめてダイクストラを行う（拡張ダイクストラ）。

鈍角・直角・鋭角判定は、整数に閉じて行うことができるのは思い出しておく。
辺の数 m の制約が書かれていないので密グラフかと思ったが、それだとTLEしてしまう設定だと気づくのに時間がかかった。
疎なグラフを仮定して、普通にpriority queueを使ったダイクストラを行えば良い。

制約はちゃんと明示してほしい。。

D. ぴょんぴょん川渡り

だいぶ素直なDPだった。

純粋に全部の列についてテーブルを定義するとMLEしそうなので、メモリ確保から無駄なくやるようにしたが、 工夫があるとしたらそれぐらい。
普通のナップサックDPの一種だと思う。

A. 委員会

かなり簡単な木DP。

B. 色紙

自分の紙の上に乗っかっているものを全て列挙し、有向グラフを作る。
それをトポロジカルソートしてやれば良い。

ある色紙がすべて覆われているケースがコーナーケースで、気づくのに時間がかかってしまった。

C. インフルエンザ

グラフさえ構築してしまえば、単なる幅優先探索するだけの問題になるんだけど。。

多分自分の解法は当時のPCスペックだと通らなかったんだと思う。
非公式解法？を読むと、 「バケット法を使え」とある。
確かに9種類に分けてしまえば、細かい分類はあとでやれば良さそう。

B. カンニング対策

d を決めてしまえば、カメラの配置は貪欲に決めれば最適になるので、二分探索して最小値を探る。

判定関数のデバッグに時間がかかってしまった。

B. 分数 ★★★

priority queueを使う発想は良かったが、TLEしないための工夫が足りなかった。

初期値を (1, m) だけにして (i+1, j) or (i, j-1) を探索するような方法を取ったが、 模範解答では (1, i) をすべて最初にpriority queueに入れていた。
ここから、取り出したものについて、既約分数のみをpriority queueに突っ込む形にしてやれば良い。

priority queueの初期化と更新の仕方は勉強になったが、この方法の計算量解析は結構大変な気がするが。。？
更新の際に、次の既約分数を求める部分が計算量を膨らませてしまう気がする。
しかしながら、「スキップしたものはいずれどこかでスキップせずにpriority queueに突っ込まれる」ような気もしており、 実際に120msecぐらいで通ってしまう。

C. あみだくじ

なんか不思議な問題だったが、意外とすんなり実装できて通った。
しかし想定解法とは若干違う実装になった。
自分の場合はあみだくじのシミュレーションを愚直に行ったため O(n * h) だったが、 回答のように、全ての横棒を高さでソートしてしまえば、上から順に O(m) でシミュレーションできてしまう。

E. ペンキの色 ★★★

2次元座標圧縮が必要なときは、余計な座標を情報に含めないようにしよう、というのはよくわかった。
しかしながら、それにしてもDFSからBFSに変えただけでメモリ量が激減するのは解せないので、もう少し研究する。

D. ラーメンの食べ比べ ★★★

※この問題はC++でしか提出を受け付けていないため、自身で書いたコードは提出していない。

易しめのインタラクティブ問題だが、地味にわからなかったので解説を読んだ。

まず、部分点から考えることが大事。
冷静に考えると、 n 個のラーメンのうち最もこってりしたもの、最もあっさりしたものは、 それぞれ O(n) 、正確には n-1 回の比較で発見することができる。
例えば、最もこってりしたものを見つけることを考える。
これは、適当な2つのラーメンの比較からスタートし、こってり度合いが勝ったものを残し、まだ比較していないものと比較させる。
これを繰り返して、最後に残ったものが最もこってりしたものとなる。
バブルソートで、最大もしくは最小が決まっていく一回のイテレーションをイメージするとよく分かる。

↑の方法だけだと部分点になってしまうが、満点解法では、さらに最初にグループを2分割することを考える。
つまり、まず最初に一斉にラーメン同士を比較し、よりこってりと判定されたグループA、 よりうすいと判定されたグループBに分ける。
最もこってりしたものはグループAに存在し、最も薄いものはグループBに存在するため、これも戦術のバブルソート風なアルゴリズムでそれぞれ求める。
全体の比較回数は、最初のA,Bに分ける部分がだいたい n/2 で、最大・最小を求める部分はそれぞれ n/2-1 程度なので、合計回数が規定回数に収まる。

F. ビンゴ ★★★★★★★★★

典型的なDPなんだろうけど、遷移の高速化がまだ自分にとって難しい。
ナップザックDPっぽいもので、同じ i 番目から横方向に遷移してくるDPがまだなじまない。

kmykさんのブログに示された解法。
メモリ制限的に配列使い回しが必要だが、それだとわかりにくいので普通に書いたものが以下になる。

dp[0][0][0] = 1
for i := 0; i < n*n; i++ {
	for j := 0; j <= S; j++ {
		for k := 0; k < min(m, j); k++ {
			dp[i+1][j][k+1] = dp[i+1][j-1][k] + dp[i][j-k-1][k]
			dp[i+1][j][k+1] %= M
		}
	}
}

ans := int32(0)
for k := 0; k <= m; k++ {
	ans = mod(ans+dp[n*n][S][k], M)
}
fmt.Println(ans)

これでもちょっと理解しきれていなそう。。

nanikakaさんの解説を見つけたので参考にしてみる。
分割数っぽい考え方は以下の図でできている気がする。