うにゅーん、って感じだ

SRM highest:1910. C#を書きます.

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

これは
ひとり 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人近い人に解いていただいているので、なんか教育的要素を一つでも感じていただけた人が一人でも多ければそれはとっても嬉しいなって

DDCC2016 参加記

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



DDCC2016に行ってきました。



人権が少ないタイプのコンテスト


コンテストの結果としては、A, B, Cの部分点は50分そこそこで取れて、Cの嘘解法がなぜか1WAしか出なくて、解法を見つけるというより嘘解法でごり押して通そう! って方にシフトしてしまい結果1時間座ってるだけになってしまった😇

結果は2完1半で43位でした。
うーん、2ページ目までには入っておきたかった、というか3完したかった。



🍣とかちょこふぉんでゅとか食べた


講演会、厚切りジェイソンさんとDISCOの方のお話を聞いた。
厚切りさんは普通に有能な人という感じだったし話も面白かった。


KKM(かしこいかわいい森田)




葦くんが酔って顔が真っ赤になっていた



おまけ



結局寿司食べて酒飲んだだけになってない…?

書くことがない

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


なんと、2日目にして書くことがなくなりました!


…というのは嘘で、実際には書く時間がない、というのが現状で、クソみたいにリアルが充実していて死にそうです。
それなのにお金は貯まらない。


最近いくら寝ても寝足りません。これではわふれるかを笑えない。


ところで12/12。

12/12

12/12


amazonの欲しいものリストです。
http://www.amazon.co.jp/registry/wishlist/1KF23B8C3ULPK/ref=cm_sw_r_tw_ws_x_RSyqybB8VBJVC


そろそろ萬寿を注文しようかな。



それでは、3日目の記事は [未定] です! よろしくお願いします!

あどべんとかれんだー2016

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



上のクソAdCの通り、これから25日間くらいブログを書いて行きたいと思います。
(早速一日目から遅刻)
とは言っても、添削とかバイトとか添削とかでクソ忙しいので、とりあえずオススメのAdvent Calendarを紹介してお茶を濁していこうかと思います。



・競プロ Advent Calendar
www.adventar.org
競プロつよい人たちがつよいことを書きます。その2も並列して進むようです。
なんと私も書かせていただきます。6日目くらいに初心者が作問して感じたこととかを書くつもりです。


・rogy Advent Calendar
www.adventar.org
東工大の技術系サークル、ロボット技術研究会のAdvent Calendarです。
私は特に寄稿する記事が思いつきませんでした。


・Advent Calendar Contest
www.adventar.org
1日1問増えていくタイプの面白いコンテストです。
私は今年も12日目の問題を担当させていただくことになりましたが、まだ何も考えてなくてめっちゃやばいです。




他のAdCばかり紹介していてもどうしようもないので、自分が書きたいなぁと思っている記事を下に列挙します。


