2019-04-07

ICPC 2019 World Finals に参加しました

2019年 3/30 ~ 4/6 に、ポルトガルのポルトで行われた 2019 ICPC World Finals に早稲田大学チームの選手として参加しました。簡潔に書きます。日記 + 多少のコンテストの感想です。

3/30

朝11時に日本発、オランダ経由でポルトガルに行く。乗り継ぎのタイミングで、同じ飛行機に中国のチームとかITMOとかがいて来たなーという感じがする。 ITMOの人たちがお揃いの大学のパーカーを着ていて、かっこいいって思った。 (日本の大学のパーカーもかっこよければね、、)

向こうのホテルに到着したのは現地時間で23時ぐらいだったけど、時差ボケとか関係なく疲れ切っていたので即寝た。

3/31

この日は、公式イベントとしてはディナーだけだったので夕方までは市街地を観光した。

World Finalsのロゴにも入ってるタワーにも登った。市内を一望出来たけど、上があまりにも狭くて、通路・階段での行き交いも一苦労だった。

川沿いからの眺めが綺麗で、日曜というのもあって賑わっていた。

4/1

Registrationの日でした。

Registrationは午後からだったので、午前中はスポンサーセッションを聞いたり、ちょっとだけQuestをした。 JetBrainsのセッションではKotlinはいいぞみたいな話を学部生が受けるプログラミングの授業のサンプルを見せられながら聞いていた。正直Javaをちゃんと書いたことが無いので、どれくらい良いものなのか分からなかったけど、色々記述量が減りそうな工夫が見えて、いいんだろうなあと思った。

Registrationでは、Tシャツをもらった後に、チーム写真の撮影をした。僕たちの直前で筑波の人たちが撮影していて、あの情報量が多すぎる光景を生で見た(?)。

あと、インタビューを受けなきゃいけなくて、誰か一人が犠牲にならなければいけなかったんだけど、自分が犠牲になった。かなり詰まりながらの返答になってしまったけど、ちょっと使われていた。

4/2

ICPC ChallengeとOpening Ceremonyの日でした。

ICPC Challengeは、マラソン、3時間、PCはチームで1台、チームメンバー誰もマラソン経験が無いのでハチャメチャになって破滅した。

Opening Ceremonyは、とても広いホールに人がぎっしりで、スタッフがたくさんいるんだなあということを実感した。選手だけで133チーム×3人も集まるわけだから、それだけ大規模なんだよな、、

4/3

Dress Rehearsalの日でした。直接会場に移動するのではなく、一回全チームの受付を済ませてから、列になって会場に向かうのはなんか世界大会っぽい感じがした。

プラクティスでは、まずポルトガル配列のキーボードをusにremapして、対応する記号のシールを貼る作業から始めた。キーボード、別に対して高そうな買い物でもないしなんでusを揃えなかったんだろうと思っている。普段からずっとusキーボードを使っているので、バックスラッシュを押そうとしてEnterキーを押しちゃうやつをプラクティスでも本番でも何回もやってしまった。

キーボードに多少でも慣れる意味もこめて、1人1問は実装した。ちなみに、エディタは3人ともCLionを使った。起動してそのままデフォルトで使っても不便が無いので、初手の環境構築タイムが無いので、来年も使えるなら使ってみると良いです。

熱心にQuestをやっていたチームメイトが、コーチとかスタッフとかでガチでQuestをやってるやつらに勝ち目がないと悟ってこれ以上やるのを諦めてた。

4/4

World Final本番の日でした。

結果はこんな感じ： f:id:imulan:20190407194600p:plain

序盤はA~D、E~H、I~Kに分けてとりあえず問題を読み、それぞれA、E、Jが行けそうだとなったのでそれぞれ実装を詰めたりしながら進めて、3つ全部WAになった(ええ...)。

この時点で1時間経過してたので、もうペナルティを気にせず完数を伸ばすことだけを考えることにした。Jは嘘だったらしいので、Aに2人で考察を詰めてもらう。その次にDも詰めてもらう。

自分は開始から3時間、Eと格闘し続けていた。個人的に問題文が読みにくくて、解釈にとても時間がかかって、ただ最終的にこれは実装軽い問題だったなあってなった(大反省)。

そこからは、Hをryo_issyと方針を詰めて実装を任せて、yamadとGを考えて、SuffixArrayの構築っぽいことをしたいなーというお気持ちを伝えたら解法を出してくれた。木のダブリングパートの実装を詰めておいた。

凍結後にこの2問とも通って5完になった。最終的に順位がついてよかったです。

自分がEにあそこまでハマったりしなければ、B、Jも出来たかもという感じがして完全に力出し切れた、という感じのコンテストとは個人的になりませんでした。しかし、コンテストが終わった後はそもそもここに来れた事自体が奇跡みたいなものなのと、これでICPCのコンテスト本当に終わりだなと言う気持ちの方が強かったです。

Closing Ceremonyでは、yesnoを見ながら、最上位勢の異常さを改めて感じました(金メダルの4チームは本当に異次元すぎる)。東大3位おめでとうございます。凍結前1位だったのを見て、コンテスト中ながらに興奮したのを思い出します。

4/5

帰国日。

前日のClosingが21:30に終わって、そこからご飯を食べてからホテルに戻ってきたのが23:00で、この日は5:00に出発だったのでちょっとしか寝れなかった。その分飛行機で寝ればいいかと思ってたけど、合計で3時間くらいしか寝られなかった。

おわりに

上にも書きましたが、自分はこれでICPC現役引退となります。 B3の春から始めた競プロで、B3(3人集められずにICPC出れない)、B4(国内予選落ち)、M1(つくば大会12位)ときて、学生のうちに世界大会に出場できるなんて夢にも思いませんでした。

