Programming Coontest

競プロなど

yukicoder contest 417 感想

はじめに

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

A - Fee Schedule（★1）

  • AC人数：131人
  • First AC：hitonanode さん（0:20）

最初の問題です．例によって，コンテストの最初の問題は，★1，それも ABC-A レベルの問題を置きました．

予想はできていたことですが，最初の1～2分にACが集中していました．

B - Dam（★2）

  • AC人数：110人
  • First AC：hitonanode さん（3:09）

仕組みが単純で考察もしやすく，しかし注意しないと間違える数学の問題です．

周期性という，よくある考察を題材としています．これをもとに，グラフの形をイメージできれば，正解にぐっと近づくでしょう．

WAが大量に出るかなと思っていましたが，そんなことはありませんでした．上位陣は何の迷いもなく通すのだと思うと，処理力の高さを思い知らされます．

C - Room Allocation（★2.5）

  • AC人数：90人
  • First AC：hitonanode さん（6:39）

少しの考察要素あり，しかしそれでいて問題の構造をよく観察すれば正解に一気に近づくタイプの問題です．

このタイプの問題は過去に ABC でよく出ていた時代もあったものですが，最近ではあまり見なくなってしまったと思っています．

正解数が思った以上に多かったです．こういうのはやはり正しく処理できる人が多いのでしょうか．

D - Prediction by Average（★2.5）

  • AC人数：62人
  • First AC：maspy さん（10:47）

平均値を題材とした問題を作りたいと思っていたら生えたので，出題してみることにしました．

平均値が人数に応じてどのような挙動をするか考えれば，正解には辿り着きやすかったかと思います．なお，制約の「 10^{13} 」は「N × S を（S を 1000 倍して整数型に直したもとで）オーバーフローせずに計算できる範囲」という理由だけで定められたものであり，言ってしまえばただのブラフです．

当初はこれが★2で，しかも C 問題に置かれる予定であったのですが，各問テスターさんの指摘によって★2.5に引き上げられ，また全体テスターさんのご意見によって現在の C 問題と順番が入れ替えられることとなりました．正解者は思ったより少なく，またそうでなくても正解までに時間がかかっていた人も多いように見受けられ，個人的には意外でした．

E - Bonus Ai（★3）

  • AC人数：70人
  • First AC：hos.lyric さん（4:25）

かなりオーソドックスな数え上げの問題です．DP で数え上げを行う，という方針は制約を見ても立てやすいかもしれませんが，どのように遷移させていくか，という点が腕の見せ所です．また，DP の高速化を累積和やいもす法で行う必要もあり，それなりの典型力も同様に必要とされます．

各問テスターさんから， N \leq 10^5 で解ける解法を提案していただきました（経路数の数え上げに帰着させる，というもの）．しかし，遷移の部分が本質であると考え，今回は導入しないことにしました．

正解数は思った以上に多かったです．

F - Similar But Different Name（★3.5）

  • AC人数：39人
  • First AC：hos.lyric さん（14:00）

ABC などでしばしば登場するような，文字列照合の問題です．文字列を良い感じの性質を満たすハッシュ値に置き換え，そのハッシュ値のもとで畳み込みを行うことでスコアを高速に計算する，という流れを踏む必要があり，非常に高い知識・考察力が要求されます．

当初はこれが G 問題で，また難易度も★4に設定されていたのですが，各問テスターさんから「解法に辿り着くまでのアプローチが様々ある*1」というご指摘を頂き，難易度を★3.5に下方修正しました．また，全体テスターさんもこの問題は早い段階で通されており，「F 問題と G 問題の順序を逆にすべき」とのご指摘を頂いたため，この問題が F 問題に置かれることとなりました．

実際この問題の正解数はかなり多く，逆にして本当に良かったです．

G - Unnatural Pitch（★3.5→コンテスト終了後に★4に変更）

  • AC人数：8人
  • First AC：maksim さん（30:47）

