読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

会津合宿2016Day1 立命セット A~E 解いた

振り返ります。(F, Gは解ける気がしないので勘弁……)

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

解説: https://drive.google.com/drive/folders/0B5BaKBeHPaOoV0NWdEE0QXJfa28

A: キャベツ / Cabbage

数列上をポインタが動くので、最終的にどこにいるか求めよという問題。

難しくない??(これは僕が無理にポインタとして解釈しようとしたからで、bool配列で廃棄するしないみたいなものを持ってやればいいのかもしれない)

gist.github.com

B: イカったー / SNS

2つの整数A,Bがある。Aを増減させてA:Bを1以上n以下の整数比で表せるようにしたい。Aと変更後のA'の絶対値の差の最小値を求めよ、という問題。

Nが小さいので比が全探索ができるというのが面白い。本番は既約な比だけ考えようとしてバグらせていたけどどうせ結果は変わらないのだからまとめてしまってよかった。

gist.github.com

C: 失われしグラフ / Lost Graph

n頂点の有向グラフで、入次数iの頂点がa_i個、出次数iの頂点がb_i個なるものは存在するか。存在するならばそのグラフを1つ求めよ。ただし多重辺はないものとする(自己辺はあり)。

最初は貪欲解を書いていたが、バグが取れなかったので結局フローを流した。フローがだんだん使えるようになってきてうれしい。

gist.github.com

D: DAG トリオ / DAG Trio

Gの制約易化版というめずらしいスタイル。問題タイトル好き。

有向グラフで、3つの有向辺を削除すると3つのDAGに分割できるようなものをDAGtrioと呼ぶことにする。与えられたグラフGがDAGtrioであるか判定せよ。ただしGは無向グラフとみなすと単純かつ連結である。

DAGtrioは D1-D2-D3(-D1)というトライアングルの形かD1=D2-D3という形になるが、このどちらも1辺を適当に選んで削除するとD1-D2-D3という形にできる。そこで辺eを全探索し、eを削除したグラフがD1-D2-D3になるかを判定すればよい。この形になるには、eを削除したグラフ全体がDAGかつ橋が2本以上あればよい。ただし注意として、eを削除したときにグラフが非連結になってしまうならばこのeは候補から外す(非連結なグラフで橋検出をするとやたら橋が出てくるので)(ハマった)

辺を1本削除するというアイデアがなるほどという感じ。二重辺連結成分分解は最近勉強していたので通したかった。原案者がYさんなのを見て完全に察した(悔しい)。

gist.github.com

E: 札 / Fuda

まさかのリアクティブ。

ある頂点vに注目すると、vは自身に接続する辺の自分とは反対の側の看板に対し、deg(v) - 1枚ずつ札を分配する。なのでdeg(v) * (deg(v) - 1)を足し上げるだけ、と考えた。

何を求めるべきかがわかれば実はとても単純という問題だった。

こういうのなかなか作れないので面白い。

gist.github.com

感想

終わってみると、割とバランスのいいセットだった気がする。D問題はD問題としてちょうどいい中ボス感のある問題だった。来年はF, Gを考えられるくらいになりたいなあ。

作問スタッフのみなさんお疲れ様でした。

来年のRUPCも楽しみにしてます!