ゆきこーだーの雨と雪(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人近い人に解いていただいているので、なんか教育的要素を一つでも感じていただけた人が一人でも多ければそれはとっても嬉しいなって
DDCC2016 参加記
これは
ひとり Advent Calendar 2016 - Adventar
の3日目の記事です。
DDCC2016に行ってきました。
D(ドンドコ)D(電源)C(確保)C(コンテスト)
— りあん😇 (@rian_tkb) December 3, 2016
人権が少ないタイプのコンテスト
ちなみに9時半着ですでに充電席売り切れでした
— りあん😇 (@rian_tkb) December 3, 2016
コンテストの結果としては、A, B, Cの部分点は50分そこそこで取れて、Cの嘘解法がなぜか1WAしか出なくて、解法を見つけるというより嘘解法でごり押して通そう! って方にシフトしてしまい結果1時間座ってるだけになってしまった😇
結果は2完1半で43位でした。
うーん、2ページ目までには入っておきたかった、というか3完したかった。
🍣🍣🍣 #ddcc2016 pic.twitter.com/khwwAmCVjh
— りあん😇 (@rian_tkb) December 3, 2016
🍣とかちょこふぉんでゅとか食べた
講演会、厚切りジェイソンさんとDISCOの方のお話を聞いた。
厚切りさんは普通に有能な人という感じだったし話も面白かった。
Kiru Kezuru Migaku #DDCC2016
— りあん😇 (@rian_tkb) 2016年12月3日
KKM(かしこいかわいい森田)
セイク🍺で優勝👍 #ddcc2016 pic.twitter.com/PjeYxAp8Dy
— りあん😇 (@rian_tkb) December 3, 2016
葦くんが酔って顔が真っ赤になっていた
#ddcc2016 pic.twitter.com/NKVPa9aqc0
— りあん😇 (@rian_tkb) December 3, 2016
おまけ
本戦会場に置いてあった水、酔い覚ましにとてもよいのだけれどそういう意図があったのか #ddcc2016
— りあん😇 (@rian_tkb) 2016年12月3日
結局寿司食べて酒飲んだだけになってない…?
CODE FESTIVAL 2016 参加記 ver0.1(ほぼチームリレー(優勝)について)
宣伝
コード祭りの参加記については
ひとり Advent Calendar 2016 - Adventar
の序盤の記事としてもっとちゃんと書きます。
今は、簡単な総括と、あと“““圧勝を収めた[要出典]チームリレー”””について何が起きたのか適当に書きます。
(チームリレーに関してはおそらくjapljさんやきゅうりさんも書かれると思いますが、私は自分の問題が開始6分で終わったのでわりと全体の様子が見れてたんじゃないかなぁ、と思うので一応私も書きます)
AdCの期間中に、いつも通りツイートとともに振り返るみたいな記事として生まれ変わる予定なのでクソAdCの方もどうぞよろしくお願いします。
一日目
本戦
まさかの4完(49min)で133位でした。まさかのatcoderのレートが微減しました。まさかのatcoderレート黄色内で最下位でした。
この結果は自分でも本当に想定外で本当に落ち込んでいるのですが、ただ、数少ない人々から4完だったの意外、と言われて少しだけ他に認めてもらえるくらいの実力がついてきたのかもなぁ、と少し嬉しくもありました。
(問題についてとか詳しい話を後日追記)
暇な時間
🍣🍖🍕を食ったのち、ボードゲームとかカードゲームとかして遊んでました。たのしい。
エキシビジョン
オープンの方でuwiさんが早々にBを通していてすごいなぁとなった、オンサイトの方は、やはりチームワークは大事という感じがあった。
ホテル
間違って隣のホテルに入ってしまいフロントで困り果てるとかいう面白イベント(面白くない)がありました。
今回は睡眠妨害コンテンツがなかったので酒を入れたのち2時前くらいに寝たと思います。
二日目
asa
起床成功、ホテルのサービスコーヒーを飲みつつ会場まで歩く。
トーナメント
最終的にマージされる32人のうち唯一atcoderのレートが黄色、本戦での爆発炎上もありとてつもないプレッシャー。
結果としては無限にバグを踏み抜き、本当にギリギリで最後まで勝ち抜きました。
壇上でtouristと並んで写真を撮った(!!!)
#codefes #code_festival pic.twitter.com/LeGUtcTLKG
— 148_りあん (@rian_tkb) November 27, 2016
うちわ、家まで持って帰ってきてみると本当にただの単色のうちわなのでなんかロゴくらいは欲しかった
Round1 : 2位通過(200 + 100)
— 148_りあん (@rian_tkb) November 27, 2016
Round2 : 4位通過(200 + 200)
Round3 : 3位通過(0 + 400)
でした(めっちゃ調子がクソだった、やはり早解きコンテストは無理) #CODE_FESTIVAL
内容は本当に散々だったがギリギリ結果を残せたので本当によかった
(TODO : もう少し細かく)
昼〜
#codefes #code_festival pic.twitter.com/Yf4ovO2SC8
— 148_りあん (@rian_tkb) November 27, 2016
トーナメントの商品であるところのステッカーを貼り、ついにMBAがステッカー台紙と化した。
UFOキャッチャーでタオルゲット! #codefes #code_festival pic.twitter.com/64bJpo83oQ
— 148_りあん (@rian_tkb) November 27, 2016
UFOキャッチャーでタオルをゲット! アームがクソ固くて普通のゲーセンの金を吸い込むUFOキャッチャーとは比べ物にならないくらい楽だった。
広げてみると普通にバスタオルサイズでびっくり
チームリレー
お待たせしました。
チームMは、海外勢が ksun48 さん、日本勢は japlj さん、きゅうりさん、kzyKT さん他。
方針としては、始まったら簡単な問題が解きたいと申告した4人がA~D、残りからksun48さん、japljさん、きゅうりさんを除いた4人がE~Iくらいまで、ksun48さんはJだかKだかを一人一問読み、解法まで至らなくても問題概要がわかったらそれをjapljさん、もしくはきゅうりさん(確かA~Dをjapljさん、E~をきゅうりさんに、みたいな感じだったと思う)に伝えて、解法・実装を練ったのち誰かに実装を回す、みたいな感じで行こうという話になりました。
結果的にこの方針は、結局ほとんどの人が最初に自分が読んだ問題の実装を担当することになった、という点以外はこのまま進んだと思います。問題の数と人数が等しいので、この点についてはもう仕方ないと思います。
以下、大まかに時系列順になります(時間が前後していたりする可能性が大いにあります)
とりあえず始まると、私はE問題が目についたのでE問題を読みました(本戦がボロボロだったので弱気になっていた部分が大きいと思います)。
(x/gcd + y/gcd - 1) * gcd が答えなのはすぐに気づけたので、問題概要とともにきゅうりさんに説明、GOサインが出ると同時にA問題が通ってPCが空いたので、ささっと書きに行きAC。E問題で6:32なのでさすがにFAであってほしいが。
その後B, Cが通り、Dが少しバグっていて先にFが通る。
その間私はGにちょっかいを出しに行っていた(こうじゃね? みたいなことを言ったが結局自分でよりシンプルな解法を思いつかれていて何もしてない感がある)。Dが詰まっていてPCが空いていたので先にGをコーディングしてくるように言う(何様のつもりだ)(しかもこの時、解法の信ぴょう性を疑っていた)。
そんなうちにDがなんとかなる。A~F 6完が 31min(これはそこまで良いタイムというわけではなかったと思う)。
その頃、実はまだHが誰にも読まれていないことに気づく。読むと 24 * 60 * 60 (秒)でModを取った後 3 * 60 * 60 (秒)の区間に含まれる点の最大を求めればいいとわかる(ただ、アホなのでRMQなのでBITとか言った(どう見ても累積和でやるべき))。きゅうりさんに見せる。
Gがバグっていて、ますます解法の信ぴょう性を疑う。ただ、手元では合ったはずのサンプルもWAになっているので、コーディングのミスだろうなぁという気。
そんな頃、まさかのIが通る。kzyKTさんがガチプロで、一人で考察を進めて一人で通した。わけわかめ。
さらに、ksun48さんがKの解法をjapljさんに投げた後、自分はJを通しに行った。3, 4分で帰ってきた。あたまおかしい。
その間、何をしていたかと言うと、japljさんと二人でGのソースコードのデバッグをする。幸い、単純なifやforの条件ミスで、すぐに通る。解法疑ってめっちゃ申し訳ない。
残った2問、まずH問題をきゅうりさんが書きに行く。サンプル以外全部RE。japljさんに交代。a_0 + b_0 + a_1 + ... がオーバーフローして添え字がマイナスになっているのでは、という話になったがサンプル以外全部REなのは違和感があったので注意深く確認する。が、やっぱりそこしかなさそう。
そんなこんな言ってる間にjapljさんが帰ってくる(最後の問題のコード、dfsとか書いてあってそこそこ実装ありそうなのになんか5分くらいで帰ってきた、まったくもうなんやねん)。
きゅうりさんが走ってオーバーフローを処理したコードを提出。
全員でジャッジを見守る。
二人のコードが同時にジャッジが終わり、両方ともAC。おそらく10完していたチームを2つくらい颯爽と抜き1位になる。
おそらく勝因は、各人が与えられた問題をしっかり解けた、というところだと思います。解法が全くわからなくて japljさんやきゅうりさんに泣きつく、みたいなシーンはほぼ見なかったように思います。特にksun48さんとkzyKTさんがガチプロしていて、結果japljさんときゅうりさんが本当に実装するだけ、みたいになったのは本当に良かったと思います。
また、あまりどハマりすることもなく、一番多くWAを出した問題でも2回、全体で5回しか出していないのも本当に良かったと思います。
あと、サンプルが通らない場合はとりあえず提出してモニタの方でバグを探す、としたのも本当に良かったです。ICPCでもとりあえずソースコード印刷しようと思います。
PCが空いている時間もほぼなかった。
(なんか考えれば考えるほど本当に完璧すぎるチーム戦だったのでは???)
という感じでした。
こちらが、各問題のAC時間になります(全提出は見る権限がなかった)
トーナメントと合わせて2回も壇上に上がれてほんま嬉しい。
(TODO : 全体の感想とか、今後の目標とか)
ひとり Advent Calendar 2016 - Adventar
を、お楽しみに!!!
コード祭り予選突破練習会をやりました
やりました。
コード祭り予選突破練習会@大岡山【非公式】 #atnd https://t.co/1WdPuvGBUO
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月28日
・開催1ヶ月半前
【初心者向け】 CODE FESTIVAL 予選突破練習会 【非公式】 #atnd https://t.co/ZZBfhrOzE1
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月21日
宇宙ツイッタラー(@kenkoooo)さん主催で今年も練習会が開かれ、今年も参加させていただきました。
そこでおよそ3分の1が東工大生だったので、これは学内で開いても集まるのでは? と思い、学内で練習会したいなぁと思い始める
そう、東工大生向けのコード祭り練習会したいなぁと思っている
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月22日
なんか週に1回のペースで言ってるなこいつ
そういえばコード祭り予選突破練習会inたいてくしたいって言ってる
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年8月30日
コード祭り予選突破練習会いんたいてくしたい
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月4日
rogyの合宿で酔っ払いながら酔っ払ってるyosupotに絡む
そういえば昨日だか一昨日だかに酔っ払いながらよすぽにコード祭り予選突破練習会開いてって言いまくった気がする
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月16日
・開催2週間前
予選Aで通れて気を良くしてしまい、練習会開催にとても前向きになる
・開催1週間前
なんかrogy(所属している技術系サークル)の部会でしゃべりたかったら喋っていいよ、と言われ一晩でコード祭りを大雑把に説明するスライドを作る
そのまま適当に日時を決める
これが一番つらかった
ところで問題の傾向が大きく変わってしまったのでこの前の練習会で作った問題セット( https://t.co/1SRmn6ahdd )が役に立たなくなってしまった
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月28日
それはそう
🍣はね、予選通過してリリリーリの金で食べてくれ、練習会では出ません
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年9月29日
・開催2日前
D, E問題用問題を集めようとするも地力が足らない、くまったくまった……って言っていたらyosupotが颯爽と問題を追加してくれた
あと宇宙ツイッタラーさんに唐突にatcoder problemsの仕様変更をお願いする(本当にありがとうございました…!)
・開催1日前
バイトに勤しむ
ばおわや
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月5日
・開催5時間前
初めて車🚗を運転する
乗るぜ🚙🚙🚙💨💨💨 pic.twitter.com/iUl0dkhw0S
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
ところで昼に今日の問題セットを公開するつもりがぶーぶをぶーぶーしてました
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
・開催2時間前
問題セットを公開
コード祭り予選突破練習会問題セット - Google スプレッドシート
この問題セットはきっとめっちゃ有用なのでみんな活用していこう!
・開催10分後
練習会サイトを公開
A問題 : AtCoder Problems
B問題 : AtCoder Problems
C問題 : AtCoder Problems
D問題 : AtCoder Problems
コード祭り予選突破練習会、始まりそう pic.twitter.com/uOc5IGSI06
— りあん♨️🍶🚙💨 (@rian_tkb) 2016年10月6日
練習会で具体的にどう解いていってもらうかをわりと考えていかなかったので、予想通りけっこうグダグダになってしまった気がする
でもまたやりたいなぁ(今度はちゃんとコンテンツを用意して臨みたいなぁ…!)
CODE FESTIVAL 2016 予選A 参加記
コード祭り2016の予選Aに出ました。
ABCDの4完で全体107位、日本人40位でした。registerフェーズで落ちてなければ予選突破してそう。
・開始
配点が 100 - 200 - 400 - 800 - 1200 なのでとりあえずCを解かなきゃ話にならないなぁと思いCから開く
解法はすぐ思いついたが無限にバグらせて4WA
・20分経過
ひいこら言いながらCを通す
順位表みたら300位とかでおいいいいい、っつった
・25分経過
B, Aと通してDを開く
が に依存しないかつ が に依存しないことはすぐ見えたけどわからず
・40-45分経過
下のツイートの解法を思いついて実装する(自分はハマらなかったけどグラフが連結でない可能性があるので注意)
こんなグラフを作って幅優先して、距離が異なるパスが発見されたらNo、ってした pic.twitter.com/pSRcHULB9K
— りあん♨🍶 (@rian_tkb) 2016年9月24日
・60分経過
実装して提出する
Submission #895510 - CODE FESTIVAL 2016 qual A | AtCoder
サンプルが一個落ちていることにより入れる値が負数じゃダメだという条件を見逃していることに気づく
・75分経過
列の最小値を持って幅優先探索中に更新していけば良さそうと気づいて実装を始める
・85分経過
実装したがWAが取れない
Submission #896588 - CODE FESTIVAL 2016 qual A | AtCoder
仕方ないから幅優先探索後にめっちゃループ回してさらに最小値を更新するか〜〜〜って言う
・90分経過
1 ケ ー ス WA
Submission #896888 - CODE FESTIVAL 2016 qual A | AtCoder
・100分経過
最後のループで300回以上更新があった場合もう負数になるんじゃね? ってNoを出力するコード出したらAC
(コンテスト後にsubmit二分探索したら30回ほどで打ち切って大丈夫だったらしい)
不正感しかないけど通ったからいいんだもん...!
Submission #897265 - CODE FESTIVAL 2016 qual A | AtCoder
不正感が強い pic.twitter.com/Wf66V4zpbh
— りあん♨🍶 (@rian_tkb) 2016年9月24日
あとはゆっくり順位表を眺めてました
(コンテストが終わったあと考察したらこれEのほうが簡単じゃない? ってなった)
とりあえずホントにどうなることやらって感じだったのでホントにホッとしています...
今年もパーカー得たい〜〜〜!!!
あと、予選Bまでに東工大内でコード祭り予選突破練習会開きたいです、協力者(というか主催者)募集中です