あめんばーどのバーチャル日記

バーチャルな世界で過ごして競プロしてる人の雑談

yukicoder contest 414 振り返り

390みたいに複数に分けたりせず、とりあえずいろいろとまとめて振り返りです
例によって他人に読ませると言うよりは、自分の考えをまとめるための書きなぐりなのでいろいろ崩壊しています。



ぶっちゃけ「コンテストを作りたい！」というよりも「これ面白いから問題にしたい！」で暴走しすぎちゃったなぁ、な感じでした。
前回(390)はH問題が浮かんだ後にtesterの人にすごい褒めてもらえたのでちゃんとコンテストとして形にしたい！…って思ってH以外は結構シンプルな問題や解いてほしい典型を考えて作ったのですが今回は………

B「４！！！！！！！！！！！！！！！！！」
D「比で解くとお得だぞ！！！！！！！！！」
H「PalindromicTreeだいすき！！！！！！！！！！！」

だいたいこんな感じでしたよね。
Fも知名度が非常に高い割にAtCoderであんまり見ないから（競プロ部での勉強の機会の為にも）投げたいなぁって感じでした。
ACEGは一応前回と同じノリにはなれたと思います。Eが難しすぎるのもわかってたけど。

前回と同じノリとはいえ

AC「ぼくらは同じノリです」
E「実質ボス問です」
F「配置に悪意を感じます」
G「典型一個じゃなくて典型3,4つくらいの組合せです」

結果A問題とC問題と一応F問題以外良心がいなくなりましたとさ（ABC三完大量発生）

うん、反省します。


Hが超弱体化してたので、まあ大丈夫かな～と思ってしまっていたところで2時間30分延長進言してくださったseekworserさん本当にありがとうございます。
というかそれ抜きにしててもTesterの皆様には本当に頭が上がりません。今回も私のわがままにお付き合いいただきありがとうございました。

総評 and 予想

一応前回と比べてD超強化、E強化、F弱化、G強化、H超弱化と見込んで、まあ均一は取れてるかなと思ってました。なおEが超強化枠だった模様。
Hを知ってれば青色の人でも全完全然あると思ってました。なかった。ごめんD。ごめんE。
DとEのTesterを分けていたのでseekworserさんが全部通してくれるまでは特にやばさの言及がされていなかったのですが、全部通してくれたあとにモノスゴイ悲鳴が来る。

通しTester、負担が大きいので気が引けてたけど、だいじ。

通しTesterしてもらえたあとは僕はこの問題セットがラヴォス第三形態に見えてました。真ん中の攻撃力がやばいので右を倒しましょう。

A : Summer Project

といいつつA問題から全力でふざけてるんですけどね。前回よりもVRChatやってない人完全に置いてけぼりのネタです。逆にVRChatやってる日本人の方でこの問題の意味がわからない方は是非とも遊びましょう。
VRC競プロ部にはなぜかこのワールドのRTA走者がおり、片方は部長で片方は元世界一です。
y23586.net

解法的には頭文字だけでも判別できる問題なのでA問題大喜利が捗りますね

B:Avator Height

Avatar Heightでした。なにしとんねん。反省の意味も込めてこのままにしておきます。
998244353練習問題。事前計算をしておくとお得だよって問題。ちょっと難しいかな。あと教育的な理由として行列累乗の話ができるので個人的にはそこもお得だなと思って編集した。
オマケ&救済としてO(Q)解法が存在する。
そしてWriterがコードゴルフに走り出すという始末。やりたい放題である。本当に僕一人だけが勝手に楽しんでただけでしたね。
そりゃ、うん、僕でも本番で証明の面倒くさい数列には走りませんわな。
いやWriterとして書いておいてなんですが、未証明の数列に手を出すのは博打なんで、できればおやめください。原因不明のWAになったら詰みだし、それでACして放置すると理解の機会を失っちゃいます。コンテスト中勝てばいいは私は肯定派なのですが、せめて終了後証明を理解はしましょう。（解説にも書こうと思ったがやめておいた）
もちろん数列の特徴を理解しないと解けない問題もあると思いますので、そういう時は大事ですよ。そういう問題作りたいね。
ちなみに本番中にこのギャグを通した人はパッと見3人だけいました。（あと「気づいてたけど普通にやった」とポストした人が一人）

