うにゅーん、って感じだ

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

Advent Calendar Contest 2017 C hel__world (2) 解説（？）

Advent Calender Contest yukicoder

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 4日めの記事です。
adventar.org
まだまだ全然埋まってないので助けてください。

解説（？）

問題はこちら。テスターをしました。
No.603 hel__world (2) - yukicoder


まずは、嘘が見つかってしまい大変申し訳ありませんでした。


さて、問題についてですが、本質というかもはや 99% は
{\displaystyle \prod_{1 \leq k \leq n} {}_{x_k}\mathrm{C}_{a_k}} を最大化するような {X = \{ x_1, ... , x_n \} \ \sum X = Const}
を探す問題になります（詳しい式は解説や元ネタ問題の解説の方を参照してください）。

https://yukicoder.me/problems/no/295/editorial の priority queue 解の方を読んでもらえばわかりますが、{x_k} の値を 1 増やす場合、全体の値は {\displaystyle \frac{x_k + 1}{x_k - a_k + 1}} 倍になります。そしてこれらは {x_k} の値が増えていくと単調に減少していくので、つまり今選べる中で一番大きいものを貪欲にとっていけば良い、ということがわかり、priority queue 解が生まれます。

ここで、お、これ二分探索したくない？ と思うはずです。きっとそう思うのです。
でも、実はそこからの道のりが意外と長いです。

今回は、解説というより、方針が思い浮かんでからここがつらかったダイジェスト、みたいな感じでお送りしたいと思っております。

（実は writer 解はこれとは違いますが、自分にはよくわからないです。）

二分探索の中で二分探索？

ここはそこまで大変とかいう話ではないですが、まず一つ重要なところだと思うので。
二分探索をするとなると、まずは、ある実数 {m} に対して、 {\displaystyle \frac{x + 1}{x - a + 1} > m > \frac{x + 2}{x - a + 2}} となるような {x} を探したい気持ちになります。
もちろんこれは二分探索をしても良いのですが（多分）、{c = x - a + 1} とおくと、これはそのままそこを使う回数（つまり求めるもの）と一致していて、かつ上の式が
{\displaystyle \frac{a + c}{c} > m > \frac{a + c + 1}{c + 1} \Leftrightarrow \frac{a}{c} > m - 1 > \frac{a}{c + 1} \Leftrightarrow c = \lfloor \frac{a}{m - 1} \rfloor}
となり、定数時間で求められるようになります。

分数の比較

二分探索をする上で分数の比較が必要不可欠ですが、普通にかけ算をしてしまうとオーバーフローしてしまいます。
そこで、2 つの分数 {\displaystyle \frac{a}{b}, \frac{c}{d}} に対し、

  1. {a / b} と {c / d} を比較する
  2. 同じだった場合、その値を {e} とおき、{\displaystyle \frac{d}{c - d \cdot e}, \frac{b}{a - b \cdot e}} に対して 1. を行う

とすると、log 回くらいで比較が完了します（今回は分母と分子の差が小さいことが保証されているのでもう少し早そうですし、オーバーフローしないところまで小さくなったらかけ算で比較してしまうと良いです）。

combination の計算

これはみなさん大丈夫だと思うので省略します。前もって階乗とその逆数を計算しておいて、n を Mod 取って n - k を Mod 取ったものより小さくなったら 0 、そうでなければその間を計算して k! で割る、みたいな感じ。

精度が足りない

これで全て大丈夫、かと思いきや、このままだとまだ通りません。というのも、m の値が 1 付近で精度を求められ、 1.00000000000000000114514 みたいな数を扱う羽目になります。でもそこについては簡単に対処できて、m ではなく m - 1 の値を決めることにより探索範囲を [1, 1e6] から [0, 1e6] に変更して対処できます（1 付近でないところで精度を求められると死にますが、恐らく大丈夫だろうという結論になりました）。あ、ちなみにもちろん long double じゃないと精度が足りません。

時間が足りない

これで今度こそ大丈夫、かと思いきやそうではありません。二分探索時に要求される精度が高いのでどうしてもループ回数が多くなってしまい、微妙に間に合いません（高速化のプロなら間に合うかもしれないです）。
そこで、二分探索をする範囲を絞ります。
上で定義した {c} と式変形で得られた式を用いて、
{\displaystyle a_k > (m - 1) \cdot c_k > a_k - (m - 1) \\ \displaystyle \Rightarrow \sum a_k > (m - 1) \cdot \sum c_k > \sum a_k - n \cdot (m - 1) \\ \displaystyle \Rightarrow \frac{\sum a_k}{\sum c_k} > m - 1 > \frac{\sum a_k}{n + \sum c_k}}
とすることができ、これで二分探索の範囲を絞ることができ（自分の雑な計算では二分探索のループが最大 40 回程度で終わるという結論になりましたが本当かどうかは知りません）、これでようやく通るようになりました。


