AHC020、ご参加頂きありがとうございました！いかがでしたでしょうか？お楽しみ頂けたのであれば幸いです。
前回に引き続き、今回もwriter記を書いていきます。
↓前回のyukicoderでのwriter記
問題
（tester: wataさん）
施設配置問題 + 集合被覆問題 + シュタイナー木問題みたいな問題でした。おそらく貪欲か焼きなましをした人が多いのではないかと思うのですが、その中でも結構方針が分かれる問題だったのではないかと思います。皆さんの解法はどうでしたでしょうか？
writer解は各頂点の出力を上げ下げする焼きなましでした。解説放送に使用した解法スライドはこちらです。
↓writer解
作問のきっかけ
実はしばらく前（yukicoderで作問して以来？）から、wataさんにお会いする度に「AHCのwriterやってみません？」とお誘いを受けていました。
毎回自分なんかがwriterなんてと思って「機会があれば……」と返していたのですが、今回は自社コンテストということで、良い感じの原案が生えたら出してみたいなという気持ちになりました。運良く良さげな原案が生えてくれたので、今回出題することになりました。
原案作成
今回は題材から作問しました。*1 AHCはストーリーが毎回面白いので、とりあえず面白いストーリーになりそうな問題設定をたくさん*2生やして、その中から良さそうなのを選びました。選定にあたっての観点としては、
- ストーリーが面白いか
- 自明解があるか
- 実装が極端に重すぎないか
- 初心者でも手が止まらないか
- 上位陣が運ゲーにならないか
- ビジュアライザにALGO ARTISロゴを入れられるか*3
といったあたりで、それらを満たすものとして今回の問題を選びました。writer解が焼きなましになったのはぼくの趣味ではなくたまたまです。だって焼きなまし強いんだもん……。
今回は上記の中でも、特に「初心者でも手が止まらないか」という点を重視しました。というのも、今回のコンテストがAHCerの増えるきっかけになればいいなと思ったからです。貪欲でもそれなりの解は出せますし、ビジュアライザを見れば改善できそうな面も分かりやすい*4ので、初心者でも何かしらの工夫ができる余地は作れたはず……？今月末にはトヨタオンサイト予選もありますし、AHC界隈がさらに賑やかになれば嬉しく思います。
調整作業
コストの値が頂点の出力強度と辺のON/OFFの和になるため、このあたりのコストの調整はかなり悩みました。片方だけでスコアが決まったら面白くないですからね。そして住民の散らばり方も関わってくるという……。テストプレーをしては調整の繰り返しで、ここは相当時間をかけたところです。その甲斐あって自分では満足のいくバランスになったかなと思います。皆様解いてみていかがでしたでしょうか？
難易度調整ですが、writer作業中「これじゃ簡単すぎるかな？もうちょっと難易度上げた方がいいかも？」と思っていたのですが、上げなくて本当に良かったです……。テストプレーの結果はぼくもwataさんも506M点くらいでほぼ同じだったのですが、wataさんを基準にしてはダメなことが分かりました。
叙々苑
ほんものてりーに勝てた人が一人もいなかったので、今回も該当者なしということで……。
感想
ひとまず無事に終わって安心しています。致命的なclarが来ないかビクビクしていたのですが、特にそんなこともありませんでした。
writerとして順位表を眺めるのはなかなか新鮮でした。高みの見物ができて楽しいですね。弊社社員を煽ることもできて最高です。これはクセになってしまうかもしれません。*5
最後に、admin兼testerのwataさん、解説放送にご出演くださったかえでさん、AtCoderというプラットフォームをご提供してくださっている社員の皆様、そしてコンテストにご参加くださった皆様、本当にありがとうございました！次回があるかは分かりませんができればまた出題したいなと思っておりますので、もしあれば是非ともまたよろしくお願いします。