実際、ここ1年ぐらいの自分の競プロのモチベーションはICPCに支えられていましたし、それに加えて文字通りの生きがいになっていました。本当にチームメイトやコーチはもちろん、応援してくださった皆さん、研究室の先生や生徒にも感謝しかありません。

明日から労働が待っているので、新しいことの連続でこれからどうなっていくか分かりませんが、これからも義務感を感じない程度には競プロに関わっていたいなと思います。最後まで読んでいただき、ありがとうございました。

2019-03-12

WUPC 2019 H - Doki Doki Programming Clubs!

AtCoder programming

問題

H - Doki Doki Programming Clubs!

問題概要

$N$ 個の数列が与えられる。 $i$ 番目の数列 $A_i$ の長さは $K_i$ である。クエリ $(X,Y)$ とは以下の通り：

数列 $A_X, A_Y$ について、 $\displaystyle \sum_{i=0}^{\max (K_X, K_Y)-1} A_{X, \ i \ \% \ K_X} \times A_{Y,\ i \ \% \ K_Y}$ を $10^9 + 7$ で割った余りを答える

上記のクエリが $Q$ 個与えられるので、各クエリについて答えよ。

$2 \le N \le 200000$
$1 \le K_i$
$\sum K_i \le 200000$
$1 \le A_{i,j} \le 10^9$
$1 \le Q \le 200000$
$0 \le X_i , Y_i \le N-1$
$X_i \neq Y_i$

アイデア

まず、クエリについて、どのような処理になっているかを観察してみる。以下では、クエリ $(x,y)$ について、 $K_x \le K_y$ を仮定する。数列 $A_y$ の方が長いので、短い方の数列 $A_x$ を長い方に揃えることになる。例えば、 $K_x = 3, K_y = 8$ ならこんな感じ。

f:id:imulan:20190312214500p:plain

短い方の数列 $A_x$ を長い方に周期的に揃えて、積の和について考える。

f:id:imulan:20190312214716p:plain

ここで、問題で与えられた通りに短い方を長い方に毎回揃えて計算してしまうとTLEするので、短い方に揃えて計算出来ないかを考える。長い方のindexに注目してみると、短い方の長さ $K_x$ の剰余によって、どの要素との積になっているかが決定している：

f:id:imulan:20190312215153p:plain

よって、クエリに対して $O( \min (K_x, K_y))$ で計算したい時、数列 $A_y$ を周期 $K_x$ で分類した和(上の例で言うと、数列 $A_y$ に関する赤の和と青の和と緑の和)を用意しておけば良いことになる。

以上の考察から、短い方の数列に揃えてクエリを処理するためには、前計算として各数列 $A_i$ について、自分より短い周期について、その剰余で分類した和を用意しておく必要がある。

以下では、 $\sum K_i = S$ とする。この前計算は $O(S \sqrt{S})$ で実現することができる。その理由については、実際に前計算のコードを見てみるとわかりやすい：

// 前計算
// k[i] のdistinctな要素を列挙
vector<int> uk(k);
sort(uk.begin(), uk.end());
uk.erase(unique(uk.begin(), uk.end()), uk.end());
int UK = uk.size();

// 各数列 a[i] について、自分以下の周期の和を前計算
vector<vector<vector<long>>> sum(n, vector<vector<long>>(UK));
for(int i=0; i<n; ++i){
    for(int j=0; j<UK; ++j){
        int L = uk[j];
        if(L > k[i]) break;

        sum[i][j] = vector<long>(L);
        for(int l=0; l<k[i]; ++l){
            sum[i][j][l%L] += a[i][l];
            sum[i][j][l%L] %= mod;
        }
    }
}

$i$ のループと $l$ のループを合わせて、ちょうど $S$ 回のループになっているので、ループが回る回数は $O(S \times UK)$ となっている。ここで、 $UK$ とは、 $K_i$ の種類数となっているが、数列の長さ $K_i$ の種類数はたかだか $O( \sqrt{S})$ である。

できるだけ種類数が多くなるような状況を考えてみると、数列の長さは $1,2,3,4, \ldots$ と、長さを1ずつ増やしながら1つずつ数列を用意する、という状況になる。これを長さ $t$ までもれなく揃えたとすると、長さの合計は $1+2+ \ldots + t = \frac{t(t+1)}{2}$ となり、 $\frac{t(t+1)}{2} \le S$ なので、種類数は $O( \sqrt{S})$ で抑えられていることが分かる。

以上で、前計算は $O(S \sqrt{S})$ であることが確認できた。以下ではクエリ処理について確認する。

一度来たクエリについてはメモ化して答えることにし、新しいクエリについては $O( \min (K_x, K_y))$ で計算することにすると、計算量は $O( (S+Q) \sqrt{S} )$ となっている。これを示すために、2つの場合に分けて考える：

$\min (K_x, K_y) \lt \sqrt{S}$ のとき

1クエリに対して $O( \min (K_x, K_y)) = O(\sqrt{S})$ で処理できるので、クエリ全体について $O(Q \sqrt{S})$ で処理できる。

$\min (K_x, K_y) \ge \sqrt{S}$ のとき

この場合は、 $K_i \ge \sqrt{S}$ となるような数列はたかだか $\sqrt{S}$ 個しか存在しない。この条件を満たす数列 $A_i$ に対して、 $i$ 以外の数列とのクエリが全部与えられたとしても、そのクエリ合計で $O(S)$ で抑えられているのは明らか。以上のことから、クエリ全体について $O(S \sqrt{S})$ で処理できる。

以上より、計算量は全体で $O((S+Q) \sqrt{S})$ となり、これは十分に高速である。

実装(C++)

裏紙

ほぼ競プロ、たまに日記