KUPC2017に参加しました

参加記を書くまでがコンテストですよね、もう数日たってますけれども。

KUPCは今回が初参加でした。京都オンサイトで参加し、6完して京都で3位、全体で33位だったので結構満足しています。

以下各問題の感想を書いていきます

大きいほうからとっていけばよい

Tを2で割っていってSに到達すればok。その前に0になってしまうとだめ

数字が大きいほうに向かうときは二通りあるけど小さいほうに行こうと思ったら1本ってところがポイントっぽい

結構好き

辞書順最大のものかつ長さを短くしたいので、詰められるだけ左に詰めていくことをします(これはO(n))

ただしこれだとaazみたいなケースで死ぬので、更新されなくなるまで無限ループさせてAC(は？)

合計のorderはたぶんO(n^2)

1時間半ぐらいこの問題にかけた。

とりあえずn<3のときは1色で塗れるしn>=3のときは2色で塗れることが分かったので、あとは何通りかを試していくのですが・・

ずーっとn=4のケースをこねくりまわして法則を探そうとしていて、いったん別の問題にうつった後帰ってきてから大きいケースで試したところ8通りしかなくね？と気づきAC。

n=3のときは全探索するコードを書いたのですが、n=5のときもこれで試せばよかったです。(少なくとも8通りはあることはそのときにすでに気づいていたので)

まずn+m頂点のグラフを用意します。

鍵iが宝箱x_iとy_iを開けられるとき、i+nとx_i,i+nとy_iの間に辺を張ります。

こうしてできたグラフの連結成分ごとに考えていきます。

まず連結成分内の鍵の個数と宝箱の個数を比べ、鍵の個数>=宝箱の個数であればその宝箱は全て開けることができます。

また、鍵の個数<宝箱の個数の場合でも、鍵と同じ個数で、任意の組み合わせの宝箱を開けることができます。

(証明は読者への課題とさせていただこう)

よって各連結成分ごとに貪欲的にとっていけば答えが求まります。

よい問題だと思いました

ｳｰﾝ難しい。提出状況を見てこれはやべーと思ってあんまり考えていませんでした。

解説を見てもこれをコンテスト中に解くのはつらいなあとか思ってました。

発想はそこまで時間がかからなかったけれども実装がつらいつらい

方針としては長さ63の鎖を用意し、根からi番目の頂点が整数xのiビット目に対応していて、頂点iの次数が3ならそのビットは1,2なら0という定義です(つまり子が1つなら0、2つなら1)。

これを二分木の形で表現しようとすると最大で63*2の頂点が必要となり少し100をオーバーしてしまいます。そこで1つゴミ頂点を用意し、i番目のビットが立っているならそのゴミ頂点と結ぶという実装をしました。これにより頂点数は65ぐらいで収まります。

のですが、最初の木にある辺を使ってはいけない、多重辺は禁止、自己辺の禁止ということでいろいろと大変な実装をすることになり、40分ぐらいひたすらコードを書いていました。

最初の木はなくてもよかったんではと思います。

ここまでのｆ以外の6問を通した時点で残り10分だったので、ほとんど考えていません。

おいしかった

初めてのオンサイトコンテストで緊張していましたがなんとかやれました。

人見知りゆえあまり交流できなかったのが悲しいですね・・人と話すことは嫌いではないんですがなんともまあ(´・ω・`)

来年は運営側に回りそうです。よろしくお願いします