ゆらのふなびと

競プロ, Python, C++

会津合宿2016Day3 北大セット 解いた

一通り解いたので、各問題を振り返ってみたいと思います。

オンサイトで自分が解いたのはBだけ。(あとはみんなでGを考えていた)

問題: http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day3

解説: (コンテスト翌日に上がっていて仕事が早い!)

hcpc.web.fc2.com

A: 席取り - Taking a Seat -

いくつか条件があるので、座れるマスの個数を求めよという問題。

言われたことをそのまま実装すればできる。

gist.github.com

B: 山手線ゲーム - Yamanote-line Game -

?に乗ったり降りたりしてできるだけ儲けろという問題。

p_i - d のうち正のものの総和を取ればよい。

降りる回数(p_iをもらう回数)と乗る回数(dを払う回数)は同じなので、ペアにして考えてよい(本番はスタートはどこでもよさそうな気がしたけど、ゴールを全探索して~とか考えていた)

gist.github.com

C : Mod!Mod!

いくつかの整数が与えられる。総和のmod3で遷移するが0に行くと死ぬ。最大で何個整数を取れるか。

整数は以後mod3で考える。すべて0のとき答えは1。1, 2があるときは1, 2のどちらから始めるかの2通りがあって、1から始める場合は

  • 1から始める
  • 0をすべて使う
  • 1, 2, 1, 2... を1, 2の少ない方の分だけ繰り返す
  • 余ったら1を2回までor2を1回まで使える

が最適。2も同様。これをそのまま書いた。もっと短くできるんだろうか。

gist.github.com

D: 日焼け - Suntan -

あいずにゃんかわいい。

排反なN個の区間が与えられる。長さTの区間で各区間を被覆するとき、被覆できる長さの総和の最大値はいくらか、という問題。

解説でしゃくとりと聞いたのでしゃくとりで書いた。確かに楽に書ける。丸ごと被覆できる区間をどんどん取り込んで、右端だけよしなにしてやればOK。

gist.github.com

E: 鬼畜ババ抜き - Unbalanced Old Maid -

f:id:pakapa104:20160920201317j:plain

高坂さん、園田さん、南さんがババ抜きをする。園田さんは顔芸でカードがばれるので園田さんからカードを引く人は自分に有利なカードを取る(この戦略は問題文で詳細に決まっており、我々解答者に選択の余地はない)。他の人からカードを引く人は相手のカードを等確率で引く。園田さんが負けない確率を求めなさい。という問題。

本番これを読んだときは、確率のDPということはわかるけどなんだこれは~という感じだった。解説を聞いて感動。カードを整理(2枚すでにそろっているカードを捨てる)すると各カードは0枚or2枚になるので、カードが存在するなら誰が持っているかは3_C_2 = 3通りしかない。その各パターンA, B, Cのカードが何枚あるかさえ覚えて置けば、それ以上カードを区別する必要はない。よって(Aが何枚, Bが何枚, Cが何枚, 誰がジョーカーを持っているか, 今誰のターンか)を状態としたDPが可能。O(nnn33)=O(n3)でn<=100なので解ける。DPって言うけどループはないの???と聞きたくなるが実は園田さんパワーでループがなくなる。これもすごい。

ほとんど解説を見ながら書いたけど、遷移をじっくり考えるのが楽しかった。submit一発で通って最高の気持ち。

gist.github.com

F: 風呂がオーバーフロー - Overflow of Furo -

辺の容量を1本だけ無限にできるときの最大の流量を求めよ、という問題。

制約的に、無限にする辺を全探索して毎回最大流問題を解くというのは不可能。直観的には辺はボトルネックになるところだけ調べればよさそうだなーという気がする。それって最小カット。なのでまずは元のグラフで普通に最大流問題を解き、最小カットを取り出す。この残余グラフ上でs->u, v->tの最大流問題を解いておくと、カットに含まれる辺uvをオーバーフローさせたときの流量は F + min(s->u, v->t) となる。こうすると最大流問題を解くのがE回→V回に落ちて嬉しい。

ボトルネック=最小カット」とか、残余グラフ上でフローを解くと追加で流せる流量が求まるとか、そういうフローへの理解を深められた問題だった。

gist.github.com

G: 最小包含矩形 - Minimum Enclosing Rectangle -

みんなぁ、こんにちは! 八森中ぷろこん部の藍座あいりだよぉ。(以下略)

N個の辺を共有してつながれた正方形全体を包含する長方形の最小面積を求めよという問題。

入力を凸包に変える。凸包を包含する長方形で最小面積のものは必ず1辺を凸包の辺と共有する(解説では「知識」と言われていたが、それは割と直感的な気もする)ので、そこを全探索。本番は凸包の頂点数もNくらいあってN<=105だから辺からの最遠点を三分探索で求めてほげほげ~と考えていたが、凸包の頂点数はそんなに大きくならない(整数座標で座標値の幅がNだとO(sqrt(N))個になるということが蟻本に書いてある)ので、O((凸包の頂点数)2)かけてよい。結局凸包を取るのが一番時間がかかるので全体ではO(NlogN)。

この問題のおかげで幾何ライブラリが少し潤った。

gist.github.com

感想

本番ではBしか解けなかったが、後半のE, F, Gはどれも学びが合って解いていて楽しい問題だった。北大セットは問題文までサービス精神に満ち溢れていて楽しい。

本当に勉強になりました。北大のみなさんありがとうございます。

次は来年のRUPCということで、楽しみにしています(?)