ゆらのふなびと

競プロ, Python, C++

KUPC2017参加記

京都オンサイトで参加しました。

コンテスト前

NA勢(shora_kujira16, Yazaten, ratea, yurahuna)で一緒に登校

13:00に着けばいいと思っていたらそれはコンテスト開始時刻で、12:00の集合には自明に遅刻する

行きがけにラーメンをACして会場へ

コンテスト開始には間に合った

一部の競プロerが喜びそうな北海道土産があったので差し入れ

コンテスト

kupc2017.contest.atcoder.jp

A: ソートして大きい順に履修する

B: 大きい方から割る*1

C: なんか解けなくてつらかった

D: 数字が2つあればいけそう

何もわからないので実験のコードを書く*2

5x5を見ると8通りしかなく、パターンに規則性がありそう

if 文を書いてエイってしたら通ってしまい笑う

こういう問題作れる人頭いいなあ

E: 宝箱を頂点、鍵を辺とするグラフを考えて、サンプルを図示する

「x か y を開けられる鍵で x を開ける」⇔「辺 {x, y} を x <- y に向きづける」だと思うと、入次数が1以上の頂点の価値の総和を最大化したい

連結成分ごとに独立

1つの連結成分について考えると、適当に頂点 s を1つ決めてそこから辺の向きを外向き*3に決めていけば s 以外の入次数は1以上にできるので、各連結成分で空けられない宝箱は高々1つ

連結成分に閉路があれば、閉路をぐるっと1周してその閉路から外に向ければよいのですべての頂点の入次数を1以上にできて、木だと辺が足りないので入次数0の頂点が1つできる

UnionFind で閉路検出して、木のグループは最小値引いてAC

あとは解説を聞いただけ

Fはひたすらやばそうだった

Gはいろいろ解き方があるらしく面白そうだった

懇親会

懇親会では drafear さん、amano さん、kimiyuki さん、odan さん、shora さんと一緒のテーブルだった

京大の drafear さん、amano さんに作問裏話を聞いたり、kimiyuki さんに Piet を "png で圧縮した結果を" ゴルフするというエクストリームスポーツの存在を聞いて震えたりした

途中で asi さんがやってきて、asi さんと shora さんから 6 年前の SuperCon の話を聞いた*4

当時参加者たちでやっていたという「バイオレンス・ノベル・ポーカー」が面白そうだった*5

お店から出た後、富山から来た kuuso さんから車で 4 時間かけて帰るという話を聞いて大変そうだなあと思うなどした

まとめ

スタッフのみなさんありがとうございました。

*1:入力の N 要る?

*2:ここでバグって1時間くらいかかっていてダメ

*3:例えばBFS順

*4:その頃から知り合い/競プロやってるってすごいなあ

*5:「漢字の書かれたカードを5枚集めて一番面白い必殺技を作ったやつが優勝」というゲームらしい。バイオレンス・ノベル・ポーカー - Google 検索