うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ACM-ICPC 2017国内予選 参加記

ICPC

半年ぶりのブログ更新ですね。
本当はこの記事の前に、この前 SnackDown2017 というやつでインドに行った、という記事を書かなければならないのですがちょっと色々忙しかったのでそのうち書きます。

icpc とは？

こちらをごらんくださいな
ACM-ICPC とは？ | ACM-ICPC 国際大学対抗プログラミングコンテスト



あらすじ

icpc たいてっく予選は毎年熾烈（しれつ）を極めていた。謎の組織 FCCPC 、†赤きもの†へと進化した後輩、大魔王 yosupot ...。
ただ、そんなたいてっくにも希望はあった。謎の組織 FCCPC は謎すぎたため消滅、大魔王 yosupot は力を溜めるための眠りについた。
今こそたいてっく予選に打ち克つべき！ †赤きもの†へと進化した後輩の次の1枠を狙い立ち上がったチーム「kurukuru-sushi」の前に立ちはだかったのは、チーム「IQ1」だった…。

登場人物

チーム「kurukuru-sushi」

rian_tkb（りあん）, Ashurnasirpal（葦）, monman53（もんまん）からなるチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1308

チーム「IQ1」

吹雪, 睦月, 夕立 からなるとてもバランスの良いチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1142

チーム「ninjaribaton」

nari, baton, ninja からなるガチプロ後輩チーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1327

ティッピーぬいぐるみ

チーム「kurukuru-sushi」の机の上に鎮座するぬいぐるみ


国内予選前日 (7/13)

たいてっく予選突破が絶望的だった一昨年、去年とは異なり、たいてっく予選突破が現実味を帯びている今年のicpc国内予選。……というより、今年の出場選手のうち†赤きもの†へと進化した後輩の次にレートが高いのが自分で[要出典]、さすがにたいてっく予選突破できないと人権がない、という状況になり今までにないプレッシャーに追われる rian_tkb。

血迷った rian_tkb は、秋葉原に赴き25000円のキーボードとリストレストを購入する。

（今思うと、ここまでして突破できてなかったら本当にやばかった）

国内予選当日 (7/14)

コンテスト前

今期の授業は全て切ったのでリハーサルが終わるまでに大学に着けばいいのだが、家にいても落ち着かないので早めに家を出る。


ラボに置いてあった蟻本を持ち、蟻本に書いていない平衡二分探索木と、あとは AtCoder の提出のうち特に苦手なものの提出コードを印刷して会場に向かう。


チームメイトが皆蟻本を持ってきていたので積み上がる。

リハーサルも3問通して暇なので遊ぶ（上の kurukuru-tippy もこのとき撮影）。

この後、もんまんくんが M問題を頑張って通していた。

コンテスト中

最速で印刷ジョブを飛ばしたつもりがプリンターがトナー切れで、少しタイムロス。
その間に A問題を読む。
……ん？ これは恐ろしいほどに簡単だぞ？？？
横からめっちゃ口を挟みながらもんまんくんにコーディングしてもらい、そのまま AC。ここまで 5min。

葦くんが B を読んでいたので見ると、構文解析。
問題文がよくわからなかったのでよくよく読むと、ダブルクォーテーションで split して偶奇を気にしつつぐっ、とやるだけ。
しかし、A が通ってしまい PC を空いた状態にしたくないという焦りから見切り発車してしまい、少しめんどい実装になってしまった。
ただそこまでバグらせずに通してくれたのでよかった（とは言ってもやはり時間はかかってしまった）。ここまで 30min。

葦くんが B 問題と格闘している間に C 問題を手に取ると、h, w <= 10 なのが不思議なレベルで簡単な問題。
本当にやるだけにしか見えない。
もんまんくんに解法を伝えつつ紙コーディングをしてもらう（もちろんこれにもめっちゃ口を挟む）。
葦くんが B を通したらそのまま C を実装してもらい、AC。ここまで 40min。

