ICPC2019国内予選参加記

ICPC2019国内予選に参加しました 結果は5完最速で4位でした 模擬国内予選がチームブン回って5位で、実際には模擬国内予選に参加していない同格クラスのチームも多くかなり心配していたので、本当に安心しました・・・

f:id:kort0n:20190713005108p:plain

終結

前日まで

模擬国内予選で構文解析が弊チームの圧倒的弱点であることが判明した為、ここから当日までこんなバチャも立てつつひたすら構文解析やってました

 

前夜

去年の国内予選の構文解析問題「数式探し」の誤読(各数字1桁とは限らないと思っていた)に気付く これなら出来そうだなあと言いながらやる 2時間程かかって絶望する 「明日の構文解析、Cあたりに自明で出るか、Hあたりに不可能で出てくれ〜〜」とか言いながら布団に入る

ところで僕はイベント前夜は全然寝られない人なんですよね。2時間ほど寝付けず布団を温めていました。

 

当日

 

1限があるせいで4時間くらいしか寝られなかった 休講にしろ

東大の国内予選では、プリンターは会場にあるものを他チームと共有するか、或いはチームの私物を持ち込んで使用するということになっていました 20チーム近くいるこの会場ではプリンターの使用待ち時間も痛く、ちょうどボーダー上にいるであろう我々は少しの時間も惜しむ為、プリンターを僕が持ち込むことになりました

 

プリンターを持って駒場着 マジで重かった 腕が破壊された

プリンターを起動して無線LANに繋ごうとする

 

 

 

あれ?eduroam繋げられないんだけど

 

 

どうやらこのプリンターはeduroamやUTokyo-Wifiを拾うことが出来ないらしい(なんか通信規格とかの問題?らしい) この辺から顔が引きつり始める

 

idsigmaさんが生協にUSBケーブルを買いにいく その間に適当にリハ通す

 

戻ってくる 繋ぐ プリンターが認識されない...

この辺からいよいよヤバいという空気が流れ始める

 

色々やるとPCがプリンターを認識してくれる 問題ページの印刷ジョブを投げるとプリンターが印刷を始める

 

「あー良かった!」

「何とかなったね!」

「じゃあ他の準備しよう」

 

などと笑いあっていると、明らかに問題文ではない謎の文字列が印刷されて出てくる は?

 

いよいよチームから完全に感情が消えておきもちになる コーチにチェックを貰う為の準備も必要なので、この辺で私物プリンターの使用を諦める 何で持ってきたんですか...?

 

意地が汚いので、部屋内唯一のプリンターまで徒歩2秒の席を確保する その後も他ユーザーアカウントのファイルが見られるようになっている等のトラブルを皆で必死こいて調べながら何とか対処してギリギリチェックが間に合う 確かこの時点で16:20くらいだった

 

本番

開始直後は各チーム問題を印刷するので当然プリンターが混む 一番最初に問題文の印刷権を手に入れる為、問題データをpdfファイルに変換してUSBファイルに突っ込むムーブを無限回イメトレしてた 後ろ見てなかったけど多分うちが一番速かったと思います

Aは流石に無なのでそのまま実装してAC なんとFAだったようで2つの企業賞を頂けました やったね

 

直後にBをidsigmaさんが実装に入り、Cをrisujirohが考察する とりあえず後ろを読むことに

Dはすぐには分からないけど暫く考えれば分かりそう

このEやりたくないですね 誰がやるんですか? 絶対僕がやることになるやつですね?

F難しそう 何だこれ

Gよく分かんない これもゴリゴリシミュレーション系?でもそんなのGに来るか?(まだ構文解析ということに気付いていない 流し読みが過ぎる)

幾何がHだと分かる (risujirohが)幾何が強く、FGあたりに(うちがギリギリ通せるくらいの)難問で来ると爆アドだったので少し悲しくなる

しかしその直後にGが構文解析だと気付く 明らかに見た目ヤバそうだしこれそんなに解かれないだろ やったね

 

 

idsigmaさんがBをAC 全体5番目だったらしい 速い

Cが少し実装を詰める必要がある問題だったらしいので、Dが出来た気になった自分が実装に入る

この時点では「押す必要のある回数が最も少ない場所の必要回数を+m回する これをnループやればok」とかいう今思い返すと完全に狂ってる解法を生やしていた よくこれで実装しようと思ったな

 