という感じで、テスターをしながらとても大変だなぁと思っていました。

難易度設定については、そもそもネタ元問題が★5 あるかなぁという気持ちはあって、ネタ元★4 今回の★5 くらいが適正かなぁと（個人的には）思いました。

DDCC2017 本戦 C - グラフいじり 解説

AtCoder DDCC

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 1日めの記事です。
adventar.org
全然埋まってないので助けてください。

（1日目から遅刻したので、これより先にnmさんの2日目の記事が公開されました）

解説（？）

りあんちゃん「で、今日やる問題ってどんな問題なの？」
たくぼくん「今日の問題はこれ。DDCC2017 本戦 の C 問題 だよ。」
りあんちゃん「それじゃあ問題を読んでみるね。有向グラフが与えられて、一つ以下の辺の長さを変えて、全てのサイクルの長さを 0 にできるかどうか…？ なんかもう何を言っているのか全然わかんないよ……」
たくぼくん「うーん、確かにそうだね。じゃあまずは『全てのサイクルの長さが 0 である』というのがどういう状態なのか、どうやれば判定ができるかを考えてみようか。」
りあんちゃん「全てのサイクルの長さが 0…。うーん、そもそもどういう状況なのか全然よくわからないよ……。」
たくぼくん「そうだね。じゃあ少し言い換えて、『どの頂点からどんな経路をたどってその頂点に戻ってきても、必ず距離が 0 になる』と言い換えてみようか。」
りあんちゃん「えっと……なるほど！ 確かにそう言い換えられるね！ でもそれってどういうことなんだろ……」
たくぼくん「一応そこまで言い換えられれば十分ではあるんだけど、じゃあもう少し言い換えようか。マイナスの距離、とかは少し考えづらいから、距離じゃなくて何か別のパラメータが上下していると考えてみようか。例えば……高さとか。」
りあんちゃん「つまり、各頂点に高さを設定して、プラスの辺はその分高い、マイナスの辺はその分低い……ってこと？」
たくぼくん「そう！ それじゃあそのとき、条件はどう言い表せる？」
りあんちゃん「えっと、距離が 0 ってことは高さの変位がないってことだから、それじゃあ一周してきても高さが変わらない、ってことだ！」
たくぼくん「そういうこと！ つまり全ての点の高さが矛盾なく定まることと同値なんだ。」
りあんちゃん「じゃあ適当な頂点の高さを適当に決めて、全ての頂点が矛盾なく決まればおっけーってことか！」
たくぼくん「今回は強連結であることが保証されているからそれで大丈夫。強連結でない場合も逆辺が簡単に張れるから同様にできるはずだよ。」
りあんちゃん「これでやっと判定はできたけど、長さを変えてこうなるかどうか、はどう判定すればいいの……こんなのできるの？」
たくぼくん「実は長さを変える場合、長さをいくつにすればいいのか、というのはさっきの高さの話を考えるとわかるよ。」
りあんちゃん「あ、そっか！ 2 点の高さがわかっていれば、その間の辺の距離は高さの差分である必要があるんだね。」
たくぼくん「つまり、その辺の本来の長さ、というのは、その辺を除いたグラフで各頂点の高さを求めてやればわかるんだ。」
りあんちゃん「なるほど〜！ 計算量的にも間に合いそうだし、これが答えだね！」
たくぼくん「残念ながらこれだと TLE するんだ。内部の高さを求めるところが O(N) じゃなくて O(M) かかるからね。」
りあんちゃん「え〜〜〜！ じゃあどうすればいいの？」
たくぼくん「ここまでくればあともう少しだよ。内部の高さを求めるところの計算量は落ちなさそうだし、消す辺を選ぶところをどうにかして O(N) にできないかな？」
りあんちゃん「え、何言ってるのそんなの無理でしょ。」
たくぼくん「そう言わずに……。消す辺は 1 本ずつじゃなくて、とある頂点が終点であるような辺全てを一気に消しても大丈夫なんだ。」
りあんちゃん「うーん…？？？ ちょっとわかんなくなってきた。どういうことなの？」
たくぼくん「なんかだんだん受け答えが雑になってきたなぁ…。つまりどういうことをするかというと、ある頂点からスタートして、その頂点に帰ってくる辺以外に対して高さを計算する。その時点ですでに矛盾があったら NG だけど、そうじゃない場合は最後にその頂点に帰ってくる辺全てを見て、それらが繋いでいる2点の高さとその辺の長さとの矛盾をチェックして、矛盾の数が 1 つ以下なら ok、ってことになるんだ。」
りあんちゃん「うーん。つまり、始点に戻ってくる辺っていうのは、高さを計算するのに関係ないから、互いに影響しないからまとめて矛盾をチェックできる、ってこと？」
たくぼくん「そういうこと！（台本棒読みだけど……）」
りあんちゃん「まぁなんとなくわかったような気がしなくもないけど、でもこんなのコンテスト中に思いつくの？」
たくぼくん「コンテスト中はこんなちゃんと理路整然と考えられてはいないけど、でも考察をしていればいずれ近いところまでは十分思いつけるとは思うよ。やっぱり『全てのサイクルの長さが 0 である』って条件をどう自分にとってわかりやすい言葉に言い換えられるかがポイントだったのかな。」
りあんちゃん「ふーん……。」
たくぼくん「（もう飽きちゃってる……）」

