ゆきこーだーの雨と雪(1)~(4) 雑記
これは
ひとり Advent Calendar 2016 - Adventar
の4日目の記事です。
11/18に、なんと5問中4問が自作問題のコンテストが開かれました! わーい
yukicoder contest 154 - yukicoder
問題名は、ゆきこーだーの雨と雪(1) ~ (4) でした。
元ネタはもちろんおおかみこども的なアレです。
ところで元ネタはもちろんおおかみこどものうんたらかんたらです
— りあん😇 (@rian_tkb) November 18, 2016
一番最初に作ったのが(2)で(多分半年以上前)、多分その時に金曜ロードショーか何かでやってたのだと思います。
(2)はまぁ簡単な問題だなぁと思いながら、当初は最後にsort関数にぶっこんで が想定解の★3でした。★2になった理由は後述。
その後、(4)の問題概要を思いついて問題文を書いたのですが、実はその時はまだ解法が思いついていなくて、やっぱ平衡二分探索木とかで殴らないと解けないのかぁとか考えていました。
そんなとき、クエリ先読み座標圧縮からのBITでできるやん! となり、完成に至りました。
その後、2問だけじゃ寂しいなぁとなり、どうせならメタっぽい(?) 問題を作ろう! と思ってwriter体験問題みたいな(1)を作りました。個人的にはけっこう気に入ってるけどふぁぼがついてなくてかなしい。
そうして3問作ってしばらく経ったのち、(現実世界の)yukiさんからゆきこーだーの雨と雪を用いて当番回をしませんか、みたいなお話をいただいて、二つ返事で了承しました。
ただ、問題が3問しかない、どうしよう…。
よし、もう1問作ろう!
となりました。
そこからがわりと難産で、あと足りてないのはおおかみ要素だ! って言って2人プレイ用の人狼を題材にした問題にしようかとも考えたのですが、
jinraw.com
ほぼじゃんけん(運ゲー)みたいな感じやんけ! ってなって断念しました。
その後、「いや、この3問でコンテストやったらただの実用プログラミング実装コンテストになっちゃうんじゃないか…?」と思いつつ、適当なことを考えてたらうまくこじつけてかつ二分探索もDPも使う問題ができました。やったぜ。
でも作った当初は、二分探索パートとDPパートが明らかに透けて見えるしこれは★3弱かなぁと思っていました。
こうして残り1問として★3が生成されたので、(2)は で通る制約に変更されて★2になりました。
その後、かみぺさんの点数を計算する★1の問題を加えた5問のコンテストとなることになりました。
ところが(4)のテスターをantaさんにお願いしたところ、なんと C++ だと ( M は参加者の人数) がわりと適当な実装で通ってしまうらしく激冷えになった。C# の string を key とする SortedDictonary が重すぎて なのに 5sec かかっていたので余計に激冷えという感じ。
さて、コンテストですが、まず(1)はまぁ、という感じ。比較的みんなちゃんと で解いていてえらいなぁという感じがした(想定解法は )。
(1) : 最初 A, B <= 1000 だったんですけど簡単すぎかなぁと思って増えました、結構WA生えててなるほどなぁという感じ
— りあん😇 (@rian_tkb) November 18, 2016
(2)は、
- 実装が重い
- そもそもstd::mapは★2適正ではない
- つらい
みたいな感じで阿鼻叫喚になっていました。ほんと申し訳ねぇ。
(2) : O(T^2) だし★2やろw、っつったけどstd::mapを使えないと死なのでむずかったか
— りあん😇 (@rian_tkb) November 18, 2016
(3)は、わりと思ったよりつまづいていただけていてびっくりした。
testerさんが後半のDP部分を Segtree で解いていたように記憶していたけど、その解法で通してる人がわりと多かったような気がした。
(3) : まずMaxは二分探索により楽勝で求まる、SumはしゃくとりDPすればまぁ
— りあん😇 (@rian_tkb) November 18, 2016
(4)は、やはり で通している人がちらほらいたように見えた。
ただ、(3)がけっこうきびしく、(4)に辿り着いている人は平衡二分木のプロばかりで平衡二分木で殴って終了、みたいな解も多かったような気がする(その人たちは頼むから解説記事を書いて、はやく)。
多分想定解で通している人はほとんどいなかったと思う。
(4) : 想定解はクエリ先読み座標圧縮です!!! O(T log T) よりデカいやつは落ちてほしい
— りあん😇 (@rian_tkb) November 18, 2016
結果として、(3)が思ったより良問になってびっくりした。
以下、適当なツイートたち。
開始すぐはジャッジが詰まっている可能性がありますが私のせいです><
— りあん😇 (@rian_tkb) November 18, 2016
バイトが長引いたせいでコンテスト直前にantaさんの追加テストケースを入れる羽目になり、リジャッジでめっちゃTLEしてジャッジを詰まらす。
全完が出ました!
— りあん😇 (@rian_tkb) November 18, 2016
30分耐えたのは僥倖
— りあん😇 (@rian_tkb) November 18, 2016
C++だけTL500msとかにしたいよな
— りあん😇 (@rian_tkb) November 18, 2016
心の叫び
みんな、想定解法で解いて
— りあん😇 (@rian_tkb) November 18, 2016
心の叫び(2)
(4) のウラ話としては、(2)を作問した時にこういう問題で解けないかなぁ、やっぱ平衡二分探索木とかで殴るのかなぁ、って思ってたらいつのまにかこれ解けるやん! ってなったので出題できたので、逆に平衡二分探索木で解いた人は全員解説をブログに書いてください
— りあん😇 (@rian_tkb) November 18, 2016
解説、書いて❤️
(3)、1問足りない! ってなって即席で作った割にはよくできてないスカ
— りあん😇 (@rian_tkb) November 18, 2016
自画自賛
今回一番嬉しかったのは、ニコ生でCの解説がされている時に「//まぁでも勉強にはなったよ」みたいなコメを見たことです
— りあん😇 (@rian_tkb) November 18, 2016
あっとこでできなくてゆきこでできることは、為になる問題やアルゴリズムに触れることだと思うんですよ
— りあん😇 (@rian_tkb) November 18, 2016
あっとことかだと知ってるかどうかで明暗が分かれてしまう問題は出しづらいけど、どこかで出ないと一生使えるようにならないわけで、たまにそういうのが練習できてもいいんじゃないかなぁと
今見ると(2)は80人近い人に解いていただいているので、なんか教育的要素を一つでも感じていただけた人が一人でも多ければそれはとっても嬉しいなって