うにゅーん、って感じだ

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

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

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 東京オンサイトにいく予定です!