あとがたり

この問題は、予選を勝ち上がったメンバーで行われる本戦という舞台でけっこう虐殺が行われたのと、公式解説がなんやねん、と（個人的には）思ったので自分の解法を書きました。
まぁコード祭りもありましたしもう忘れている人が多そう…。
公式解説、なんやねんとは思いましたがあちらの方が汎用性が高そうで、こういう問題を安定して通すには多分公式解説の方法がさっとできると良いのだろうと思います。まぁ800点問題に取り組む人はこれくらい常識でいてほしい、ということなのでしょうか（つらいにゃあ）。


さて、上の方でも書きましたが解説アドベントカレンダーの埋まり具合があまりよろしくないです。
1日目から遅刻していることからも分かる通り、自分には残りの日を埋めるパワーはないので、ぜひみなさん助けてください！

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

CODE FESTIVAL

しました。

atnd.org

9/30(土) にやりました。思ったより予選B が近く、慌てて開催 3日前くらいに大枠を固めて参加者を募集したのですが、結果15人もの人に集まっていただき、とても嬉しかったです！

昨年も同じような練習会を行った のですが、昨年との一番の違いは「学外の人も参加できるように貸しスペースを借りて開催した」というところで、実際に人が集まらないととても悲しいことになっていたと思うので本当に感謝です。
（これは他の大学の人からすると意外かもしれませんが、うちの大学は競プロ関連活動がそこまで盛んでなく、練習会などが盛んに行われている他の大学の方々が羨ましいなぁという感じ。今回貸しスペースを借りたのも、学内だけだと全然人が集まらなさそうだと思ったからというのがあります。）


前日

昼 〜 夜


バチャコンの問題セットが決まっていないがライブを見に行く

深夜 1時半ごろ 〜


多い


こんなことをしている場合ではない


使おうと思っていた問題が試しに投げて見たら IE になり悲しむ（ちなみにこの問題でした https://beta.atcoder.jp/contests/autumn_fest/tasks/autumn_fest_06 ）


4時前にようやく完成


結局 11問 3時間になりました


当日


アナウンス


会場がわりとあっとこ本社に近い（新宿御苑はさんで反対側くらい）


スポンサー 欲しい！！！（5000兆円のフォントで）


到着

思ったより会場がちゃんとしていてよかった。

当初の予定より 10分遅れで開始


1時間20分ほどで全ての問題に AC がつく


やはり 2時間40分だと短かったらしく、オンサイトに聞いて 20分延長


2時間半ほどでこばさんが全完！


コンテスト、こんな感じになりました
https://not-522.appspot.com/contest/6671465998974976


コンテスト終了後、適当な解説をしたのち簡単な懇親会をしました。

www.slideshare.net



解いてね


以下、適当なツイ






このお二方とは、次の日の KUPC でもたくさんお話しできました🙌



練習会、やっぱりオンサイトめっちゃ楽しいので色んな人にどんどん開いて欲しい〜！

JAG夏合宿2017（+コード祭り2017予選A）参加記

ICPC

9/22-24 に、JAG の夏合宿（http://acm-icpc.aitea.net/index.php?2017%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E6%A1%88%E5%86%85）に行ってきました。
今年初めて icpc アジア地区への切符を手にしたので、夏合宿は初参加！

宿泊部屋が足らないという話だったので、毎日お家に帰りました（ただ思ったよりオリセンが家から遠く、片道1時間かかったので宿泊したほうが良かったかもしれない）。