ここで順位表を見る。
結構いい感じに進んでいたと思っていたので IQ1 に時間ペナルティでとても大きく離されていてとてもビックリする。
この様子だと正答数で上回らないと IQ1 に勝てないぞ……。

ここで自明問題が尽きる。
自分はすでにちょっとテンパっていたので、葦くんに D の問題文の要約を頼む（正確には問題概要はほぼ入っていたが、D に入る問題に見えなかった（＝普通に解ける気がしなかった）ので誤読が怖くて読んでもらうことにした）。
どう考えても n * m <= 500 が重要な制約だが、よくわからない。
葦くんから整理された問題概要を聞くが、まだわからない。
ただ、こういうのは大抵 n = m あたりが重要なので、紙に 20 * 25 = 500 という式を書く
→ あ、これいけるのでは？？？
PC が空いていた焦燥感もあり、とりあえず書き始める。
途中少しテンパるが、大きなバグもなく実装した……はずが、答えが合わない。
よく見てみると、求めるものが作れるレシピの集合が何通りあるか、ではなくレシピの集合の要素数の最大値だった（ここは葦くんの誤読だったと思う）。
ただ、修正自体はすぐにでき、AC。ここまで 1h10min。

ここでまた順位表を見ると、また IQ1 との差が広がっている。これは本格的にヤバい……。
E は無理そうという話があったので、先に F を見る。明らかに考察ゲーの匂い。
無理そうと言われていた E も読むが、確かに無理そうだったので、F の考察をする。
とりあえず計算用紙に印をつけて実際に折ってみる。
左からの位置と上からの位置と左右どっちに折ったかがわかれば、次の状態が定式化できそうな状態にはなる、が、まだ考察が進まない。
もう少し考察をすると、上から何番目にあるか、というのは折り方と 1対1 に対応することがわかる。
あと、逆に折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらないことがわかった。
が、前からやっていくべきか、後ろからやっていくべきかがよくわからない。
両方からやって 2^30 はさすがに間に合わなさそう……。

ここでうだうだ言っていると、もんまんくんが考察の手助けをしてくれて、一気に解法へ結びついた


（折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらない、という自分の考察を完全に忘却していた）

ばばばっと書く。
1-origin なので境界条件とか +1 するか、とかがクソめんどい。
実際にバグる。
サンプルが合うようにコードをいじいじする。

そうこうしているうちに葦くんが G 問題がいけそうな雰囲気になったと言っていて、写経が必要なのでとりあえずコードを印刷して交代する。

コードを印刷して眺めていると、バグがすぐに見つかる。
また交代してもらってそこを直すとサンプルが通ったので、そのまま投げると AC。俺ってもしかして天才か？？？ ここまで 2h。

葦くんが G の写経をしている間、E を考えるが普通に無理そう。
H に関しても、4回まで調べればいいので探索範囲はすごく絞れそうだが絞り方がよくわからない。
なので、葦くんの G の解放に反例がないかどうかを調べる。

葦くんのコーディングが終わってサンプルを食わせるが、バグっている。
いくつかのしょうもないバグは潰し、見た目上はいい感じに動いているが、どうしても関節点列挙がバグっている……。写経はもんまんくんに適宜チェックしてもらっていたので問題ないはず……。
もう時間がなかったので一回バグったままで投げてみるが、当然 WA。
結局バグがどこかわからず、最後は順位表を見ながら終了。

最後の 2h59m59s で IQ1 が F を通していて、時間ペナルティ的に 1WA でも出していたら順位が逆転していたので、本当に危なかった。


結果、ABCDF の 5完 0WA早解きで 16 位でした！ まぁ上々では
f:id:riantkb:20170715204109p:plain

Standings
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/standings/

コンテスト後





打ち上げに行くが全然飲み足りないので、家で独り祝勝会

いま、めっちゃジンが入っています✌︎

あとがき

国内予選突破できて本当に良かった。
こんな日が来るのは本当に夢みたいで、大学入って競プロ始めて以来、一番嬉しいかもしれない。