実装残り2行くらいになったところで、「いやこれ候補2箇所あったらやり方によってはおかしくならない?てかそもそもこの解法おかしくない?」と気付く 明らかに反例は作れそうなのだが、反例を頑張って考えるより20分のペナを差し引いてもジャッジくんに今すぐ教えてもらった方がプラスになると考えて投げる 当然WA

 

恥です。

 

 

明らかにやべー解法だったので、ソースコードと入力と出力を印刷してPCをrisujirohに譲ることにする

ところでDの入力はこれです           

 

f:id:kort0n:20190713012725p:plain

これが数十ケースくらい

これを印刷するとこうなります

f:id:kort0n:20190713013142j:plain

 

バカか?

 

これで印刷代500円くらい取られました 金返してくれ...

そしてこんな入力見せられても当然何も分かりませんでした 何で印刷したんですか...?

 

考えるとO(N^3)のdp解法が降ってくる risujirohがCを通したので実装に入る 実行にそこそこ時間掛かったけど無事AC

 

僕がDをやっていた間に他の2人がEの考察を詰めていてくれたらしくて、やるべきことを伝えられる 「じゃあよろしくね」と言われる

 

f:id:kort0n:20190713014104j:plain

 

3箇所くらい途中でバグらせつつも、40分くらいで実装+デバッグ完了 実行に10分くらい掛かるも無事AC ここ完全に神懸かっていた...

f:id:kort0n:20190713014539p:plain

ペナ差でBBQにも勝っていたらしい


その後は全員でFを考えて始める 誰も良い解法が思い浮かばない

PCが空いているのも勿体無いので、小さいケースでの実験コードを書き始める

これを無限にバグらせる 本当にE実装したんですか...?

実験コード書き終わった頃には終了10分前 流石にもう不可能なので、国内予選突破ほぼ確定を喜び合いながら雑談していた

合同バチャや模擬国内予選等々で全敗のheno_worldより上にいたのでへへーんとか言ってたら残り40秒でE通されて逆転された 犯罪だろ

 

アジア地区予選へ向けて

 そういう訳で、無事アジア地区予選に進めることになりました

WFに進むためには学内1位になる必要がある訳ですが、圧倒的格上のチームが2つ存在するのは厳しいですね

1チームだけなら何らかのアクシデントで運良く勝てることも無くは無いと思うんですが、2チームあると...参ったなぁ...

今年はセミファイナルというステージが存在するという噂もあるらしい?これは情報を待つしか無いですね

 

来年以降出る人へ

プリンターはちゃんと家で動作確認しろ

競技プログラミングのすヽめ

これはGUTアドベントカレンダー2018の12/20分の記事です。他の記事はこちらから

 ----おことわり----

この記事ではあえて専門的な用語は使わずに、高校卒業レベルの数学・情報・プログラミングの知識さえあれば読める記事に仕上げることを目標としています。既に競技プログラミングコンピュータサイエンスに精通している方が読むともどかしく感じる箇所も多いかと思いますが、ご容赦願います。

 

 

こんにちは。今年参加したGUTの活動は #GUTウニ紅白戦2018 のみなので、僕のことをご存じない方も大勢いらっしゃるかと思います。こるとんと申します。

今年のアドベントカレンダーでも、最近ハマっている趣味について書こうと思います。

 

皆さんは「競技プログラミング(通称:競プロ)」をご存知でしょうか?

 競プロの大まかな内容は、上ツイートに記載されている通りです(上記ツイートは、競技プログラミングのコンテストを開催する会社「AtCoder」の取締役社長のchokudaiさんによるもの)

...とは言え、これだけだと詳細が分からないと思うので、順に解説していきます。

 

競技プログラミングでは、定期的に「コンテスト」が開かれます。コンテストでは数問の数学的な問題が出題され、参加者達はそれを制限時間内にプログラムを使って解き、出来るだけ多くの得点を獲得することを目指します(得点の計算方法はコンテストによって異なるのでここでは割愛)。その結果に応じて参加者の中で順位が付けられます。

 

ここで注意するべきなのが、大抵の場合コンテストの参加者が考えるべきことは、「答えの求め方」ではなく、現実的な時間内に答えを上手く求めることが可能となるような、解の効率的な探索方法を考えることであるということです。

 

どういうことでしょうか。例えば、以下のような問題を考えてみましょう。

 

問題1

プログラムの実行時間制限:2秒