今回、チームメイトの一人は学会か何かが被ってしまったので、kurukuru-sushi からは りあん（@rian_tkb）と 葦（@Ashurnasirpal）が参加し、毎日一人チームに迎え入れる形でコンテストに出場しました。

1日目

1日目はすぬけさんのセット（Japan Alumni Group Summer Camp 2017 Day 1 - AtCoder）


この日のチームメイトはすみけんさん（実は高校の一つ上の先輩だったことがコンテスト中に発覚しびっくりした）。


Macbook Air に ﾘｱﾌｫ を刺しているという謎環境なので、コンテスト前に簡単な操作方法のレクチャーをする（これは結局 3日間ともした）。

コンテスト中の流れ

（記憶が薄れてきているので細部が違っているかもしれないですがご容赦）


コンテスト開始。問題が1セットしかなくホチキスどめされていたのでまずはホチキスを丁寧に外し、問題を机にばらまく。

自分が最初に手に取ったのは E で、問題文の上部に BNF が見えたので問題概要を全く読まずに 3秒で葦くんに投げる（kurukuru-sushi では構文解析問題は全て葦くんに投げるという戦略を取っている）。

次に D を読むと、これは簡単な算数。早速コードを書き始める。途中少し詰まった（直角でないところを直角だと勘違いしていた）ところですみけんさんが J を一瞬で通す。その間に自分もミスに気づき、続けて D も AC。

次は多分 K に取り掛かっていたと思う。問題文を読んでこれはどうせ C_i - G_i でソートしてほいするやつでしょ、とか言いつつ書く。マイナスがついたりつかなかったり、どっちがおっきいとどうなる（自分は通す直前までコストとゲインを逆だと思っていた）とかがややこしいのでそこらへんを色々試すが、どうしてもサンプル1 とサンプル2 が同時にうまくいくようなことがない。そうこうしているうちにすみけんさんが A をいけそうとのことだったので書いてもらう。

K はこれ以上考えるとドツボにはまりそう（というか既にはまっている）なので、ここで葦くんに投げた E の様子を見にいく。問題を読むにそこまでつらそうな問題には見えず、スカラーは要素数1 のベクトルじゃない？ と言ったらなんか解決したらしい。

その間にすみけんさんが一人で A を通し、葦くんに E を書いてもらう。手の空いたすみけんさんに K を投げ、その間に自分は H を考える。制約がクソでかいので、明らかにうまい方法があるやつ。こういう問題はまず条件を緩めた問題から考えると良い ので同じ動きを連続でしてよい場合を考えると、3つのうち高々2つの動きしか使わないことが判明。ということは交互にやっていって片方だけ残ってしまったらくるっと回る動作を間に挟めばよい、とわかる（よく考えるとこれが最短ムーブになる証明をしていない）。

ちょうどその頃 K のサンプルを手で試していただいていたすみけんさんにより、C_i + G_i でソートしてほいだということが判明。そこで自分が C と G を逆と勘違いしていたことも判明。

そのあと順位表を見て F が通されているように感じたので F を解けそうな目で見る。するとぱっと見ごつかった問題が実は自分より後での各文字の最初の登場位置と、自分より前での各文字の最後の登場位置がわかれば解けることがわかり、かつそれは普通に各文字から前後に伸ばしていけば間に合うので、途端に解ける問題に大変身した。

そのあたりで葦くんが E を通し、続けて自分が H, K, F と AC。E が通ってから F が通るまで 30 分かかっていない。

残る問題は 4 問で、正直人間に解ける問題が残っていなさそうに見える。

残り40分くらいで、葦くんが G が最小費用流になりそうだと気がつき、自分がライブラリの写経を始める（G をぱっと見フローと気づけなかったのはとても反省…）。写経をしている間に 2人の考察によりじわじわと解法がまとまり、コードを書くが、実装が重くしかも若干バグらせたため時間切れ、とても悔しい（でも結局その後書き上げても通らなかった）。


結果は 7完 7位。上にはガチプロしかいないので人類トップ、ってことでまぁ僥倖かなぁという気持ち。



普通に疲れていたのでそそくさと帰宅してしまった…。


2日目

2日目はこどふぉのgym（http://codeforces.com/gym/100633/）


この日のチームメイトはあるごんさん。あるごんさんを kurukuru していく。

コンテスト

（あまり覚えていないし疲れてきたのでここは適当です）

全体的に readforces だった。

最初に L を読んでいけそうに思ったが、誤読したのとまぁまぁバグらせて（無駄に O(N) で解いていた）結局 5WA。冷え冷え〜。