この問題、最初は却下される前提とTesterの反応が見たいという理由だけでN=1e18で出して長文お気持ち表明が来ました（当たり前すぎる）。完全に相手がテッドさんだからやってました。この辺りもかなり反省点。seekworserさんが見た時点では現在の制約でした。
うーん、調子乗り過ぎた。

解説のオマケについてはTesterの人が追記してくれた内容でほぼおしまいです。

C:Very Poor

まあこれはドドドドド典型なんじゃないでしょうか。
円環は二周分で考えましょう、二分探索か尺取り法を使うと解けるよ、一周よりも多い要素を取らないようにね。
このセットの最後の良心と言えばそうなります。

まあ結局ふざけてるんですけどね。

D:Real Collider

戦犯。いや、本当にごめんなさい。何を言っても言い訳にしかならない。
ググれば公式出てくるしPythonならFractionと多倍長で殴り放題だからPython超有利問題のC++いじめ虐殺問題ですね～くらいに思ってたんですがPythonでも死者が大量に出るわ最上位勢の人もWA祭りするわで、Writerの思ってた倍くらいの虐殺になってしまいました。Testerは予想の範疇だった模様。
このコンテストが行われる一週間くらい前のABCで言語格差の話題で競プロTLがちょっと荒れてて「このDが控えてるところにその話題やめて～」って思ってたのですが、それ以前の問題でした。
三角比と有理数の再帰比較を使えば4乗以内で解けるというのは以前競プロの問題を見ながら思いついて研究したことがあったのでそのまま出したって感じでした。すみませんでした。
聞いていることも何をやればいいかも単純ですし二時間半あればぼちぼち通す人いるだろうと思ってました。すみませんでした。
最悪128bit整数とかBigIntでもゴリ押せるしいいでしょと思ってました。すみませんでした。
Testerさんが「鈍角三角形も外接円にはならない」に引っかかってたので図を急遽作って置いてこれで大丈夫と思ってましたが感想ポスト見る限り皆さん引っかかってました。すみませんでした。
4乗以内に抑える解法をVRChatのWriter解説会で言った所某赤コーダーさんから「想定解難しすぎ」と言われる始末。すみませんでした。
Testerに出した時点では★2.5だったし（即★3昇格したし）実は最後の最後まで★2.5降格を悩んでました。すみませんでした。
でもテストケース作成は本気でブチ殺しにかかってました。探すのとても大変だったけどめちゃくちゃ楽しかった。すみませんでした。

一人くらいは幾何学マスターがいたり64bit整数でキメる人現れないかなと思ってみてたのですが、呟いてる方がおられました。感動。めちゃくちゃおもしろい。

あと解説会でドロネー三角形分割でちゃんと公式があったことが発覚。ドロネー三角形分割は前に仕事で使ったことがあるので懐かしいなぁとなった。


Dについては前回の390Dが逆詐称評価の嵐だったので、ちょっと難しくしようかなと思ってたんです。
だけど前半ボスだからシンプルめでみんなが辛いのって何かなと思って「幾何」だなと思ったんですね。それで以前研究したネタを放り込むことにしました。

すみませんでした。

E:Tone Correction

ここだけARC-likeで実質このセットのボス。使ってる典型的にこの位置にはなりましたが、Writer的にはGH含めこの問題が一番難しい。DにはヒヤヒヤしましたがちゃんとF＜G＜D＜Eになってくれて満足。
個人的には良問になったと思うので、前回Hほどではないですがこのノリを忘れずに作っていきたいなと思いました。
問題文の通り、色の改変をしているときに浮かんだ問題です。イラスト編集ソフトには選択した範囲の色相をグルグル回すような機能があるんです。
早速問題作成して「とはいえ、適当に階差を取ってDPすりゃ解けんだろ」と思ってましたが、あれ解けない。
小一時間お仕事しながら考えて階差をソートすればいい、と気づいて思ってたよりも面白くなってしまいました。

配置的にはかなり前の方に置かれたし最後まで★3.5昇格を悩んでいたのですがTesterと話して「青色でも十分挑戦できる内容」で★3据置になりました。そして橙diffになりました。

F:Initial Motion

ある意味このセットの悪意の象徴になってしまった。悪意はありました。
「390Gと同じノリ」「AtCoderで最小費用流を見ないので話したい」「前回の感想で『典型コンテスト楽しい』と言われた」を組み合わせてできた最小費用流そのまんま問題。
まあDとEが生まれた時点で典型コンテストではなくなってしまったのですが。
D問題が★3昇格したのを機に、全てが★3を名乗れるけどベクトルが全然違うので「じゃあ使う典型は一番難しいけど問題としては一番簡単なのを最後に置くか………」となった問題。
Tester陣も秒殺してました。