長さNの整数列a_1, a_2, \cdots, a_Nが与えられます。次に, Q個の整数の組l_i, r_i\left(i = 1, 2, \cdots, Q\right)が与えられます。各l_i, r_iについて, a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を求めてください。

 

制約

1\leq N \leq 10^3

1\leq Q \leq 10^3

1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)

1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)

 

N=5

a_1=1, a_2=3, a_3=6, a_4=2, a_5=5

Q=3

l_1=1, r_1=3

l_2=5, r_2=5

l_3=1, r_3=5

 

に対する答えは

10

5

17

 

貴方に求められているのは、制約を満たすような如何なる入力N, a_1, \cdots, a_N, Q, l_1, r_1, \cdots, l_Q, r_Qが与えられても、正しい答えを実行時間制限以内に出力するプログラムを書くことです。

「プログラムの実行時間制限」なるものは一先ず無視していただくとして。如何でしょうか。

 

恐らくプログラミングの経験がある方にとっては造作も無いでしょう。与えられたl_i, r_iについて a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を愚直に計算するプログラムを書けば、この問題は解決出来ます。

 

では、以下の問題は如何でしょうか。

 

問題2

プログラムの実行時間制限:2秒

長さNの整数列a_1, a_2, \cdots, a_Nが与えられます。次に, Q個の整数の組l_i, r_i\left(i = 1, 2, \cdots, Q\right)が与えられます。各l_i, r_iについて, a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を求めてください。

 

制約

1\leq N \leq 10^5

1\leq Q \leq 10^5

1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)

1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)

 

一見何も変わっていないように見える?いえいえ、制約のところが僅かに変化しています。

とはいえ、問題の内容は全く変わっていません。ということで、こちらの問題も、与えられたl_i, r_iについて a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を愚直に計算するプログラムを書けばok...

 

とはなりません。何故か。

皆さんご存知の通り、コンピュータは単純な処理を高速に実行するのが得意です。数千個の数の総和計算もあっという間にこなしてくれます。

では、どれ程多くの処理を要求しても、コンピュータはそれらを必ず一瞬で解決してくれるのでしょうか。答えは当然"No"です。コンピュータの処理速度にも限界があります。

それはどの程度なのか、一言で言い表すのは大変難しいです。ここでは、「『基本的な処理』を10^8回以下しか行わないならば、大体2秒以内に処理が終わる」ということにしましょう。

「『基本的な処理』って何だよ」と仰る方、ごもっともです。ここでは、以下のようなものを指すことにしましょう。

・2つの数の加減乗除の計算

・2つの数の比較

この辺について語り始めるとキリが無いので、今回はこういうことで...

 

このことを踏まえた上で、先程の問題1問題2を振り返ってみましょう。

問題1問題2において、前述の方法により問題の解決を試みる場合、それぞれ最高でどの程度の回数基本的な処理が必要になるのでしょうか?

各問題で、N, Qについて、最小値と最大値が決まっています。恐らくN, Qいずれも大きい方が大変でしょう。ここでは, N, Qがそれぞれ最大値を取る場合を考えます。

l_i, r_iはどうでしょうか。a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を求めるのが最も大変なのは、\left(l_i, r_i\right) = \left(1, N\right)のときです。このとき, a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}N個の数の総和ですから, これを計算するには基本的な処理をN-1回実行する必要があります。このようにして、整数の組l_i, r_iQ組与えられます。最も大変になるのは, Q回の処理各々でN-1回の基本的な処理を要求される場合で、このとき答えを出力するまでに基本的な処理をQ\left(N-1\right)回ほど要求されます。

 

では、ここで問題1問題2制約を振り返ってみましょう。

問題1では、1\leq N \leq 10^31\leq Q \leq 10^3という制約条件が与えられていました。これより、プログラムを実行する上で基本的な処理をQ\left(N-1\right)回実行することを求められたとしても、必要な基本的な処理の回数は10^6回程度しか要しません。つまり、2秒もあれば十分余裕を持ってプログラムを実行することが可能です。

一方、問題2では、1\leq N \leq 10^51\leq Q \leq 10^5という制約条件が与えられていました。ここで、プログラムを実行する上で基本的な処理をQ\left(N-1\right)回実行することを求められた場合、必要な基本的な処理の回数は10^{10}回程度となります。これでは、プログラムは2秒以内に全ての処理を終えることが出来ません。

 