それではみなさん、つくばで会いましょう！

三角形はいくつ？ 雑記

Advent Calender Contest yukicoder

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



アドベコン2016の12日目の問題を担当させていただきました。

www.adventar.org


問題はこちら
No.461 三角形はいくつ？ - yukicoder


問題概要としてはパズル的なのでよくある、線をいっぱい引いた図形の中に三角形がいくつあるか数えるものです。




さて、解法としては、直線を3本取ってきたときにその3本で三角形が描けているか、を判定してあげればいいです。



判定方法についてですが、まず3本が1点で交わるとダメです。また、3本の互いの交点のうち一つでも最初の大きな三角形の外側にある場合、3本は最初の大きな三角形の中のみ伸びてる線分なのでこれも三角形となることができません（日本語が下手）。


実は、この2点をクリアすればその3本は必ず三角形を描けています。



次はこれを実際にどう判定するかですが、
{\displaystyle q_i = \frac{b_i}{a_i + b_i}}
という値に注目すると、
前者は3本の {q_i} の和が1であるかどうか、後者は3本のうち任意の2本に対して {q_i} の和が1より大きいかどうか、にそれぞれ対応しています。
（これはもちろん {\displaystyle \frac{a_i}{a_i + b_i}} という値に注目してもほぼ同じように解けます）


この判定を全組み合わせに対して調べれば、とりあえず {O(N^3)} で解けます。ただ、2本を確定させたとき、もう1本に対して3本の {q_i} の和が1になる線分があるかどうかと、任意の2本の {q_i} の和が1以下のものがいくつあるか、というのは {q_i} の値でソートしておけば両方 {O( \log N)} で解け、結果 {O(N^2 \log N)} となります。

（うまくしゃくとりとかすると {O(N^2)} になります）





これは最初 {O(N^3)} が通る制約で★2で出す予定でした。ただ、アドベコンの周囲の問題の難易度を眺めているとどうも★2が多そうだったので（ただこれは罠でその後みんな★3に昇格した）{O(N^2 \log N)} に制約を変えて、ついでに誤差を {10^{-16}} 程度まで小さくして分数で足したりソートしたりしてもらうようにしたりとか、{N = 4000} にしてオーバーフローを誘ったりしました。


ただいくつか誤算があって、まず、long double は仮数部が 63bit あるので、long long の範囲では誤差が出ない、ということ。これは出題前に気づいていました。本当は浮動小数点数を使った解答を全て誤差死させたかったのですがまぁ致し方なし。double がほぼ全て落ちるだけでも僥倖みたいなところがある（ちなみに C# には double より精度の高い浮動小数点数型が存在しないので分数解しか通らない、はず）。


次に、変に {N = 4000} とかいうギリギリを攻めたせいで TL が少し厳しくなってしまったこと。これは kimiyuki さんにテスターをしていただいた際に明るみになりました。まず、Python ではナチュラルな {O(N^2)} が TLE するらしくもうびっくりという感じなんですけどまぁこれは置いといて。問題は、分数クラスがちゃんとしていて毎回約分するようなものだと毎回 {\log} がかかって 5sec でも TLE することがあるらしくにゃーんという感じでした。

それと相反して {O(N^3)} が通っていたりもして、それは本当にびっくりなんですけど。というのも、オーバーフローをさせる関係で今回ちゃんと最大ケースを作っていて。しかもそれの答えが 23億 とかで。でも一つ一つ数え上げて 4sec ちょいで通っていて。もうC言語ってなんなんだよ、という感じ。

それと★4に昇格したのも誤算の一つで。おそらく {N = 4000} のせいで解法が {O(N^3)} の全探索から一つ {\log} に落として高速化、というプロセスを辿りづらかったのかも？ 部分点というか部分ケースがあってまずそっちが通るかどうか試す、みたいな方針でいったらもう少し楽に解かれたのかも。そもそも {O(N^2 \log N)} が通る制約に見えなくてずっと {O(N \log^2 N)} 解を考えてた、とかがあったらめっちゃ申し訳ない。



