裏紙

ほぼ競プロ、たまに日記

会津合宿2017 参加記

diary

9/18~9/20の2泊3日で、これに行ってきました

atnd.org

競プロオンサイトイベントはCODE FESTIVALしか行ったことなかったので、とてもワクワクしながらオンサイト行きました。

会津大学に初めて行ったんですが、自分が通っている大学と比べてかなり景観が良くて、自分もこういう感じのキャンパスに通いたいなってなった*1。

台風一過で、気温もちょうどよく、天気も良くてかなり過ごしやすかったです(小さい頃福島県に住んでいたのでなんとなく分かるのですが、夏はめちゃくちゃ暑いし冬は雪が大量でつらそうなのでかなりいい時期だと思います)。

ちなみに、宿は同じ大学の後輩2人と3人で泊まりました。 自分は、普段結構眠れずに夜更かしをしてしまう*2ので夜みんな寝る時に全然眠気こなかったらどうしよう...とか思ってたんですが、毎日宿に着いたらほぼすぐ寝られました。

各日のコンテストのチーム分けは、組みたい人がいればその人と組んで、あとは(バランスを取ると言う意味で)レートが高い人が低い人の名札を2枚引いてチームを組むという感じで決められました。

Day 1

コンテスト

立命館セット(3時間)でした (コンテストページ)

チームはACPC_shake_daaaaaというチームでshakeさんとtsukasa_diaryさんと一緒に参加しました。「シャケだー」は「日常」ネタらしいです(「日常」を断片的にしか知らず)

tsukasa_diaryさんはこの合宿のコンテストではコーディングしない縛りをするとのことだったので、shakeさんと自分がコーダーになるという形になりました。 とりあえずshakeさんにA、自分はB、tsukasa_diaryさんはC以降という感じで読み始める。Aをshakeさんが書いている間に、Bも方針が立ったので、Aが終わったらそれをshakeさんに伝えながら書いてもらう。で、ちょっとバグらせたりなんだりしている間にtsukasa_diaryさんからCとDの解法が降ってきたので自分が実装マンになる。後はEとかFとかを考えている間にうーんとなって終了してしまった。フローやっぱりまだ練習が足りない...という反省。ABCDの4完でした。

解説の時、最終問のヤバさがヤバすぎて度々謎の笑いが発生していた。

懇親会

駅前の中華料理屋で懇親会が行われました。会津の人とか立命館の人とかと交流をした(雑すぎる)

後はACPCの顧問的なポジションの先生が隣だったので色々お話をした。「早稲田、最近ICPC参加チーム増えてますよね、早稲田でもコンテストやらないんですか？」みたいなことを言われた。一応やんわりと企画してはいますが、運営者側が現状4人で、今回の3日間(立命館・会津・北海道大学)の作問チームのお話とかを聴く限り、やっぱり4人で準備するの無謀でしょ...みたいな気持ちになったので、今すごくどうしようか頭を抱えています...

この日は朝早かったのもあって、即寝した。

Day 2

コンテスト

会津セット(5時間)でした(コンテストページ)

チームはACPC_fitというチームでfuu32さんとtuki_remonさんと一緒に参加しました。

A,B,C(自分)とそれぞれ読み始めてAもBもいけそうと言う感じなので順番に書いてもらう。が、Bはサンプルが合わなくて自分もCを通した後で一緒にバグを探すことに。連休との距離が年をまたいでるときにおかしいことに気づいて、直してもらった。次に、Dはfuu32さんと一緒に考えて自分が方針を立てたので、どっちが実装しようかってなったけど色々ややこしいので自分がやることに。

その後、EとかFを読むけど全然方針が立たずに「？？」となる。Gも読んでみたけど実装大変だし、最後のDPが早くする方針が立たないからとりあえず置いておく。この辺で、他の問題を読んでもらっていたチームメイトからIは二部マッチングで、Lはセグ木でいけそうな気がするというコメントが来たので、自分がフローの写経をしたり、セグ木の写経をする。

最後1時間で、なんとかEとF(小さい方で実験したら何となく分かった)を通した。ABCDEFILの8完でした。そのうちのAB以外の6問を自分が実装していたので、もう少しチームメイトに実装を任せるということをした方がよかったのかな...という反省感があります。この辺をどうするべきかが悩ましくて、普段自分のチームだと方針が立った時に(幾何以外は)自分に実装が降ってくることが多いのですが、その辺の振り方が難しい。

懇親会

この日は、この合宿のスポンサーであるRCOさんのおかげで参加費無料の懇親会が開催されました。(ありがとうございます(｡>﹏<｡))