コンテスト中は「みんな………Fに気づけ………」と50回くらい念を送ってた気がします

作問研究したかった身としてはBellmanFord落としや負のDijkstra落としのケースを作るにはどうすればいいか………で結構楽しかったんで、そっちに振ったのもありました。この問題Pythonだとだいぶ不利でTL設定が地味に厳しかったです。

G:Pickup Parentheses

この問題は使ってる典型は上級気味なものでありますがかなり見えやすく、テクニックを3,4つくらい要求してます。今回のセットはEが一番の良問だとは思ってますが、教育観点から見るとこれも良問になったとは思ってます。
見た目の時点であまりにも「包除包除包除包除包除！」って感じがしてるのでそこを隠せたらなぁ……とは思っていました。
この問題もとりあえず包除原理から考えてもっと制約を厳しくできないかな？と考察していったら区間重複さえしなければ限界まで制約を伸ばせることができて楽しかったです。
やっぱりどこかでできそうかな？くらいの原案ベースを考えた後に自分で考察を重ねていくのが良いのでしょうか。

わりといろんな方向から攻められる問題だと思うのでテストケースの試行錯誤も結構楽しかったですね。
某998マスターを意識して作ったら998マスターに怒られてかなしい。

H:Mirror Relay

Palindromic Treeそのまんま問題。以前（と言っても3年前）VRC競プロ部でとある人から教えてもらって一緒に勉強したデータ構造。
当時はなんとなく理解しただけでもとても面白かったのですが、改めて研究すると意外と簡単な構造かつ面白い。でも関連問題を全然見ない。一応日本語の問題ではyukicoderで一問あったのですが、8年前の★5（投票は★4.5）だし、しかもこれはこれでそのままだし………とりあえず★4で出してもいいのか……？って感じでした。
ボスを名乗るのには遥かに弱いのは承知だったのですが、前回の390Hが奇跡中の奇跡だっただけで私がそうそう簡単にボスを作れるほどの実力などあるわけもなくっていうか8割くらいそれが理由であとは建前でこの構造もっと知られてほしい！って感じで作った持ち物検査問題でした。
当たり前のようにちゃんと理解してる人には秒殺されました………★3投票されたのはちょっとかなしい。まあ知名度の低さに便乗した感はあるので、多少捻っても二回目以降出したら★3.5以下には降格かな………とは私も思います。とりあえずPalindromic Treeのverifyになってくれたら嬉しいな。

ロリハで頑張る解法はちょっと考えてたけど面倒なのでやめてたら結構それで通してる人もいて、眺めながら勉強になるなぁ……と思いながら見てました。

振り返ってみて

ざっくり

  • 多倍長なら殴れる→そんなことはない
  • 問題の本質に含まれる悪ふざけは面白くないのでやめます
  • 問題の本質に関係ない悪ふざけは今後も続けます
  • 典型からそのまま問題を作るのはやっぱりわりと楽だがやっぱり瞬殺される
  • ちゃんと自分で考えると面白い問題に繋げられると思った
  • そして自分で考えるのに至るベースは自分が今まで解いた問題だなと思った

今回のEも前回のHも自分が感動した問題がベースに発展した問題だったんですね。前回Hならこれ＋TLでフォロワーが呟いてた問題組み合わせられないか？ってなったのが最初でしたし。
049 - Flip Digits 2（★6）
今回のEも問題名は忘れてしまったのですが階差で解く問題が面白かったのを記憶していたので「これは問題になるんじゃないか」って感じでした。

120人もの人の2時間半、Testerの3名に至ってはめちゃくちゃお時間を頂き誠に恐縮ではございましたが、私も今回大変勉強になりました。
今年はそんなに単独コンテストを作る予定はしばらくお休みかな～と思いますが、ちまちまといい問題が作れるように、ついでに橙になれるように精進していきたいですね。

ふざけすぎたり見込み違ったところはだいぶありましたが今回のセットは前置きで「作問練習させてください……」ということで作問の感覚の理解と言う事でご容赦いただけると……だめ？すみません……。

といいつつ最近KaggleとかRustとかデータ分析とか久々にアバター改変に夢中になってるのでどうなるかわかりませんがね！
ゆっくり人生楽しませてください。

本当にありがとうございました。