【No.025】「会津合宿 2016 参加記」

1日目立命館セット

ryohatsuxx というチームで参加しました。(オンライン6位)

.@dohatsutsuさん .@mot_xxさんと出ます．よろしくお願いします！！
— Ry0u_ (@ry0u_yd) 2016年9月17日

C問題とE問題は僕が担当しました。

C問題はいろいろバグを埋め込んでしまって3WA。なかでもaとbを逆にしてしまうバグはひどかった・・・。

E問題ではグラフが完全に構築されるまでクエリを投げ続ける解法を試した後、グラフを完全に構築する必要がないことに気づいて「なるほど」と思いました。

( flushするのを忘れていてWAを出してしまい申し訳なかった )

D問題はry0u_ydさんと相談して解法を考えてもらい、僕が実装して解きました。

ry0u_ydさん、ありがとうございました。

2日目会津大学セット

寝坊してしまい13時ごろに大学に到着しました。

到着してすぐに自分の作った問題のClarを確認し、重要なものがなかったので一安心。

僕が作ったのはDとFとJとM問題でした。

ここで少し作問側の感想を書きたいと思います。

D問題

思っていたより正答率が低かったです。

「ほんの少しだけ変わったダイクストラの問題を出したい」と思っていろいろなグラフを書いていたら、「エッジに使用できる時刻が限定されたグラフ」というのを思いついたことがきっかけでこの問題が生まれました。

（ストーリーはコンテスト前日の夜になってから急遽付け足したものなので、橋が一方通行になってしまうという違和感が生まれてしまいました)

F問題です。 pic.twitter.com/vQgd6TmXZ8
— ぴゃ (@snuke_) 2016年9月18日

コンテスト終了後、snukeさんがツイッターでGIFアニメーションを投稿してくれました。

そのときちょうどFの解説を書いている途中だった僕はほんの少しやる気を失いました。

もともとは石(ストーン)が2個以下しか存在しないという制約で出題しようと思っていたけれど簡単すぎるなぁと思ってボツにしていました。

しかし数日後、石が3個以上あればクリアできることに気づいて出題できるようになりました。

( 問題の概要をジャッジのメンバーに説明しているときにH=1またはW=1のときに石が3個以上あってもクリアできない可能性があることに気づきました。)

HとWの制約をどちらも1以上16以下に設定したのは。 H=1またはW=1 のときに全探索ができるからです。とはいえO( 石の数 )でも解けますが・・・。

面白い問題ができたと思っていましたが、既出だったらしくて残念でした。

最初は回数だけを出力させるつもりでしたが、ある日辞書順最小の最小カットを求める方法が分かったのでより難しい問題を作ることできました。

3日目北海道大学セット

@Yazaten さんと @tookunn_1213 さんとで　energy_star というチームで参加していました。オンラインで2位という好成績。
— 怒髪 (@dohatsutsu) 2016年9月19日

Yazaten君とtookunnさんにAとBを書いてもらい、自分はC問題とF問題を担当しました。

F問題でもバグを埋め込んで4WAしてしまいました。Ford Fullkerson法で通しましたが1.85secもかかっていて、制限時間ギリギリで危なかったです・・・。

GはYazaten君と一緒に考察した結果、凸法をして頂点数を少なくしたあと、どの辺を長方形の辺と重ねるか全部試す方針で実装することになりました。

INFの値が小さくて1WAしましたが無事ACしました。

dohatsutsu’s diary