だいたい半分くらいでお酒飲む席と飲まない席に分かれたんですが、自分は飲む側の席にいて、大いに盛り上がりました(内容は書きません*3 )

この日も早稲田でコンテストやらないんですか？みたいな話になって、4人だけは現状で集まってるっていう話をしたら、どっかの大学とコラボしてもいいんじゃないですか、と言われてじゃあどことかなあ...って言ったら「慶応でしょ」みたいな話になって面白かった。確かに、そういう案もあるなあって思った。ただ、慶応のICPC参加者を全然知らないので自分からはコンタクトできない...また、もし他にも人が足りないみたいなところあればぜひ声を掛けて下さい...

この日の夜はこどふぉ(div2)があったので、かるく酔っていたけどunratedなので宿で参加したりして過ごした。

Day 3

コンテスト

北海道セット(3時間)でした(コンテストページ)

チームはACPC_Anzio_High*4というチームでrikaさんとYang33さんと一緒に参加しました。A,B,Cとそれぞれ読み始めて、Aはすぐ行けそうなのでやってもらう。Cはすぐには方針が立たなかったので、AをYang33さんに通してもらった後、一緒に読んでもらう。

Bがとても辛そうなので、一緒に考察する。rikaさんが、領域内の格子点の数みたいな考察をしていて、この個数を高速に数えたいなあと思うと、公差の方の軸で切ってみるとその直線上に並ぶ格子点の個数が等差数列になってそうな感じが見えたので、結局この等差数列が初項、公差、項数は何なのかをrikaさんに計算してもらう。

Cが通る頃にBの計算が終わっていて、とりあえずこの考察が合ってそうかどうかを確かめるために自分がpythonで等差数列の和を求める関数を書いてチェックする。合ってそうなので、実装を任せようかと思ったのだが、この等差数列の和を求める関数が実質答えになるので、そのままメイン関数も書いて自分が提出する。modとかオーバーフローとかに苦心する必要がなく、python最高という気持ちになる。

Eは問題を読んだYang33さんから「2次元BITを使いそう」という話を聞いて、自分も読んでみたらいけるとなったのでYang33さんに書いてもらう。自分は2次元BIT持ってなけど、Yang33さんは持ってて、すぐに写経が終わったので、そこからのクエリ処理とかをペアプロする。

残り1時間でFとGが残っていて、Fは「足し算だったらよくありそうな問題だなあ」って言ってた(logとれば足し算になるという発想は無かった...)。Gは、とりあえず普通に行列累乗するDPは方針が立って、制約怖いけど投げたらやっぱりTLEする。そこから、「行列累乗 高速化」とかでググり始める。すると、Yang33さんが巡回行列の積を高速に計算する方法を見つけて、自分の行列累乗の行列も巡回行列になっていて「おおー！」ってなってそこから30分で頑張って通した。

まとめ

初めて合宿系のイベントに参加したんですが、とても楽しめました。毎日いろんな人とチーム組んでやるのが良く、若干チームを組まなかった人とは交流が少なめになってしまったのは残念ですが、やっぱりチーム戦は楽しいですね。

あとは弊学でもコンテスト開きたいですね...今年ICPCに10チームも参加していたので、どこかに人はいると思うんですが(観測はできていない)、会津とか立命館とかの様子を見ていて、競プロに興味がある人が集まっているのがいいなあと思ったので、うちも集まったらいいんじゃないかなと思います。なので、興味がある人は最近できたPDCとかにコンタクトしてみたら良いと思います。

会津、とても充実していたので、来年もまた参加したいです。春の立命館合宿も行ってみたいですね。

会津大学の皆さんありがとうございました！

*1:自分の通っているところは「工場」と言われています

*2:ひどい時は、布団に入って横になったまま眠れず朝を迎えたりすることもある

*3:書けません

*4:Highschoolまで入れようとしたらオーバーした

GCJ 2017 R1A B - Ratatouille

GCJ programming

問題

Dashboard - Round 1A 2017 - Google Code Jam

問題概要

究極のラタテュイユのレシピが完成した。レシピにはどの原料をどれほど使うべきか、が記されている。ラタテュイユにはn種類の原料が必要であり、1人前を作るのにi番目の原料がR_iグラム必要である。

その原料をセットとして揃えて売るために、原料パッケージをいくつか注文することにした。原料パッケージには、ある特定の原料が一定量だけ入っている。各原料ごとにp個のパッケージがあり、i番目の原料のj個目のパッケージにはQ_{ij}グラムの原料が入っている。

