読者です 読者をやめる 読者になる 読者になる

うにゅーん、って感じだ

SRM, CF, AtCoder黄. SRM highest:1746. C#を書きます.

ゆきこーだーの雨と雪(1)~(4) 雑記

yukicoder

これは
ひとり Advent Calendar 2016 - Adventar
の4日目の記事です。



11/18に、なんと5問中4問が自作問題のコンテストが開かれました! わーい

f:id:riantkb:20161204234041p:plain
yukicoder contest 154 - yukicoder


問題名は、ゆきこーだーの雨と雪(1) ~ (4) でした。

元ネタはもちろんおおかみこども的なアレです。

一番最初に作ったのが(2)で(多分半年以上前)、多分その時に金曜ロードショーか何かでやってたのだと思います。


(2)はまぁ簡単な問題だなぁと思いながら、当初は最後にsort関数にぶっこんで {O(N \log N)} が想定解の★3でした。★2になった理由は後述。


その後、(4)の問題概要を思いついて問題文を書いたのですが、実はその時はまだ解法が思いついていなくて、やっぱ平衡二分探索木とかで殴らないと解けないのかぁとか考えていました。
そんなとき、クエリ先読み座標圧縮からのBITでできるやん! となり、完成に至りました。


その後、2問だけじゃ寂しいなぁとなり、どうせならメタっぽい(?) 問題を作ろう! と思ってwriter体験問題みたいな(1)を作りました。個人的にはけっこう気に入ってるけどふぁぼがついてなくてかなしい。


そうして3問作ってしばらく経ったのち、(現実世界の)yukiさんからゆきこーだーの雨と雪を用いて当番回をしませんか、みたいなお話をいただいて、二つ返事で了承しました。

ただ、問題が3問しかない、どうしよう…。

よし、もう1問作ろう!

となりました。


そこからがわりと難産で、あと足りてないのはおおかみ要素だ! って言って2人プレイ用の人狼を題材にした問題にしようかとも考えたのですが、
jinraw.com
ほぼじゃんけん(運ゲー)みたいな感じやんけ! ってなって断念しました。


その後、「いや、この3問でコンテストやったらただの実用プログラミング実装コンテストになっちゃうんじゃないか…?」と思いつつ、適当なことを考えてたらうまくこじつけてかつ二分探索もDPも使う問題ができました。やったぜ。

でも作った当初は、二分探索パートとDPパートが明らかに透けて見えるしこれは★3弱かなぁと思っていました。


こうして残り1問として★3が生成されたので、(2)は {O(N^2)} で通る制約に変更されて★2になりました。



その後、かみぺさんの点数を計算する★1の問題を加えた5問のコンテストとなることになりました。


ところが(4)のテスターをantaさんにお願いしたところ、なんと C++ だと {O(TM)} ( M は参加者の人数) がわりと適当な実装で通ってしまうらしく激冷えになった。C# の string を key とする SortedDictonary が重すぎて {O(T \log T)} なのに 5sec かかっていたので余計に激冷えという感じ。



さて、コンテストですが、まず(1)はまぁ、という感じ。比較的みんなちゃんと {O(\log N)} で解いていてえらいなぁという感じがした(想定解法は {O(N^2)})。


(2)は、

  • 実装が重い
  • そもそもstd::mapは★2適正ではない
  • つらい

みたいな感じで阿鼻叫喚になっていました。ほんと申し訳ねぇ。


(3)は、わりと思ったよりつまづいていただけていてびっくりした。
testerさんが後半のDP部分を Segtree で解いていたように記憶していたけど、その解法で通してる人がわりと多かったような気がした。


(4)は、やはり {O(TM)} で通している人がちらほらいたように見えた。
ただ、(3)がけっこうきびしく、(4)に辿り着いている人は平衡二分木のプロばかりで平衡二分木で殴って終了、みたいな解も多かったような気がする(その人たちは頼むから解説記事を書いて、はやく)。
多分想定解で通している人はほとんどいなかったと思う。



結果として、(3)が思ったより良問になってびっくりした。


以下、適当なツイートたち。


バイトが長引いたせいでコンテスト直前にantaさんの追加テストケースを入れる羽目になり、リジャッジでめっちゃTLEしてジャッジを詰まらす。





心の叫び



心の叫び(2)



解説、書いて❤️



自画自賛




今見ると(2)は80人近い人に解いていただいているので、なんか教育的要素を一つでも感じていただけた人が一人でも多ければそれはとっても嬉しいなって