・ゆきこーだーの雨と雪回(http://yukicoder.me/contests/154/) の雑記
・コード祭り参加記の追記と、ふざけた感じverの記事の作成
・ハルコンの自分の方針の解説
C#でcinみたいなやつを作ろうとした話
C#の単純型の話
C#erがC++を書いて思ったこと



それでは、2日目の記事は [未定] です! よろしくお願いします!

CODE FESTIVAL 2016 参加記 ver0.1(ほぼチームリレー(優勝)について)

宣伝

コード祭りの参加記については
ひとり Advent Calendar 2016 - Adventar
の序盤の記事としてもっとちゃんと書きます。

今は、簡単な総括と、あと“““圧勝を収めた[要出典]チームリレー”””について何が起きたのか適当に書きます。
(チームリレーに関してはおそらくjapljさんやきゅうりさんも書かれると思いますが、私は自分の問題が開始6分で終わったのでわりと全体の様子が見れてたんじゃないかなぁ、と思うので一応私も書きます)

AdCの期間中に、いつも通りツイートとともに振り返るみたいな記事として生まれ変わる予定なのでクソAdCの方もどうぞよろしくお願いします。

一日目

本戦

まさかの4完(49min)で133位でした。まさかのatcoderのレートが微減しました。まさかのatcoderレート黄色内で最下位でした。

この結果は自分でも本当に想定外で本当に落ち込んでいるのですが、ただ、数少ない人々から4完だったの意外、と言われて少しだけ他に認めてもらえるくらいの実力がついてきたのかもなぁ、と少し嬉しくもありました。


(問題についてとか詳しい話を後日追記)

touristのtalk


これめっちゃ好き(自画自賛)

暇な時間

🍣🍖🍕を食ったのち、ボードゲームとかカードゲームとかして遊んでました。たのしい。

エキシビジョン

オープンの方でuwiさんが早々にBを通していてすごいなぁとなった、オンサイトの方は、やはりチームワークは大事という感じがあった。

ホテル

間違って隣のホテルに入ってしまいフロントで困り果てるとかいう面白イベント(面白くない)がありました。
今回は睡眠妨害コンテンツがなかったので酒を入れたのち2時前くらいに寝たと思います。

二日目

asa

起床成功、ホテルのサービスコーヒーを飲みつつ会場まで歩く。

トーナメント

最終的にマージされる32人のうち唯一atcoderのレートが黄色、本戦での爆発炎上もありとてつもないプレッシャー。
結果としては無限にバグを踏み抜き、本当にギリギリで最後まで勝ち抜きました。
壇上でtouristと並んで写真を撮った(!!!)



うちわ、家まで持って帰ってきてみると本当にただの単色のうちわなのでなんかロゴくらいは欲しかった


内容は本当に散々だったがギリギリ結果を残せたので本当によかった


(TODO : もう少し細かく)

昼〜


トーナメントの商品であるところのステッカーを貼り、ついにMBAがステッカー台紙と化した。



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が空いている時間もほぼなかった。
(なんか考えれば考えるほど本当に完璧すぎるチーム戦だったのでは???)


という感じでした。

f:id:riantkb:20161127223306p:plain

f:id:riantkb:20161127223317p:plain
こちらが、各問題のAC時間になります(全提出は見る権限がなかった)


トーナメントと合わせて2回も壇上に上がれてほんま嬉しい。



(TODO : 全体の感想とか、今後の目標とか)


ひとり Advent Calendar 2016 - Adventar
を、お楽しみに!!!

コード祭り予選突破練習会をやりました

やりました。


・開催1ヶ月半前


宇宙ツイッタラー(@kenkoooo)さん主催で今年も練習会が開かれ、今年も参加させていただきました。
そこでおよそ3分の1が東工大生だったので、これは学内で開いても集まるのでは? と思い、学内で練習会したいなぁと思い始める
なんか週に1回のペースで言ってるなこいつ

rogyの合宿で酔っ払いながら酔っ払ってるyosupotに絡む


・開催2週間前
予選Aで通れて気を良くしてしまい、練習会開催にとても前向きになる


・開催1週間前
なんかrogy(所属している技術系サークル)の部会でしゃべりたかったら喋っていいよ、と言われ一晩でコード祭りを大雑把に説明するスライドを作る

www.slideshare.net
そのまま適当に日時を決める


これが一番つらかった


それはそう


・開催2日前
D, E問題用問題を集めようとするも地力が足らない、くまったくまった……って言っていたらyosupotが颯爽と問題を追加してくれた
あと宇宙ツイッタラーさんに唐突にatcoder problemsの仕様変更をお願いする(本当にありがとうございました…!)


・開催1日前
バイトに勤しむ


・開催5時間前
初めて車🚗を運転する



・開催2時間前
問題セットを公開
コード祭り予選突破練習会問題セット - Google スプレッドシート
この問題セットはきっとめっちゃ有用なのでみんな活用していこう!


・開催10分後
練習会サイトを公開
A問題 : AtCoder Problems
B問題 : AtCoder Problems
C問題 : AtCoder Problems
D問題 : AtCoder Problems


練習会で具体的にどう解いていってもらうかをわりと考えていかなかったので、予想通りけっこうグダグダになってしまった気がする
でもまたやりたいなぁ(今度はちゃんとコンテンツを用意して臨みたいなぁ…!)

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を開く
 {(a_{i, j} - a_{i, j + 1})}{i} に依存しないかつ {(a_{i, j} - a_{i + 1, j})}{j} に依存しないことはすぐ見えたけどわからず


・40-45分経過

 下のツイートの解法を思いついて実装する(自分はハマらなかったけどグラフが連結でない可能性があるので注意)


・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
 


あとはゆっくり順位表を眺めてました
(コンテストが終わったあと考察したらこれEのほうが簡単じゃない? ってなった)


とりあえずホントにどうなることやらって感じだったのでホントにホッとしています...


今年もパーカー得たい〜〜〜!!!



あと、予選Bまでに東工大内でコード祭り予選突破練習会開きたいです、協力者(というか主催者)募集中です