前回，前々回と最後に数え上げの問題を置く回が続きましたが，今回の最後の問題は最適化です．最適化の問題を考えていたところ，この問題が生え，「気づき」が重要な問題として良いと感じたため，出題を決めました．

「端より真ん中でそろえたほうが良い」ということは，直観として比較的働きやすいかと考えていますが，それを「どのように評価できるか」に気づけるかどうかが，ポイントだと考えています．これに気づけるか気づけないかで，正しい解法に辿り着けるかが大きく変わってきます．

AC数8人は完全に予想外，また想定解と同じ解法だったのは，見た限り ygussany さんのみに思われました（他はセグ木や遅延セグ木が多い）．想定解はかなり綺麗な形になるので，ぜひ考えてみてください（セグ木も遅延セグ木もいりませんが，それでも実装はやや面倒かもしれません）．

おわりに

前々回は全体的に易しめ，前回は後半が難しめのコンテストだったため，今回はその中間くらいの，易しすぎず難しすぎずの難易度を心掛けたつもりでした．しかし，最終問題の正解者数が私の作成した問題の中で過去最低になってしまったのが予想外でした......．

また，今回はコンテスト終了後に解説風の動画を作成しています（yukicoder contest 417 にゆっくりが挑戦する【ゆっくり茶番・ゆっくり解説】 - YouTube）．動画は視覚的に問題の解法を表現するのに非常に便利な媒体であり，個人的に競プロの解説には非常に適していると考えているのですが，現状ではこれを実践している例はあまり多くないです*2．そこで，今回は新たな試みとして，動画も作ってみることにしました．競プロ動画の方式は様々あり，多くの動画投稿者さんが十人十色のスタイルで行っているのですが，その中でも私が好きで作ってみたかった，「ゆっくり茶番」スタイルを，今回は取り入れてみることにしました．

さて，私はかねてからとあるオンサイトコンテストの運営に携わっていることを，各所において明かしています．その報告ができる日も，もうだいぶ近いかもしれません．

*1:具体的には，先に大文字・小文字不問のマッチングを下準備として行ってしまえば，あとは「大文字か小文字か」しか気にしなくてよくなるため，ハッシュ化が容易になる，というものです．

*2:定期的に行われている例としては，evima さんの YouTube チャンネルなどがあります

第2回緑以下コンテスト/緑以下コンテスト Extra 感想

コンテスト本編へのリンクは こちら

コンテスト Extra へのリンクは こちら

本編F - 数字探しゲーム（緑以下コンver.）（茶色）

  • AC 人数：58人
  • FA：ecottea さん（12:08）

「コンテストに典型そのままではない問題がもう少し欲しい」というモチベーションで生やした問題です．簡単めではあるものの，しかししっかりと味のある構築問題を目指して作りました．

「数字の数」に対する制約と，「倍数」に対する制約をどのように扱うかがカギを握ります．「数字の数」に対する制約が桁数に比べて多くないことに気づけるかどうかが重要でした．

コンテスト中の序盤から順位表に不穏な様子を感じ取り，「これは一旦飛ばして後で戻ってくる人が多いから，一時的に AC 数の逆転が起こっているだけだろう......」と思っていたところ，逆転は縮まるどころかむしろ広がるばかりで，最終的に H 問題や I 問題，さらには K 問題よりも AC 数が少ないという始末になってしまいました*1．コンテスト内最大の虐殺枠となってしまい，申し訳ございません．運営陣も「この位置で良い」という意見が多く，この手の問題の難易度を正しく見積もることの難しさを痛感させられます．

本編J - 美しい整数列（緑色）

  • AC 人数：39人
  • FA：seekworser さん（6:56）

以前からストックのあった問題で，緑以下コンテストの開催が決まったため，ここで出題することを決めた問題です．

個人的に，この問題で大切なのは「問題文の条件から構造を見抜くこと」だと思っています．「一つが決まれば他も自動的に決まるので，その一つをどこに定めるのが良いか」を見出すのがこの問題のカギです．

