...あれ、見えてますかね?
こんにちは、抹茶大好きまっちゃラテです!!
え~...すみません、話が苦手なもので、ブログも何を書けばいいかわからんですが...
今回、Mojacoder さんで開かせていただきました、私の単独コンテスト、Matcha Rate's Sakura Contest -MRSC- 🌸🍡 の、裏話やどんなことをやったのかなど、ここに記録していこうと思います!
えーとその前に...
私がコンテスト、または問題作成の際に心がけていることを記します。主に以下の 4 つです。
私としたことが、GTXC のやつも忘れてたので、ここに記します。
- ラテ流作問の掟目次
- 第一: やはり最初、問題作成
- 第二: ほぼ一番の難所である、想定解作成
- 第三: 大体ここでいつも精神を削がれる、テストケース作成+バリデーションテスト
- 第四: 「自分が必ずしも合ってるとは思うな」、Tester集め
第一: やはり最初、問題作成
はい。最初からむずいことが来ました。私もちょくちょく趣味で(!?)作問をしているのですが、「こういうテクニックを使った問題作りたい!!!」という気持ちで臨むと、大体最悪な問題ができてしまうのです (実は、単独で出した問題がそれに当てはまるのです...)。
私の個人の見解ですが、問題の思いつき方は以下の 3 つがあると思われます。
- 1: なんかネタが舞い降りてくるタイプ
- 2: なんか典型問題を少し変更するタイプ
- 3: なんか実験してみてこういう問題が作れそうタイプ
私の場合、圧倒的に 1 番が当てはまると思いました。大体ああいう問題は、学校の下校途中や、友達との会話をしている時や(!?)、なんか思い出を探っていきながら見つけるのです。まさに深さ優先探索ですね!!!!
...まあ、本当にこんなのったりした感じで作問することが多いです。経験を無駄にしないということは、このことなのかもしれません。
この際、典型テクニックはなるべく使わないような問題を思いつくことが多いですね...(だってすぐ見破られたくないもん!!!!)
ちなみにいうと、私の場合はGoogle Document で AtCoder の問題みたいなフォームで書いています。こんな感じ?↓ 題名はですね...ほぼセンスの光具合が優先されると思われます。私はでぃーぷえるTranslation君を用いてなんとかこんな感じになっています(語彙力
※ $K$ や $\le$ は LaTeX 記法をまねています。確かに数式はありますけど、私はそのフォントがあまり好きではないので使っていません!!
第二: ほぼ一番の難所である、想定解作成
ここも大事なところ。想定解がしっかりしてなければ、それはもちろんコンテストには出せません。これは当たり前です。
想像してみてください。
二分探索を必ず使わなければいけない問題に対して、想定解が "Binary Search!" を出力するだけのコードだったら、嫌でしょう?
なんなら、この想定解を作った時点でこれは噓解法であるかどうかを見極めないと、私のように大変な目に遭います(後半部分をご覧ください)。
まあつまりは、本当にコードの意味をわかっていないと想定解が間違ってるかどうか気づきにくいということです。なので皆さんは、緑色になってから作問をすることを、私自身から強くおすすめします(私自身への戒め)。
いや、もちろん緑色になれ!!!って言ってる訳ではないのです。
想定解の正当性を証明できるような知識さえ持ってれば、必ず質の高い想定解を作ることはできます!!!!!多分!!!!!!!
(言い方、自分は茶色コーダーのくせになんか上からですみません)
第三: 大体ここでいつも精神を削がれる、テストケース作成+バリデーションテスト
来ました。皆さん大好きのテストケース作成です!!!!
私が想定解が嘘かどうかは、大体ここで気づきます。いや想定解作成で気づけたらいいんですけどね...はっきり言いましょう。私には無理です☆
テストケース作成はどうしてるのかというと、以下のような目安になってます(必ずしもどのコンテストでもこんな感じとは言い切れないことに注意してください)。
sample
ケース: 問題の入出力例とまったく同じケースを作るhand
ケース: とりあえず考えられる入出力を手動で作るrand
ケース: とりあえず大きいケースを自動で作るcorn
ケース: 想定解でも引っかかったようなコーナーケースを作るadd
ケース: 後々見つかったコーナーケースを作る
...果たしてこれはここに書いていいものなのでしょうか?自分にはわかりません(指摘されたら消します)
手動で作るケースはまあ予想通りでしょう。問題は、自動で作るケースです。
例えば 100000 個の数値が与えられるような問題での作るケースを考えてみましょう。流石にこれは手動では、私だったら宇宙が終わるくらいかかります。
なのでこういうのは、皆さんご存じの「ぷろぐらみんぐ」を使って書いていくのです!!!
ほいでどうやってやるかって?
それは個人で調べてみてください!!!!!!!!!!!!!!!!!!!!!!(説明する気力がない人)
参考までに、ケース作りのサンプルコード(C++)を載せておきます↓
#include <bits/stdc++.h> #include <fstream> //file参照 #include <random> //乱数生成 #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; using urd = std::uniform_real_distribution<>; using ll = long long; int main(void){ //ここではメルセンヌ・ツイスター法を用いた乱数生成器を使用する int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count(); mt19937_64 rnd(seed); std::ofstream file; //ここに入力する対象でなんかする!!! /* * ちなみに、ファイル操作では * * file.open(S); (S は参照ファイル名) * file.close(); (今開いているファイル S を閉じる) * * で、乱数を使って入力を生成したいときは(型エイリアス宣言を使っているので少々見にくいですが) * * urd N(1,1000); * * と書きます!(これだと 1 から 999 までの実数値をとる!) * (つまり生成する数値は半開区間であることに注意!) * * で、乱数生成の際に、 * * file << N(rnd) << endl; * * みたいな感じで書きます!(これだと参照したfileに N(乱数) と改行を書き込む!!! * * もっというと、for文を使って一気にケースを作ることが可能!!!やばすぎ!!!感動!!!!!! */ }
ふぅ...ちょっと落ち着いていいですか?マジになりすぎました...(🍵ごくごく)
まぁ、上のプログラムにお世話になっております。メルセンヌ・ツイスター、名前がかっこよすぎる...!!!!!✨✨✨✨✨✨✨✨
第四: 「自分が必ずしも合ってるとは思うな」、Tester集め
え~私の見解としましては、これが一番精神を削がれることだと思います。
なぜなら、自分の想定解が噓解法であることを躊躇なく指摘されることが多いからです。
じゃあTesterさんが悪いのか!?というとそうではなくて、言い換えるとTesterさんは「良い問題にしよう、絶対嘘解法疑惑なんか生み出させないぞ!!」という気持ちで臨んでくれているので、Testerになってくれた方々には本当に感謝するべきです。
私も実際、" M から始まる 11 文字の人" から噓解法を指摘され、なかなか精神が安定しないときがありましたが、その出来事があったからこそ、こうやって素敵なコンテストを開催することができたのだな、と今でも思っています。
(ん、なんか段々趣旨から外れているような...?)
まぁ、一回そこは置いといて!
Testerさんを集める手段はいくつかありますけど、私はTwitterから自力で集めることがほとんどです!!!
あの時も、yukicoder さんに投稿した問題もあるんですが、実は。その時も最初はどうやって集めればいいかわからず、Twitterで集めている人を見かけたので見様見真似で私も同じようにして集めたのが、今でも続けてTwitterで集めているきっかけでもありますね...
あと、Testerさんとはすぐに共有できるように、なるべく Discord などのプライベートな空間で複数人で話し合えるようなところでやったほうがいいと思います!!!直接、個人個人でTesterさんに、ケース更新の報告や指摘の報告などを共有できないと、いろいろ手間がかかってしまうと思ったためです!!!!
#
...とまぁ、ここまで話しましたが、こんな感じでてんやわんやな問題Testをしていました。
ということで。実は、
ここからやっと本編に入ることを忘れないでくださいね?
(驚かせてすみません)
GTXC のうらばなし
去年(2022)に開催した、クリスマスコンテストでは、裏ではいろいろあったのです...
各問題ごとに記していきます!
ちなみに、このコンテストを開催しようとしたきっかけは...
”””興味""" です。
(じゃあこれ言う必要ある?ないです)
(あ、この先解法ネタバレ注意です)
A(#1) Red and Blue
A問題なので、まあ簡単目で。今回はソートに関するものにしました。連想配列でも解けますけどね...
まだまだ序盤なので、本棚をテーマにして作りました。
(今、問題文を見てみたんですが、ま~わかりずらいですね...すみませんでした...)
推定diffは 50 以下を目安にして作りました。
B(#2) Footprint
B問題なので、まだ簡単目...とでも思いましたか?^^
この頃の私は、「重実装の問題を何か 1 つ出してSolverさんたちを苦しめさせてやろうひっひっひ」と思っていました(最悪)
二次元グリッド問題が好きだったので、シミュレーション問題にしようとしたらこんな感じになっちゃいました。
実は、これはNを10^{18}にしても解けるな...とも思っていました。
Hard版も作ろうかな~と思いましたが、さすがにHardはいっか...ってなってこのような制約にしました。なんなら想定解がむずくて書きたくn (殴
ヒント: (白字にしてます)↓
連想配列でX座標Y座標を別々に持ってれば、クエリ 1 つ当たり二分探索でO(logN)で解けそう...?知りませんけど。
推定diffは 390 以下を目安にして作りました。
C(#3) Let's "Clone" It
C問題はなんかひねりました。なんかCチックな問題を作りたいな~と思って作りました。Bくらいでした。Dくらいでした。Cが作れません。助けて!!!!
と思ったとき、過去の自分が何か作っていたのでそれを参考に作りました。数学的思考ですねこれは。
多分、過去の自分もこういうの作れてうれしかった記憶があったと思います。
あと、Story上にnumDeer君と書きましたが、感のいい人なら多分突っ込まれますねこれ。あとは特に書くことはない!!!!!
推定diffは 500 以下を目安に作りました。
(このタイミングですみませんが、ケース更新しました。過去の想定解は嘘解法でした(今は修正済です))
(私の友だちが指摘してくれました。ありがと~!!!!!!)
D(#4) Pile The Integer Game
実は、とある実況者の実写動画を見て思い浮かんだものです。なんなら確か高2の2学期期末考査の真っ最中...?(勉強せい)
で、二分探索じゃないときついな~と思ってた矢先、愚直でも解けるという二段構えに心躍らされました(?)
まぁつまりはシミュレーションです。今見ると、テーマ被った~やっちゃった~って思いますけど、過去の自分はそんなことはとうに思ってないでしょうね...
推定diffは 700 以下を目安に作りました(にぶたんじゃないと無理と思ったため)。
E1,E2(#5,#7) A Most Popular Matcha's Snow Land
多分過去のツイートをあさっていただくとわかると思いますが、実はimos法に慣れていたときだったのです。その過去のツイートが見つからんです :(
最初この問題を思いついたとき、あのD問題を思い出しました。それもあって、Hard版が作れたんだと思います。ここでHard版の想定解がないのは、自分で解けなかったためでs (大殴
推定diffは、Easy: 700 以下、Hard: 1200 以下を目安に作りました。
F(#6) Playing Connection Woods
F問題なので、相当むずくしようと思いました。実は、最初この問題もシミュレーションのつもりで作っていました(過去の自分、テーマ被りすぎです)。
...と思っていると、なにか🍄の人がそっと手を差し伸べてくれて、その瞬間さわやかな風が心地よく吹き始め、
「おい、この問題、区間スケジューリングで、解けるぜ(イケボ」
と言ってくれたのです...!!! キャー!!!!かっこいー!!!!!✨✨✨✨✨✨✨✨
実は、過去の過去の自分は貪欲法大好きでいました。めちゃめちゃ嬉しかった覚えがあります。
推定diffは 1000 以下を目安に作りました。
#
こんな感じでGTXCは成り立っていました。違うテクニックでこの問題は解ける!!!って言いきれる人って、マジでかっこいいですよね...あこがれる...
え~、こっから本編の後半です。しっかりついてきてくださいね!!!
長っ!!!!!!もう見るのやめるわ!!!!なんて悲しいこと言わないで心にとめておいてくださいね!!!🔥🔥🔥🔥🔥🔥🔥
MRSC のうらばなし
今日(2023/03/05)、開催した桜コンテストの裏話です。実は裏で大変なことが起こっていたのです...!!!
A(#1) All to Almost Perfect?
A問題なので、気楽に作るか~という思いを込めて作りました。簡単な場合分けです。
Storyは大分意味の分からんものが作れて、大満足です(え?)。綺麗に並べるって、いいよね...並べすぎるのもアレですけどね...
推定diffは 50 以下を目安に作りました。(Testerさんの推定: 10,30,50(Just!!) )
B(#2) Share It Now
実は、過去の自分が作ったやつなのですが、めちゃくちゃな感じで想定解を書いておりました(しかも嘘解法)。改めてA問題と同じ手法で解いてみると、あらびっくり!!超が付くほど簡単に想定解を作れました!!!!
...え?A問題はあまりなんか関係ないって?
実は、またテーマ被りしたのです。最初次のような文章でした。
「すべてのおぼんに対し、乗っている🍡の個数が K の倍数であるようにするためには、少なくともいくつだけお団子を作る必要がありますか?」
でも、後々Bとテーマ同じやん!!!ってことに気づいたのです。なので、おぼんに乗せるお団子の数がちょうど~にすることはできますか?調に変更したのです。
多分、このころの自分は大体Bに殺されていた時期でした。精神が持たなかったんだと思います。
Storyの友だちとの会話は、私の人格を殺して作ってみました。最後の口調が強くなっていると思われます。多分。
推定diffは 100 以下を目安に作りました。(Testerさんの推定: 50,70,80,100(Just!) )
C(#3) Swap to Palindrome
これは最近作った問題です。なぜか回文の問題を作ろうとしたらできたやつです。
最初は順列全列挙で作ろうと思っていたんですが、回文の定義を見直してみればめっちゃ高速に判定できんじゃん!!!!で、N<=105にしました。
今Storyを見てみると、やばいですね。
茶処に回文のメニュー名が入っていたらめちゃくちゃ怖いですよ。知りませんけど。
推定diffは 300 以下を目安に作りました。(Testerさんの推定: 250,200)
D(#4) Separation and Union
過去の自分が解けないくせに作った問題です。今、この立場からすると結構簡単に見えますね(個人差があります)。
最初、題名は "String Sales" でした。売っている文字列を買ってその文字を切り取って組み合わせる、って感じ!
多分ですけど、価格追加して所持金追加してってやると、DPの問題に早変わり!!!(本当か?)になります。ん~...その場合の推定diffは1000を超えそう...
なのでその問題はしまってあります。おいておくので、興味があったらやってください!!そして私に教えてください!!!!!!
で、Storyではデコレーションケーキをモチーフにしようかなーと思ったので、ただの文字列だと味気ないので、チョコレートにして自然な感じに仕上げてみました。召し上がれ!!!!!!!!
推定diffは 600 以下を目安に作りました。(Testerさんの推定; 300,350、思ったより結構低め...?)
E(#5) Break-The-Brick!
はい、じゃ、まずは言ってましょう(唐突)。せーの...!!
って、あれだ!!著作権あるから言えないのかもしれない!!!うおー言いたいのに!!!韻が踏めるはずだから!!!!
「OOOO!!!!」(ある女子生徒4人組でバンドを作り、文化祭で青春を飾る青春ストーリーのアニメの題名)
...そうです。不自然に -(ハイフン) を付いていると思ったでしょう?
そのアニメを見ている私からすると、めちゃくちゃ発音同じやん!!!になったのが、題名の起源になりました。(最初は、ダルマ落としを英語にしただけにしようと思っていました)
あ、ご飯呼ばれたので、またあとで~!!
#
よっし、再開しました。
え~となんだっけ?ぼざろの話をしていたのか...
よし気を取り直して。
て言ってももうあまり言うことがない...ただ、過去の自分はこれはDPじゃ解けません!!!どやっとか言って今の自分からすると「は?」の一言になったことだけは言えます。
推定diffは 800 以下を目安に作りました。(Testerさんの推定: 650,600、これも低め...いや、妥当?)
F(#6) L to R Multiply
F問題、実はこんなことがあったのです。こういう問題がありました。
「数列Aからいくつか選び、選んだ要素からなる数列Bとします。Bはどの2要素を選ぼうと互いに素であるようにしたいです。Bの長さの最大値はいくつ?」
N<=16なら、まあbit全探索ですが、これを105で解こうとしました。
しかし、" M から始まる 11 文字の人" に、衝撃の一言を発されたのです。
「これ、NP困難では、ないですか?」
え?と思いました。全然気づかない(そもそも常人ではほぼ見抜けない、すなわちその指摘した人は天才だということ)ので、マジで意味不明と、最初は本当に思いました。でも、その後の説明で、納得しました。
え、じゃあこの問題、多項式時間しゃ解けないってこと?そういうことです。
そう、この問題だけ全取っ替えをしたのです。幸いにも、D問題は過去に作ったことがあったので助かりました。
そのD問題が、今回出したものです。大分、私の"""罠"""にまんまとはまってくれて助かりましたよ!!^^
素因数分解の問題を作りたかったので、この問題はまるで都合のいく素晴らしい問題でした。でも、実際のコンテストでこれが出てきたら私は泣くと思います。
「じゃあその問題を俺たちに解かせんな!!!」って!?すみませんでした。。。
推定diffは 1300 以下を目安にして作りました。(Testerの推定: 1000、そこそこあってそう...?)
G(#7) 1 Bird on Cherry Blossoms
お気づきでしょうか。私はグラフ理論が大好きでたまらないんですよね...!!!!(ニヤリ
ちょっとひねろうとしたら、素数を集めるというものというのが脳の中に出てきたのでそれにしました!!
実は、この問題が時間制限に厳しめにしてあるのです...!!!(すいません、アンケートの問題がすげぇ紛らわしかったですね)
(Pythonではすべてが時間制限に厳しめにしています(最悪))
まあ解説を見てもらったらわかる通り、愚直に素数判定した瞬間即座に落とします(This is True 無慈悲)。
K=0に引っかかってくれてる人がいて、くぅ~!!ありがとうございます!!!!!✨✨✨✨✨✨✨✨^^
推定diffは 1200 以下を目安に作りました。(Testerさんの推定: 800,700、なんか簡単だったそうです...)
Ex(#8) 7 - 3 = 5 ?
題名を見て、「こいつ頭おかしくなったんか?」と思ったそこのあなた!!大正解です()
いや、あるTwitterのスペースでですね、なんかの資格試験の勉強をしている際、7 - 3 = 5 で計算してミスるという最悪なことをしたのですよ!!
それが元凶になってこんなことになりました(実は最初から 7 問構成でいこうと思っていました)
で、肝心の問題内容ですが、実は最初は K=5 固定でいこうとしました。しかし、これまた " M から始まる 11 文字の人" に、またさわやかな風が吹き始め、
「これ、フェルマーの小定理で、解けるよ(イケボ」
と言われました。ずきゅーーーーーーーーーん!!!!!!!!!!!!!!!!!!💖💖💖💖💖💖💖💖💖💖💖💖💖
...んん、すいません取り乱しました。
まぁ、こんな最高な人がいてくれたおかげで、素数に拡張して解くことができました。
...え、合成数のときはどうするかって?知るか!!!!!!!(最悪な返事)
推定diffは 1300 以下を目安にして作りました。(Tester推定: 1300(Just!) )
#
ということでした。
どうでしたでしょうか?今回の「茶処・まっちゃら亭」のStoryをお楽しみいただけたでしょうか?
これからも、こんな感じでのったりゆったりぐったりやっていきますので、よろしくお願いします!!!!!
...次、記事書くのは...入緑時?これからも茶梅、頑張ります!!!!!!!!!!!
今回は、参加してくださり+この記事を見てくださり、誠にありがとうございました!!!!!!!!!!!
(11249文字、マジで疲れた...)
Epilogue
よし...とりあえずはこれでコンテスト関係は終わり!!!AHC、やってきま~す!!!
バタン(ドアを閉める音)