JOIうめ

JOI

JOI 09春合宿

問題は
JOI 2008-2009 春季トレーニング合宿 問題

Pyramid

概要

H*WのマスにN個のピラミッドが建っている。各ピラミッドは座標x_i,y_iを頂点として周囲のマスに行くに従い高さが１下がる構造をしている。異なる重なっている部分は高さが高い方が採用される。
全てのマスの高さの合計を出力せよ。

解法

頂点の石の高さを一旦メモし、各添字が増える方向に高さを更新し、その後各添字が減る方向に高さを更新する。
各頂点でピラミッドが建っていると考えて良いため、この操作で各マスでの高さが求まる。

実装

単純なループ

感想

気づけなかった。ただそれだけ。

Abduction

概要

H*Wのマスがあり、(1,1)から(H,W)へマス内で動き回る。今、動いた方向の情報がM個与えられ、曲がってからは1マス以上動く。
ゴールにたどり着く方法は何通りあるか。mod100000で答えよ。

解法

曲がる情報を見た後各マスへ行く方法をdpする。この方法だとH*W*Mかかるので、不適切。各更新は縦と横の情報のみ見れば良いことがわかるのでMAX(H,W)*Mで終わる。これにより計算量が削減できる。

実装

解法の通り。

感想

実験すれば気付ける。実験なしでも気づきたい。

Advertisement

概要

有効グラフがある。ある頂点を選ぶと、そこからいける点へ広告を配布する。
全ての頂点に広告が行き渡るために必要な頂点数の最小値を求めよ。

解法

強連結成分分解(SCC)し、同じ成分を同値類としてグラフを再構成する。
入次数が0の点の個数を数える。

実装

SCCの実装に注意。その後は代表点によりグラフを作り、入次数が0の点をカウントする。

感想

SCCさえ実装できれば終わり。

Distribution

概要

各点に数字の書かれた根付き木が与えられる。（各点で人を表し、親が上司であると考える。）
根にはm枚の紙があり、これを葉方向（部下方向）へ配布していく。紙は分裂せず、1枚以上読んだ人の数字が全体に加算される（読んだ枚数によらず、その人の持っている数字を加算する）とき、合計値の最大値を求めよ。

解法

dfsにより、葉までのコストの最大値が求まる。最大値を求めた後に、最大値を辿る経路のコストを0にする。
これをM回繰り返すことによりO(NM)で求まる。

実装

dfsをひたすらくりかえす。来た道はparentを管理し、葉から道を復元することで達成できる。

感想

最初dpを考えて迷走したが、Mが意外と小さいことに着目したら試すだけで良いことに気づき、解けた。