この問題についても難易度推定を誤ってしまい，茶色上位から緑下位くらいだと思っていたのですが，F 問題ほどではないにしても虐殺枠となってしまいました．コンテスト後に，似た出題が過去の ABC にあったことを言及されていました（ABC255-Eが，その問題の存在にも difficulty（水上位であった）にも準備段階では気づくことができませんでした*2．似たような出題がないか，その問題の difficulty はどの程度かは難易度推定に非常に重要な要素なので，まずはそこを意識することの重要性を思い知らされました．

ExtraB - 最大最大公約数（★2.5）

ジャッジを準備したのは ragna さんですが，原案は私であったため，当記事で紹介しておきます．

約数の個数の少なさを利用する問題は，過去のコンテストにも多く出題されています．個人的にそのアプローチが好みなこともあり，原案を投げたのですが，難しめなこともあってか Extra コンテストとして出題されることになりました．

Extraコンテストの中でも序盤にあったこともあってか，コンテスト時間中に解いてくれた人も多く，原案を出した私としては嬉しいです．

おわりに

前回 MojaCoder で開催されていた「緑以下コンテスト」が，プラットフォームを yukicoder に変更し，さらにオンサイトを開催するなど，進化を見せました．進化した緑以下コンテストのオンサイト運営に携わることができ，非常に嬉しいです．今後も開催されるのであれば携わりたいと思うようになりました．

反省点としては，何と言っても私の作問が見事に虐殺枠となってしまった点ですね......緑以下コンテストの他の方が出している原案は典型一発のものがかなり多かったのですが，私はそれを見て「よりコンテストを面白いものにするため，典型一発とはいかないものも生やしたい」と考えていました．その結果本編に上記の 2 問が出題されることとなりました．「面白かった」という意見が多く，その点では準備した甲斐あったと思いましたが，（AC 数の問題のみならず）セットの中でそこだけ「浮いてる」という指摘を受け，もしや良いことばかりでもないのかもしれないと思い知らされました．今後のオンサイトに出題する問題のあり方を考えるきっかけにしたいですね......．

さて，私は既に将来的にとあるオンサイトコンテストの運営に携わることが決定しています．そのときが来れば X でも報告ができると思いますので，そのときまでご期待を......

*1:コンテスト中の AC 人数ですが，H 問題が 90 人，I 問題が 95 人，K 問題が 70 人と，いずれも F 問題の 58 人より大きな差がありました......

*2:尤も，この問題に関しては偶奇で符号を反転する必要がある，値の候補を複数考える必要があるなど，さらに一段階難しい要素があるのですが......

yukicoder contest 411 感想

F - Yellow Cards（★3）

  • FA：遭難者さん（9:34）

「イエローカードの性質を競プロの問題にできないかな」と思っていたら，ふと生えた問題です．それなりに上手い感じの設定になってくれたと思います．

高難易度にありがちな，状態の持ち方を工夫する必要のある DP の問題です．応用的な考察が必要なこともあり、当初は★3.5を提案していましたが、テスターさんに★2.5～★3を主張されたため修正しました．AC 数が想定よりもはるかに多く，変更して本当に良かったと思います*1．

想定解法は O(NK) の DP ですが、テスターさんから O(\log K) 解法が提案されたため，解説において Bonus. で記載してあります（★4.5～★5相当？）．

G - Coloring Vertices on Namori（★3）

  • FA：risujirohさん（8:37）

私が作問を始めた初期（1年～1年半前？）の頃から作問ストックにあった問題です．かなり典型寄りの問題であり，単独コンテストに回すような問題でもなかったため，どこで出題しようか......と，出題する機会を伺っていたところ，オムニバスコンテストが開催されるとのことで，ここで出題を決めました．

当初は K \leq 10 だったのですが，後で「別に K が大きくても普通に解けるよね」ということに気づいたため，今の制約で出題しています（なぜ最初から気づいていなかったんだろう......）．

おわりに

意図したわけではないですが，2 問とも 998244353 系統の問題にしたところ，ほかの方の問題にも 998244353 系統が多くてびっくりしました．こういう回もあると思います．