あとは B が簡単な DP だったのでささっと実装したり（Mod が 10億9 でキレた）、G の forward というのが時計回りか反時計かわからずあるごんさんに読んでもらい、そのまま解法を伝えて書いてもらったり、葦くんが H の問題文読解に成功して AC したり、I をわかんねぇなぁ〜、と言いながら貪欲を書いて AC したりしました。


結果 5完で、オンサイト 6位かな？ 全体的にキツすぎるセットだった…。


この日は Hec さんとけっこう話をしていた気がする。ABC-D じゃない 400 は怖いよね、という話もした気もする。


コード祭り予選まで少し時間があったので新宿で弐寺をしてから帰った。SP六段です。


コード祭り予選A

その日は予選A がありました（CODE FESTIVAL 2017 qual A - AtCoder）

ボーダー予想として、本戦ボーダーは4完早解き、ありがとう祭りのボーダーも4完になるかなぁ、と踏んでいたので、D から開くことを決意。すぎむさんの 700 なので AND Grid のような思いつき構築ゲーが出るかもと予想していたので、死ぬ気で解きにかかるぞという強い意志。


結果、D をうまく思いつけて運良く 27分ほどで通せて、最後に A で 1RE（文字の長さが 4未満の場合に死んでいた）したものの全体 75位、日本人 19位という成績でした。勝ったなガハハ！

d が 2 より大きい偶数のときに各色が大きな正方形を描いていることに、ツイートする用の図を書いているときに気づいた（ア）

D はもちろんつらかったけど他の問題も普通につらくてつらいセットだなぁとなった。


2回目のパフォ 2800 超えによりレートもそこそこ上がった。嬉しい。

3日目

3日目は JAG のセット（Japan Alumni Group Summer Camp 2017 Day 3 - AtCoder）


この日のチームメイトはめるさん。めるさんを kurukuru していく。

コンテスト中の流れ

めるさんが A を読んですぐ AC。葦くんが B を読み、実装に入る。自分は C の読解に苦しむ（グリッドに整数が記入されている的な設定でもよかったのでは？）。

葦くんが苦しみながらも B を通し、自分も苦しみながら C を通す（上から下じゃなくて左上から右下に斜めに埋めていってしまったので実装がクソつらかった）。

D はC に苦しみつつも問題概要を聞いていて、さすがに bitDP だろうという気持ちになる。ぱっと見 {O(2^{2N})} っぽいが部分集合の部分集合はもうちょいオーダーが落ちそうに感じ、この方針で行こうと考える。
あいこじゃない遷移は簡単だが、あいこになる確率がとてもつらい。ただ、うまくベン図を書いて考えると {O(N)} で求まり、勝利。AC。

そうこうしているうちに葦くんが F の考察をまとめる。プロ。そのまま葦くんが書いて AC。

E については、自分が + で区切ればいいというのを思いつくが、そのまま区間DPしても 2500^3 になりダメ。すると葦くんが解法を閃いてくれる。プロ。それは自分が実装を行い、AC。実装はめるさんに投げてしまってもよかったかもしれないなぁ。

あとは G を考えていたが、きっと解法は枝刈りではないだろう…、と思ってしまっていたので、相性が悪いと思いつつもフローを考えたりしていて、結局そのまま終わってしまった。6問解いた時点でもう少し時間が残っていたら枝刈ろうと思えていたかもしれないが、まぁ致し方なし。

あと、G をほぼ諦めていた段階で D の計算量を計算したらやはり部分集合の部分集合は {3^{N}} 個で、{O(N \ 3^{N})} になっていた（大学受験数学が得意）。



結果 6完で、オンサイト 7位？ 2日目と同じくらいキツいセットだった…。


まとめ

競プロづくしでとても楽しい3日間でした！
コンテストの内容については、さすがにこれは通せなきゃダメだったなぁ…、みたいなのはほとんど無かったような気がしたのでまぁ悪く無かったと思います。ただ、どの日も半分以上の問題の実装を担当したので、もう少し配ればよかったかもなぁとは思いました（自分はそこまで実装の速い方ではない）。

国内予選突破という目標を達成してしまったので来年の ICPC はコーチとして出ようかなぁとか思っていたのですが、やっぱりチーム戦たのしすぎなので来年も選手として出ているかもしれません。まだわかりません。



懇親会的なものがなかったり帰宅勢だったりしたので、あまり交流ができなかったのが少し心残り……。
次は KUPC 東京オンサイトにいく予定です！



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/

コンテスト後





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

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

あとがき

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

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