でもまぁストックのクソ問が思ったよりいい感じな問題になった（ほんまか？）のでまぁよかったかなぁ。とは言ってもストックのクソ問の中でもまだマシなほうなので残りのストックは本当に日の目を見ることがないかも……。

ハルコン2016 参加記

ハルコン

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




カービィやスマブラなどで有名なハル研究所が開催していたプロコンに参加していました。

www.hallab.co.jp


期間は11/7 ~ 11/25 で2週間以上あり、まぁいわゆるマラソンマッチです。
私がコードを書き始めたのは多分11日くらいなので、ちょうど2週間くらい参加していたことになります。



最後に順位表を見たときは6位だったので、再評価でいい値が出たり上がコケたりしてくれれば、賞金がワンチャンありうるかも…？



こちら、提出したコードにめっちゃコメントを書いたものです。読んで。

ハルコン2016でのrian_tkbのコード · GitHub

そのうち、自分の方針をまとめた解説記事みたいなのも書きたいと思ってます

（マラソンやったことないのでビームサーチとか焼きなましとか言葉しか知らないので、今回も盤面評価すらしていないので多分他の人とは方針が全然違いそう）



以下、期間中の関連ツイートを適当にまとめたもの


C++書けないマンとしてはな


誤差の処理とか、ちゃんとREADMEに書いておいてほしかった（コードを読解した）
C++書きたくないマンとしてはな
最初、1ターン目からビームが打てて、かつ次に打てるのがその40ターン後だと思っていた、けわしい
（実際には、最初にビームを撃てるのは40ターン目で、次に打てるのはその41ターン後）
ようやく主なバグが取れてまともなスコアが出る

普通のオンラインジャッジみたいに1ケースずつ動かし直してると思ったら1回で200ケースまとめて動かしてたでござる
探索の深さを増やすようにして2位まで更新
（この時期ですでにhirokazuさんは58000台を出してたのか…）
かっこいい…
2円の共通接線はめんどいので結局別の方法で解決しました
無限にバグが仕込まれているのでもうダメ
2位争いが熾烈になり、程なくして置いていかれる
これも地味につらかった
このツイートをしたら翌日には修正が降ってきてて、もしかして監視されてる！？ ってなった

C++書けないマンとしてはな

めっちゃTLE

残り1日を切り、更新できず賞金ボーダーから置いていかれて焦る

残り1時間を切ったタイミングで、乱数で回数を回す方向にシフトしたら突如として6万を切り、なんやねんって言う
終了直後の方針ツイートとか色々




初心者が作問して思ったこととか

これは
ひとり Advent Calendar 2016 - Adventar
の6日目の記事であり、かつ
Competitive Programming Advent Calendar 2016 - Adventar
の6日目の記事でもあります。



簡単な自己紹介とか

競プロアドベントカレンダーに載せさせていただくので多分5億人くらいが見てくれるだろうと予想して、少し自己紹介を書きます！

いま大学3年で、競プロを始めたのが大学入ってすぐくらいだったので、なんだかんだ2年半くらいやったことになります。
コード祭り本戦には3回とも出ていて、2015だけパーカーをもらえました。

SRM

https://www.topcoder.com/members/rian/details/?track=DATA_SCIENCE&subTrack=SRM
https://competitiveprogramming.info/topcoder/srm/history/rian

最近低迷していて、今はギリギリ黄色です。
Div1Easyが解けないことに定評があってつらい。

一番成績の良かった回は0完7撃墜350点です。
https://competitiveprogramming.info/topcoder/srm/round/16776/div/1

Codeforces

riantkb - Codeforces

最近始めました。ギリギリdiv1。
一応調子が悪くなければ2完できるみたいな感じっぽいしdiv2に落ちたくない。

AtCoder

https://atcoder.jp/user/riantkb
http://kenkoooo.com/atcoder/?kind=user&name=riantkb