ところでこの回の D,E はかなり難しいと思うんですが，私だけですか？（どちらも解くのに1時間くらいかかっている......）

*1:ちなみに難易度投票ではまさかの★2.5が最多でした．私の中でもけっこうな大誤算だと思っており，反省点としたいです．

緑以下コンテスト 感想

コンテストへのリンクは こちら

I - Knight （緑-1）

かねてから低難度のストックとして作ってはいたものの，どこに出して良いかがわからなかった問題でした（設定がありふれていすぎるように感じてしまい，yukicoder に出すにはかなり躊躇われた）．そんな中，緑以下コンテストの Tester をやらせていただくこととなり，せっかくなら Writer もやろうかなぁと思い，出題させていただくことにしました．

実験をすれば「ある程度の大きさからはすべてのマスに行けるだろう」と，法則性が見えやすいです．が， H=3, W=3 のときに注意が必要です．実際，この 1 ケースだけ WA の提出がかなり多かったです．

難易度感覚としては，緑の簡単目の問題だったのですが，実際難しすぎず簡単すぎずで置く位置も間違っていなかったように思います．

おわりに

今回，yukicoder ではなく MojaCoder での開催となり，共同でのコンテスト開催も初めてのことで，不具合が起こらないかと色々不安な面もありましたが，皆さんに楽しんでいただけたのが嬉しかったです。

あと，yukicoder 並みの人数が参加してくれているのを見て，びっくりしました．影響力がすごい......

yukicoder contest 401 感想

はじめに

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

A - Bouns 2.0（★1）

  • AC人数：118人
  • First AC：hitonanode さん（0:40）

最初の問題です．今回も，多くの人に解いていただけるよう，前回，前々回のコンテストと同様に 1 問目は ★1 レベルの問題を出題しました．

基本的な四則演算ができれば解ける，ABC-A レベルの問題です*1．

B - Lakes and Fish（★2）

  • AC人数：107人
  • First AC：SSRS さん（3:19）

考察をもとに，二分探索を用いることができるかを問うた問題です．

普段よく ABC で見るタイプの出題のされ方とはやや異なる出題の仕方をしたつもりではありますが，それでも ABC-D レベルくらいだと考えています．

こちらも多くの人が解けていました．この問題をコンテスト参加者の 9 割弱が通していることから考えると，yukicoder に出る層のレベル帯の高さを改めて思い知らされます．yukicoder はもっと有名になってほしいものですが......　MMA Contest などが yukicoder を利用しているので，これで yukicoder の知名度が上がることに期待したいものです．

C - Strange Werewolves（★2.5）

  • AC人数：99人
  • First AC：potato17 さん（3:41）

今まで出題した問題の中でもかなり数学要素の強い問題です．「最後の 1 人さえ固定すれば残りはどの順番でもよい」ことに気づくことができるかどうかがカギとなるように思います（個人的に競プロで見る頻度はあまり多くないように感じており，どのくらい典型なのか......と思うことがありました）．

想像以上に多くの人が解いていたように感じました．この手の数学も得意の人が多いのでしょうか．

D - Nine Numbers（★2.5）

  • AC人数：89人
  • First AC：KumaTachiRen さん（1:31）

入力が与えられない考察問題です．ほかのコンテストサイトも含めて，このような出題は最近ではかなり珍しいのではないでしょうか．

かなり思いつくのが難しいように思うかもしれませんが，「できるだけ少ない要素の数で全ての値を網羅できるにはどうすればよいか？」と考えていけば，n べきを用いる発想になりやすいと思います．

テスターさんから「実際の操作列も出力させたほうが面白くなる」という声を頂いたのですが，「後半の難度を考えるとここは軽くしたほうが良い」という判断で，導入しないことにしました．後半の難度を考えると，導入しなくて正解だったように思います．

また，コンテスト後の TL で指摘があったのですが，「平衡三進数」なる考え方があるようです．一部の人にとっては，かなりの有名事実だったのかもしれません．

E - Reverse Directions（★3）

  • AC人数：42人
  • First AC：rin204 さん（20:57）