お分かりいただけたでしょうか。問題2において、答えを出力するプログラムを作成すること自体は、ある程度のプログラミング経験がある人ならば難しくはないはずです。しかし、短時間の間に答えを求めてくれるプログラムを書く為には、答えを効率的に求める方法を考えねばなりません。これは難しい問題です。

これは他のパズルやクイズにおいては類を見ない問題です。そして、これこそが多くの人を魅了する競技プログラミングの醍醐味なのです。

 

では、問題2を解決するには、どうすれば良いのか。例えば、以下のような方法があります。

a_1, a_2, \cdots, a_Nが与えられたときに、新たな数列S_nを, 

S_0=0

S_n=S_{n-1}+a_n

と定義します。要は, a_1からa_nまでの総和ですね。S_1からS_Nを計算するときにそれぞれ2つの数の足し算を実行しますから, S_1, S_2, \cdots, S_Nの計算には計N回の基本的な処理を要します。

では、その後l_i, r_iに対し、a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}をどのように計算すればよいのか。実はS_nさえ求めていれば簡単で、a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}=S_{r_i} - S_{l_i-1}が成立しています。則ち、2つの数の引き算を行うだけで、a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を求めることが出来るのです。これより、Q組の整数の組l_i, r_iに対してa_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}を求めるには、計Q回の基本的な処理を実行すればよいのです。

以上より、この手法を取れば、答えを出力する為に必要な基本的な処理の実行回数はN+Q回です。これより、1\leq N \leq 10^51\leq Q \leq 10^5という制約条件のもとでも2秒で十分答えを出力することが可能であることが分かります。

 

如何でしたでしょうか。「答えそのもの」ではなく、「答えを効率的に探す/求める方法」を考えるという、少し変わった面白さが伝わっていれば幸いです。

 

競技プログラミングは以下のような方々におすすめできます

パズルが好きな人

これまでに見てきたように、競技プログラミングとは、一言で言い表せば「人より速くパズルを解くゲーム」です。パズルが好きな人はハマりやすいと思います。「一般的なパズルに飽きたので一風変わったパズルを解きたい」という方には尚のことおすすめできます。

人と競うのが好きな人

「競技」プログラミングですからね。コンテストは他の参加者との勝負です。

レート(実力の指標)を上げるのが好きな人

言及していませんでしたが、冒頭に紹介したchokudaiさんのツイートの画像にも載っていたように、競プロでは各ユーザーの実力の指標として「レート」という数字が示されており、コンテストの結果に応じてこれが変動します。そのレートに応じて、ユーザー名表記の色が変わる、というのが競プロの通例です。まるでGUTで流行った某音楽ゲームのようですね。レート中毒者にもおすすめ出来る趣味です。

 

この記事を読んで競プロに興味を持つ方が1人でもいらっしゃれば幸いです。それでは、この記事を終える前にもう1問。

 

問題3

プログラムの実行時間制限:2秒

長さNの整数列a_1, a_2, \cdots, a_Nが与えられます。次に, Q個の整数の三つ組t_i, p_i, q_i\left(i = 1, 2, \cdots, Q\right)が与えられます。各t_i, p_i, q_iに対し、以下のいずれかが成立します。

t_i=0である。このとき、1 \leq p_i \leq q_i \leq Nである。

このようなp_i, q_iに対して, a_{p_i} + a_{p_i+1} + \cdots + a_{q_i-1} + a_{q_i}を求めて、その値を出力してください。

t_i=1である。このとき、1 \leq p_i \leq N, 1 \leq q_i \leq 10^3である。

このようなp_i, q_iに対して, a_{p_i}の値をq_iに変更する。(出力を行う必要は無い。)

制約

1\leq N \leq 10^5

1\leq Q \leq 10^5

1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)

t_i, p_i, q_i\left(i = 1, 2, \cdots, Q\right)は前述の①, ②のいずれかを満たす

 

N=5

a_1=1, a_2=3, a_3=6, a_4=2, a_5=5

Q=3

t_1=0, p_1=1, q_1=3

t_2=1, p_2=2, q_2=7

t_3=0, p_3=1, q_3=3

 

に対する答えは

10

14

 

問題2と同じようにやればいい?t_i=1, p_i=1, q_i=100が来たらS_1, S_2, \cdots, S_Nを全て計算し直さないといけませんよ...

 

これの解法が知りたい方は、セグメント木(Segment Tree)で検索してみてください。

それでは。