yukicoder contest 393 感想

はじめに

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

A - Four Seasons（★1）

• AC人数：142人
• First AC：sepa38さん（0:46）

最初の問題です．コンテストを開催するにあたり，より多くの人に解いてもらえるようにと，1問目は難易度のかなり低い問題を心がけようと思って，前回に引き続き簡単めの場合分けで答えられるレベルの問題を出題しました．ABC-A レベルなこともあってか，多くの人が正解していたように思います．

B - Butterfly in Summer（★2）

• AC人数：131人
• First AC：maspyさん（1:09）

簡単めの逆元計算を題材とした問題です．

逆元計算は難しいかなと思い，★2 で出題したのですが，予想以上に正解者が出ました．出題者の私が驚いています．

また，たしかに実装量こそ少ないものの，コンテスト開始後すぐに AC が大量発生し，その速さに驚きました．Concon Substrings (Count Version) でもこのような現象に驚いた記憶があります．

余談ですが，この問題を作成した 4 月頃に，「有理数 mod の出力方法で困っている」という話が Twitter で話題となりました．ちょうどその頃それについての理解を問う問題を作っていたことがあり，安易に言及できませんでした．

C - Sharpened Knife in Fall（★2→コンテスト後に★2.5に変更）

• AC人数：91人
• First AC：maspyさん（6:17）

図形を題材にした問題です．とは言っても，ただの数学の問題として解くのではなく，二分探索のアルゴリズムと組み合わせて解く点で「競プロの図形問題」と言え，個人的に好きな問題です．

これだけ設定が単純ならば，どこかしらで出てきてもおかしくはないように見えるものですが，少なくとも私が見る限りではこの題材そのままの問題は知りません．「ありそうでない」という問題だと感じています．

実装が重いものの，問われている知識そのものは単純で，方針も見えやすいため★2で良いだろう......と思っていましたが，予想より解かれておらず，この問題は難易度設定を誤ったかなと反省しています．

D - Guardian Dogs in Spring（★2.5）

• AC人数：84人
• First AC：heno239さん（6:23）

先ほどとは打って変わって，考察要素の強い問題です．

一見難しいように見えるかもしれませんが，実は解法は一発で，「ソートして隣接要素をつなぐ」です．

このような問題で大事になってくるのは，「次元を落として考える」ということです．この問題では 2 次元の場合を考えましたが，1 次元の場合を考えると，ソートしてから隣接要素をつなげばよいことは割とすぐにわかるはずです．実は 2 次元の場合に対してもこの解法が通用するので，この問題が解ける，というわけです．

グラフを考えて適当な基準での貪欲を考えるなどの下手な嘘解法が通りやすい問題ですが，こういうのはテストケースを増やしてもきりがないため，せめて制約を上げてグラフ解法を TLE/MLE させようと考えました．その結果， という制約になっています．（ジャッジに かかるため，これ以上は安易に上げられません）

E - Poor Sight in Winter（★3→コンテスト後に★2.5に変更）

• AC人数：80人
• First AC：maspyさん（14:13）

このセット内ではかなり典型要素の強い問題だと思います．最短経路問題と二分探索を組み合わせて解きます．

このように，複数のアルゴリズムを組み合わせて解くような問題は個人的にきれいな問題だと思っているので，今後も作りたいと思っています．*1

思ったより解く人が多くてびっくりしています．

F - Unhappy Back Dance（★3）

• AC人数：67人
• First AC：oteraさん（14:07）

図形の問題です．

偏角ソートの考え方を基本に，ベクトルの正規化を正確に行えるかを問うています．

小数で評価を行っている解法を落とすため，座標の制約を 以下と，非常に大きく設定しています．そのことが原因で，実装方針によっては 64bit 整数の範囲で計算できないかもしれません．また，64bit より上の整数を用いて実装し，TLE になってしまった方もいますが，これ以上 N を小さくしようものなら下手をすれば が通りかねないこともあり，この制約にせざるを得ませんでした．図形問題の制約の設定方法は難しいと思い知らされます．

G - Back Door Tour in Four Seasons（★3.5→コンテスト終了後に★3に変更）

• AC人数：45人
• First AC：hos.lyricさん（8:50）

今回の最後の問題は数え上げです．

主格転倒を用いて項をうまい具合にまとめあげると，きれいに因数分解ができる形になってくれます．また，「数え上げには期待値を考える」というテクニックもありますが，これも今回の問題と相性が良いです（Testerさんに教えていただきました）．

個人的にかなり難しい問題だと感じたのですが，コンテスト中に40人以上通されるとはまさか思いませんでした．この手の数え上げが得意な人が多いのかと思い，びっくりしています．

おわりに

今回は全問正解者が多く，結果的に多くの方に楽しんでいただけたコンテストになったかと思います．ただ，難易度設定を見誤るなど，まだまだ課題は残るものです．

単独コンテストを開くにはアイディア出しから作業までやることも多く，そう簡単にできるものでもありませんが，また開きたいものです．

*1:典型詰め合わせ問題という意味では，典型90問-089は個人的にすごく綺麗だと思っています．