このあたりから，考察実装ともに難易度が上がってきます．

D に引き続き構築問題ですが，こちらは割と理詰めで正答に近づいていけるタイプの問題だと思います．

当初は ★3.5 で企画していましたが，全体 Tester さんが ★3 を主張していたため ★3 に落としました．★3.5 でも良かった気もしますが......投票を見る限り★3 と ★3.5 の中間くらいなので，ここに関してはどちらでもよかったかもしれません．

特にこの問題は実装量が非常に多く，今回のコンテスト時間を 150 分にした一つの要因でもあります．コンテスト後も「実装が多い」という声をよく耳にしたものです．ここに関しては申し訳ないというほかありません......．

F - YOU Grow Bigger!（★3.5）

  • AC人数：33人
  • First AC：to-omer さん（14:00）

今回の問題の中でも特に考察一発要素（いわゆる「ギャグ」）が強い問題です．このような問題を出題するのは今まであまり無かったのですが，今回は出題してみることにしました．

「答えは必ず 2 以下になる」ということに気づければ，考察が一気に進みます（というかほとんどそれに尽きます）．

また，最短路に帰着させて解いている人もいましたが，こちらとしては最短路の解法は全く想定しておりませんでした．

G - Multiple of 99（★4）

  • AC人数：14人
  • First AC：hos.lyric さん（29:03）

今回も，前回に引き続き最後の問題は数え上げです．「形式的べき級数」と呼ばれる高度典型を用いる問題であり，今回のセット内でも特にハイレベルな知識が要求されます．これにより，知識も考察も高い水準で要求される非常に難度の高い問題となってしまいました．

元々は形式的べき級数が不要な別の設定の問題（★3.5相当）だったのですが，その設定だと落としたい解法が通ってしまうことがわかり，現在のような設定となりました．そのことで，形式的べき級数が必要になり，元々の問題に比べて一気に難易度が上がり，はからずも今回のラスボス枠を飾ることとなってしまいました．

それでも最終的に 14 人が通しており，また最終的に 9 人が時間内に全問正解をしていました．おめでとうございます．

おわりに

前回のセットが思った以上に多くの人に解かれたため，今回のセットは特に後半の難度を高くしました．それでも多くの人に解いていただけてたいへんうれしかったです．

yukicoder のみならず，ほかのコンテストサイトでも作問をしたい気持ちになるものです（個人的に UTPC に問題を提供したい気持ちが強い）．

*1:今の ABC-A は難化傾向にあることを考えると，それより簡単まであるかもしれません......

はちじ　作問集

はちじが作問した問題をまとめてあります．

典型か ad-hoc か，また難易度の値については，独断で決めています．

簡単枠

問題 難易度 コメント
Four Seasons 100 yukicoder で作問した中で，最も簡単な部類の問題です．
Fee Schedule 100 簡単な算数の問題は，いかがですか？
Bouns 2.0 100 上同様，ABC-A レベルの問題です．
UFO Game 200 若干処理が面倒ですが，それでも ABC-B レベルです．
Treasure Searching Rod (Easy) 250 制約強化版が 525 点にあります．

典型枠