黄色です。writer権はちょっと得られそうにないです。
前はけっこうちゃんと埋めてたんですけど最近はとてもサボっていてダメ。

作問履歴

yukicoderの方で何問か作問をしました。
りあん🐺☔️⛄️さんの問題一覧 - yukicoder

一番最初に作問をしたのが去年のあどべこんの12日目で、
www.adventar.org

こちらの問題になります。
No.319 happy b1rthday 2 me - yukicoder


そして先月、5問中4問が自作の問題なコンテストを開催させていただきました。
rian.hatenablog.jp


なので、作問を始めてからちょうど1年間で7問yukicoderで作問させていただいたことになります。


本題

記事のタイトルが「初心者が作問して思ったこととか」ですが、とりあえず一番強く感じるのはやっぱり、

作問って難しい！！！

です。その中で、具体的にどういうところが難しいとか、どういうところに苦労してるみたいな話を書きます。

誰か作問のプロ、作問テクみたいな記事書いてほしい

難易度・分野の制限

まぁ当然ですが、自分が解けないレベルの問題は作れません。
さらに、自分が苦手とする分野の問題は本当に作れません。
自分はグラフの問題が本当に苦手で、逆にDPやsegtreeを用いると解けるような問題が比較的好きなので、実際にyukicoderで作問した★3以上の問題(5問)はDPが2問、BITを使う問題が2問、数学が1問となっていてひどい偏りようです。

作問のプロ各位は一体どれだけの地力と隙のなさをお持ちなんだ、って感じ。

また、証明はしてないけどきっとこれで通るやろ！ みたいな解法は自分がコンテスト参加者なときは好きに投げられますが、自分が作問側の場合はちゃんと証明しないとひどいことになりますし、なんかコスパが良くない気がします。特に自分は嘘考察をすることに自信があるのでつらい。

良問が作れない

つらい。クソ問ばかり量産されます。

自分の作った問題の中でそこそこ良問なのでは？ って思っているのが、
初作問のNo.319 happy b1rthday 2 me - yukicoderと、
最近のNo.448 ゆきこーだーの雨と雪 (3) - yukicoderなのですが、
どちらも解法からではなく先に問題概要を思いついた、という共通点があります。

上のツイートでも言っていますが、なんか個人的には「このアルゴリズムを使う問題を作りたい！」とか言って作ろうとするとクソ問しか産出されず死亡、みたいなことが多いです。きびしいせかい。

というか初めての問題であるところのNo.319 happy b1rthday 2 me - yukicoderがもはやピークだったのでは？ という危惧があります…

テストケース作成が大変

作問をすると自動的にテストケースも作らなければなりませんが、強いテストケースを作るのがとても難しいです。
嘘解法を落としたり、TLE解をきちんとTLEにしたりするのがとても大変。というかできない。

特に後者は C++とかいうクソ速クソ言語のせいで とてもきびしい。C#解よりオーダー悪いのに爆速、みたいなこともあってもうなんやねんという感じ。

そもそも想定解法が正しいのかとても不安

毎回、出題してからACされるまでビクビクした時間を過ごしています。
テスターってすごいだいじ。

C++はクソ

C++はクソです。

想定解法で解いてほしい

平衡二分木で殴った人は早く解説記事を書いて。
No.449 ゆきこーだーの雨と雪 (4) - yukicoder


誰か作問のプロ、作問テクみたいな記事書いてほしい

書いてほしい。



ところで

ただいま、Advent Calendar Contest Advent Calendar 2016 が開催中です！

www.adventar.org

私は今年も12日目に出題させていただけることになりました。多分★3で、去年のより簡単めだと思います。
こちらもどうぞよろしくお願いします！！！





明日の記事は、
Yazaten さんの「色々なアルゴリズムで「殴る」」と、
とこはるさんの「最近改訂した定式化ドキュメントまわりの話」
だそうです！ 楽しみですね！

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