競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2312 魔法少女さやかちゃん

多分勉強会の問題の中で開いてから解くまでが最速だった.(これは罠で,日本語の問題だからという説がある

解法

輪というのが考えにくいのでなんとか区間というか数を一列に並べる問題にならないか考えてみます.
試しにK_{min},K_{max}の位置を固定してみると,K_{min},K_{max}の間に二本の数列が存在していることが分かります(長さ0の数列もありうる)
この二つの数列について,Kの値をどちらの数列に割り振るか決めたとき,どちらの数列も単調増加になるように並べると最適になることがわかります.
単調増加な数列を2本作ればよいので,Kの値を事前にソートしておいてDPをします.
dp(i,k):=片方の数列の最後尾がiでもう片方の最後尾がkであるときに必要な精神力の和の最小値
とすると各状態の遷移は累積和を使えばO(1)でできるのでO(N^2)でできます.
空間計算量もdpの配列を使いまわしていけばO(N+M)になります.

AOJ2538 Stack Maze

勉強会の問題がICPCっぽく(悪い意味で)なってまいりました.

問題文

Stack Maze | Aizu Online Judge
日本語訳が欲しい方は「mayoko stack maze」とかで検索するとよいです.

解法

最初に思いつくのはdp(r,c,今持っている宝石のスタック)というDPだと思いますが,多分間に合いません.

書くのが面倒なのでN=HWとします.
すると,次に思いつくのはO(N^3)の次のようなDPだと思います.

dp( (r_s,c_s) ,(r_t,c_t) ) :=(r_s,c_s)からスタートして(r_t,c_t)までスタート時点で積まれているスタックに影響を与えずに稼ぐことのできる得点の最大値
とすると全体O(N^3)で全ての長方形で取得できるスコアを計算でき,最終的にdp( (1,1),(H,W) )が答えになります.
これのやり方については(r_s,c_s),(r_t,c_t)が宝石と穴の対になっているかで場合分けをしてごにょごにょします.

上記の解法では間に合わないのでもう少し考えます.
宝石と穴の関係について,一つのデータセットには同じアルファベットが最大10までしか存在しないので,宝石,穴の組み合わせについては10*10*26=2600でほぼNの最大値と一致します.先ほどのDPについて考えると,考えるべき座標の対( (r_s,c_s),(r_t,c_t) )は宝石と穴のペアとスタート,ゴールだけでよさそうです.
よって状態数がO(N)に落ちて,各状態の更新をO(N)でやれば全体O(N^2)ぐらいでできるはずです.

具体的にどういう実装をしたかというと,メモ化再帰を行いました.
f(S,T)について,始点Sから終点Tまでいくつスコアを稼ぐことができるかという配るDPを行います.
今見ているマスが通常マスならそのまま右下への遷移を行い,宝石マスなら長方形内の穴との対f(S_c,T_c)を全探索し,DPの表に反映させます.
これをメモ化再帰によってO(N^2)で求めています.
実際は宝石と穴とのペアの探索で高々10回のループを回しているので,5*10^7ぐらいの計算回数になると思います.

AOJ2296 Quest of Merchant

頑張るだけ

解法

色々眺めていくとナップサック以外考えられなくなると思うのでナップサックで考える.
まず初めの考察として,原点から出発して再び原点に返ってくる操作を1セットとできそう.

では1セットにしてどうするか.どう見てもN \le 7が怪しい.
1セットで訪れる町の集合を個別に考える.町の集合は2^N通り.
訪れる町の集合が決まると,その町の集合を全部通って原点に帰るまでの最短時間はTSPもどきでまとめてN2^Nで求められる.
また,町の集合ごとに取得できる商品についてナップサックDPを行うことで,1セット(重量上限W)で持ち帰れる最大の商品価値をNM+MWで求めることができる.

つまりここまでで,各訪れる町の集合ごとに,(所要時間t,商品の合計価値v)という情報が得られる.
あとはこれを使ってナップサックDPを行い,時間T以内に取得できる商品価値の最大値を求めてやればよい.

AOJ2224 Save your cats

薔薇園の魔女に比べたら11454倍楽

解法

閉路を含まなくするためにできるだけ少ない長さの辺を削りたい.
すなわち,できるだけ辺の総和が長くなるように閉路を含まないグラフを作りたい
よって最大全域森を作ればよい.

これはクラスカル法で最小全域木の作り方と同じように貪欲に長い辺から使って構成していけば作成可能.

AOJ2310 薔薇園の魔女

二度と解きたくない

解法

全探索をします.
といっても直線を引く候補が無限個あるので,少し考察をします.

最適解の直線があったとして,分割する数を減らさないように少しずつ直線の角度をずらしていくと,直線とある格子点がぶつかるところで動かせなくなります.
このことを考えると,格子点を通る直線をほんのわずか左右に動かしたものだけを候補として考えればよく,HW本の直線だけ考えればいいことが分かります.
直線を決めたら,その直線が何回境界をまたぐかを求めてやるといくつに分割できるかが求められます.つまり直線と線分の交差判定ができればよいです.
サンプル2から,角をちょうど貫通する直線は角の生命体を分離しないっぽいです.いやこれどう見ても4つに分割してるでしょ...

あとはあとは線分と直線の交差判定をO(H+W)でやりたいので,直線を偏角ソートして順に探索していけばO(HW(H+W)で解けます.
探索上では格子点を通る直線の探索をしているので,格子点を通る場合は左右にずらした場合の線分の交差について,2通りのカウントが必要になります.

AOJ2168 Luigi's Tavern

マッチングかー,フローっぽいなあ,どう見てもフローじゃん
みたいな感じだった

解法

パーティーを沢山作りたいので,各パーティーに役職はそれぞれ高々一人でいいことが分かります.
それで,人を頂点,友好関係を辺として張ってみると各頂点を高々一回ずつ使ってマッチングを沢山作ってくださいみたいな問題に見えてくると思います.
とりあえず簡単化のために,各パーティは必ず4つの役職全てを含む場合を考えてみましょう.
各頂点を高々一回というのは,頂点を入り口用と出口用の頂点二つに分割して,入り口と出口を流量1の辺で繋げば実現できます.
これでこのケースはグラフを構築してフローを流すだけで解けることが分かりました.

では各役職が欠けてもいい場合について考察してみましょう.
ある役職が欠けてる場合は,フローを流すときその役職をスキップしてフローを流すことができると考えることができます.
スキップする回数も制限がありますが,スキップするために使う頂点をその役職のダミーの人であると考えると,
ダミーの人がそれぞれNW,NC,NM人いると考えることができます.
そしたら同様に入り口と出口を分けてその間に人数分の流量の辺を張るだけになります.

グラフの構築ですが,自分で番号を決めるのではなく,どの役職の何番目の人=何番目の頂点みたいに変数として保存して置き,sz++ のようにして自動で割り当てていくと比較的楽になると思います.

AOJ2305 Beautiful Currency

Beautifulのスペルが覚えられないのは私だけじゃないはず.

問題文

Beautiful Currency | Aizu Online Judge

訳は載せませんが,美しい通貨群にするために必要な各々の変動レートの"最大値"を求める問題です.
総和と勘違いしてサンプルが合わず丸一日悩みました.

解法

N \le 20なのでbitDP...と思ってしまいそうですがそんなことはありません.
元の通貨の最大値をMとします.
冷静になると(ならなくても)以下の三つのことが分かります.

  • 各通貨について,変更後の通貨の値は2M以下でいいことが分かります.(2Mにするより1に変えたほうが結果が良くなるため)
  • 通貨の大小の順序を変える必要はない(同じ値になることはある)
  • i番目の変更後の通貨の値b_iは,i-1番目の通貨の値b_i-1の倍数であればよい.(再帰的にj < i-1番目の通貨の倍数になるため)

以上のことから,
dp(i,m):=i番目の通貨の値をmにしたときの変動レートの最大値の最小値
と定義できます.
この値について,貰うDPで値を求めていくとO(NM\sqrt(M))で間に合わなさそうな気がしますが,
配るDPにすると実はO(NMlogM)となり間に合います.
logになる理由はこの問題の解説を見るといいと思います.
No.390 最長の数列 - yukicoder