問題 難易度 コメント
Addition and Multiplication in yukicoder (Easy) 300 割と直感通りにやってもできるかも．
Hello, Forgotten World! 400 意外にハマる人が多かったです．
Butterfly in Summer 400 これが ABC-D に出題されたら今はどれくらい解かれるのだろうか．
Lakes and Fish 400 これくらいなら多くの人が軽く通してくるんですね......．
DAM 425 算数を頑張りましょう．どこかで見たことあるような気もしますが，出所知らずです．
Sharpened Knife in Fall 450 こういう「競プロで図形の問題を解く」というのは個人的に好きです．
Strange Werewolves 450 競プロにそのままの形がほとんど出ていないこともあり，典型度がイマイチつかめない．
Nine Numbers 450 Writer が知らなかっただけで，名前までついているくらいの典型だったらしいです．
Room Allocation 450 あんまり最近の ABC にこういうの無い気がします．どう書くかは人によってけっこう分かれそうです．
King Kraken's Attack 475 方針は浮かびやすそう？
Prediction by Average 475 問題の設定から「ある性質」を見出しましょう．こういう制約ブラフは今後もやっていきたいです．
Concon Substrings (COuNt Version) 500 難易度の割にやたらと解かれたのを覚えています．
Bonus Ai 500 シンプル・イズ・ベストとも言うべき問題です．こういうのを ABC にもっと出してほしい，そう思います．
Treasure Searching Rod (Hard) 525 Easy 版の制約強化．できるだけ楽な方針を選びましょう．
Poor Sight in Winter 525 この手の「典型詰め合わせ」問題は個人的に作りたい種類の問題です．
Unhappy Back Dance 525 制約の決め方の苦しさを思い知らされた問題．
Coloring Vertices on Namori 525 作問当初に生えた問題．ド典型で，出し所がわからずに約1年半温めて，結局オムニバス回で出題することにしました．
Good Omen of White Lotus 550 テスターさんに指摘されるまで楽な方針に気づかなかった悲しみ．
Yellow Cards 550 解法は予測しやすいが，工夫が必要で，そこにひと考察必要かと思います．
Addition and Multiplication in yukicoder (Hard) 550 こちらは適当にやろうとすると失敗します．
Black Market 575 実装量がかなり多め．
Back Door Tour in Four Seasons 575 最終的な結果がかなり綺麗な形になる数え上げの問題だと感じています．
Concon Substrings (ConVersion) 600 名前の付け方が個人的にだいぶ好みです．作問当初の頃にこれを生やせたの自分でも何故？という気持ち．
Similar But Different Name 600 これ今 ABC に出されたら下手すりゃ黄 diff 割るまであるのでしょうか......．
Surprising Flash! 650 akakimidori さんによって提案していただいた，Hello, Forgotten World! の超強化版です．知識も実装もなにもかも本当に難しい！

ad-hoc 枠

問題 難易度 コメント
数字探しゲーム（緑以下コンver.） 300 第2回緑以下コンテスト最大の虐殺枠．ad-hoc 入門には良い問題だと思っているので，ぜひどうぞ．
Symmetry 400 ad-hoc めの問題の中でも特に簡単な部類だと思います．
Knight 400 実験で答えを導きやすい問題......ですが，コーナーケースに要注意！
美しい整数列 400 問題の構造をイメージできるかどうかが，カギを握ります．
Concon Substrings (Swap Version) 500 私が最初に作問した問題です．
Guardian Dogs in Spring 500 思いのほかかなり評判が良く，個人的に嬉しかったです．意外とこういうの出ていないんですね......
Creeping Ghost 550 色々な解法があるので，お好みで．
Concon Substrings (COuNt-CONstruct Version) 600 既出に気づかずに出題し，終わった後に指摘されて悲しくなりました．
Again Make UTPC 600 UTPC に出題した気合いの実装です．とにかく重いです．私自身の当初の想定解も間違ってました．
Reverse Directions 650 考察は割と理詰めでもどうにかなりますが，実装がとにかく重い！
Rage With Our Friends 700 ある考察が鍵となりますが，それを乗り越えたところで実装量も多く，かなり苦しいです．
YOU Grow Bigger! 700 「ある事実」に気づくことが答えにほぼ直結します．ただ，別解もあったらしい．
Unnatural Pitch 750 まさかの yukicoder 初の本番 AC 数一桁を記録してしまった問題です．高度なデータ構造で殴った人が多かったですが，想定解ではそれらは不要で，（それでも実装は重めなものの）綺麗に書けます．
Multiple of 99 850 原案が強化された結果こうなりました．知識も考察も超高度に要求されます．

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 させようと考えました．その結果， N \leq 8000 という制約になっています．（ジャッジに O(N^2) かかるため，これ以上は安易に上げられません）

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）

図形の問題です．

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

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

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

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

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

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

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

おわりに

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

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

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