yukicoder contest 378 感想

はじめに

皆さん，コンテストお疲れ様でした．はちじです．この度単独コンテストを開催できましたので，その感想を述べていきたいと思います．

A - UFO Game（★1）

• AC人数：119人
• First AC：shobonvipさん（0:49）

記念すべき単独コンテストの，最初の問題です．コンテストを開催するにあたり，より多くの人に解いてもらえるようにと，1問目は難易度のかなり低い問題を心がけようと思い，簡単めの場合分けと計算によって答えられる問題を出題しました．文字列のスライスやオーバーフローなど，気を付ける点は様々あると思いますが，それでもABC-A, Bレベルだと思います．

B - Treasure Searching Rod (Easy)（★1.5）

• AC人数：109人
• First AC：uwiさん（2:50）

素直に全探索をすれば解ける，基本的な問題です．

この問題，F問題と同じ設定の問題で，制約が小さい問題となっています．このように，制約が違う難しい問題を出題する，ということができるのが単独コンのメリットだと感じています．序盤でAC数がなかなか伸びなかったのですが，F問題と同時に通そうとした人が割と多かったからかもしれません．このような出題方法は目の前の問題を通す上での障壁となりうることに気が付いたので，今後は注意しようと思います．

C - Hello, Forgotten World!（★2）

• AC人数：78人
• First AC：nok0さん（5:16）

文字列の問題です．ただ，この時点では特別な文字列アルゴリズムなどは必要とせず，「辞書順最小」についての構造を把握し，少し考察を行えば比較的容易に解くことができます．

また，この問題には噓貪欲が存在し，「できるだけ後ろに helloworld を置いたほうが良い」というものです（「helloworl??????????」で落ちます）．この噓貪欲をやった場合はサンプル以外全てWAになるようにしました．

多少はこの噓貪欲にハマる人がいるかもしれないとは想定していたのですが，（特に序盤で）想定以上に引っかかった人が多かったです．

D - King Kraken's Attack（★2.5）

• AC人数：63人
• First AC：jianglyさん（17:16）

このあたりから考察の度合いが増えていくと思います．一見すると難しい問題に見えるかもしれませんが，「倒せる敵の数が と にしか依存しない」ということに気づければ割とその後の手も見えやすいのではないかと思います．

問題の説明文に誤りがあり，コンテスト中に訂正させていただきました．大変申し訳ございませんでした．

結構WAを出されている方が多かったのですが，例えばなどの場合の例外処理をしていなかった場合に落ちるようです．

E - Creeping Ghost（★3）

• AC人数：57人
• First AC：yupiteru_kunさん（16:58）

構築問題です．グリッドを移動するタイプの構築問題を出題したいと考えていたら，なかなか他では見ないタイプの構築問題が生えたので，出題することにしてみました．特別な知識は必要とはせず，色々と移動パターンを実験すれば解けるタイプの問題になっています．Writer解は外周をぐるぐる回り続ける，というものでしたが，Tester解はDFSによって移動パターンを構築する，というもので，私も想定していなかったものでした．

基本的には外周をぐるぐる回る解が多かったように思いますが，Tester解のようなギザギザ移動を考えられた方も多くいたように思います．

F - Treasure Searching Rod (Hard)（★3）

• AC人数：58人
• First AC：jianglyさん（8:52）

Bの制約強化版の問題です．

主客転倒をすれば解けます．寄与ぶんの計算に等差数列の和の公式を用いる必要があり，そこが少し難しかったかもしれません．

基本的には角度を変えることなく主客転倒で解いている方が多かったように思いますが，たまに45度回転をして解いている方がいました．しかし，そちらの方が実装が難しいと思います（偶奇を考慮する必要があるため）．

G - Good Omen of White Lotus（★3）

• AC人数：43人
• First AC：maksimさん（14:07）

「最も確率が高くなるように移動方法を選ぶ」タイプの問題を出題したいと思い，確率の式についての考察と，その後の平面走査＋セグ木DPが必要な問題が生えたので出題しました．

当初は平面走査＋セグ木DPと，高度なことが要求されると思っていたため，★3.5を想定していたのですが，テスターさんが★3を主張されていたので★3で出題しました．解かれ具合を見てもこれで正解だったように思います*1．また，全体テスターさんに「LISで解ける」とのご指摘を受けるまで，LISで解けることに全く気付いていませんでした．「もっと簡単に解ける解法はないか」を普段から考えることが大切だと思い知らされます．

また，当初は だったのですが，「非本質な座圧は良くない」と思い，コンテスト1週間前に今の制約に変更しました．特に意見も出ていないですし，変更して正解だったと思います．

H - Surprising Flash!（★4.5）

• AC人数：15人
• First AC：hos.lyricさん（25:12）

当初はこの問題は予定されておらず，G問題までの7問で出題予定だったのですが，akakimidoriさんから「C問題の設定を一般化したものがより制約が大きくても解ける」というご指摘を頂き，なかなか面白いと思ったため出題してみることにしました。

解法は，「ワイルドカードマッチング」と呼ばれる手法とSA + LCP を用いて辞書順比較を行う手法を組み合わせるものであり，高度典型の力も考察力も両方ともものすごく高い水準で要求され，非常に難度の高い問題となっています．

私自身，よく言われる「ボス問」の概念はあまり好きではないのですが，このようにセット中に一つだけ抜きんでて難易度が高い問題が生えてしまい，事実上のボス問となってしまいました．

非常に難度が高く，何人ACできるのかと心配でしたが，最終的に15人もの方にACしていただけました．おめでとうございます．

おわりに

思いがけない超高難度の問題が追加されたことで自分でも不安でしたが，最終的に全完が10人現れ，レベルの高さを思い知らされました．全完された方はおめでとうございます．

開催する側としても非常に楽しかったです．また機会があればこのような単独コンテストを開いてみたいものですね．

*1:難易度投票を見ていると「★2.5」が何件かありましたが，流石にそこまで簡単と言われることは全く予想していませんでした．