これらのパッケージを使って、ラタテュイユキットをなるべく多く作りたい。ラタテュイユキットは、ラタテュイユに必要な各原料のパッケージ1つずつを組み合わせて構成される。

原料の比が厳密なもののみを作ろうとするとあんまりセットが作れないので、実際にそのセットで作ることができるとラベルに書いてある量に対して、原料は90%~110%の間に収まっていれば良いということにした。

例：ラタテュイユ1人前に500gのトマトと300gの玉ねぎが必要な場合

原料パッケージとして、900gのトマトと660gの玉ねぎを持っているとする。
これらのパッケージを使って、2人前のキットを作ることが出来る。
2人前には1000gのトマトと600gの玉ねぎが必要だが、
  トマトの量は1000gの90%~110%
  玉ねぎの量は600gの90%~110%
に収まっていれば良いので、可能である。

また、x人前のキットを作ると考えるときに、xは必ず整数でなければならない。更に、何人前のキットを作ろうと、それは1個のキットと見なす。この時に、作れるキットの個数を最大化せよ。

  • 1 \le n \le 50
  • 1 \le p \le 50
  • n * p \le 1000
  • 1 \le r_i \le 10^6
  • 1 \le q_{ij} \le 10^6

アイデア

パッケージのグラム数は本質的に重要な情報ではなく、重要なことは各パッケージは何人前に割り当てることが出来るのかということである。

例えば、1人前には10gのトマトが必要な時に、201gのトマトのパッケージは19~22人前のキットに入れることが出来る。このように、各パッケージを区間として考えることにしよう。

では、この区間を計算することを考える。パッケージの量をQ、その原料の1人前の量をRとすると、m人前のキットに入れることが出来る時、 0.9 * R * m \le Q \le 1.1 * R * mを満たし、mについて変形すれば \frac{10 * Q}{11 * R} \le m \le \frac{10 * Q}{9 * R}と計算でき、O(1)で計算できる。

さて、この区間を各原料ごとに昇順でソートしておき、各原料について何番目を見ているかを保存しながら、小さい方から貪欲にi人前のセットが作れるかをイテレーションしていくと良い。

任意の区間に対してだとこれが上手く行かない場合があるような感じがするが、今回のような区間の作り方だと上手くいく。なぜなら、今回の区間の作り方に従うと以下のことが成り立つ：

同じ原料の2つの区間l_1とl_2を考える。l_1がl_2に含まれる時、2つの区間は少なくとも1つの区間の端点を共有している(Property 0)。

→ 各区間が実際にS_iグラムから得られたものだったとすると、S_1 \le S_2のとき、l_1の下限はl_2より大きいことはない(つまりl_2と下限が一致)。逆に、S_1 \gt S_2のとき、l_1の上限はl_2より小さいことはない(つまりl_2と上限が一致)。よって少なくとも一方は端点が一致することが分かる。

上の貪欲が正しいことを証明する前に、他にも良い性質があるのでそれを確認しておこう。

  • Property 1: ある区間を捨てる(どのキットにも入れない)ことにする時と言うのはもうその区間のあらゆるx人前のキットが作れないことを意味する。

  • Property 2: ある区間を採用する(あるキットに入れる)ことにする時に、区間の共通部分のうち最小値がMだとすると、M未満のx人前のキットはもう作れない。

確かに、上の貪欲に従っていくなら、2つとも当たり前のことだという感じがする。それでは証明に入る。

上の貪欲によって、M_1 , M_2, \ldots , M_k人前のキットが作成されていったとする。ここで、N_1 , N_2, \ldots , N_k, N_{k+1}人前のキットの作り方のうち最小のものがあるとする。

Case A

iをN_i \lt M_iを満たす最小の値とする。Property 2によって、このようなことが発生するのはN_i人前のキットがもう作れない場合に発生する。これは、考えた貪欲がそのような区間を捨てているか、以前に使用してしまった可能性が考えられるが、前者はProperty 1によって有り得ない。また、貪欲の選び方とProperty 0によって後者も起こり得ない。ある区間rが選ばれる時、その原料パッケージに対してまだ残っている区間はrよりも上限は小さいことはない。よってその時点で選ぶのはrがベターであることが分かる。

Case B

Aのようなiが無いとする。つまり、N_{k+1}のキットが作成できなかったことになるが、Property 0,1によりこれは有り得ないことが同様に言える。

以上より上の貪欲は最適なことが分かる。

実装(C++)

続きを読む