73回生 physics
去年12月10日にオンライン予選(インターネット上で行われる)があって、本選に行くにもまずそれを勝ち抜けないとなりません。僕は今年は部室で受験していました。予選を通過するためには、100点満点の問題を3完(3問の完答)+部分点がセオリーです。問1~3をいかに早く解いて部分点に回れるかが勝負となります。予選で僕がどんな感じで戦ったか問題も交えながら書いていきます。
JOI君は鉛筆をN本買うために近くの文房具店に行くことにした．文房具店では鉛筆が一定の本数ずつのセットで売られている．セット X はA本でB 円，セット Y はC本でD円である．JOI君はセットXかセットYの一方を選び，選んだセットをいくつか購入する．両方のセットを購入することはできない．N本以上の鉛筆を得るために必要な金額の最小値を求めよ．
XをN/A(小数点以下切り上げ)セット買う場合と、YをN/B(小数点以下切り上げ)セット買う場合の比較です、本番では直ぐに正解のプログラムを書くことが出来ました。
JOI君はおじさんの家で双六を見つけた．双六は直線状に並んだN+2個のマスからなり，1番目のマスはスタート，N+2番目のマスはゴールである．その他の各マスには0または1が書かれていて，各i (1 \leq i \leq N) について，i+1 番目のマスに書かれた数字はA_iである．
双六では，最初にスタートのマスにコマを置き，サイコロを振って，出た目の数だけコマを進めることを繰り返す．ただし，1の書かれたマスに止まった場合は，ゲームオーバーである．ゲームオーバーにならずにゴールのマスに止まるか，ゴールのマスを通り過ぎたら，ゲームクリアである．
JOI君は双六を遊ぶためのサイコロをおもちゃ屋さんに買いに行くことにした．おもちゃ屋さんにはN+1個のサイコロが売っている．j番目 (1 \leq j \leq N+1) のサイコロはj個の面を持ち，1,2,...,jが1つずつ書かれている．
JOI君はゲームクリアできるようなサイコロのうち，最も面の数が少ないサイコロを1個買うことにした．JOI君はどのサイコロを買えばよいだろうか．
これはサンプルの入出力を見ると考察しやすくて、例えば
入力例3
7 0 0 1 0 1 1 0
出力例3
3
1が付いたマスは飛ばさなければなりません。例えば"0 1 0"なら最初の0からその次の0まで移動するのに2以上の目が必要です。"0 1 1 1 1 1 0"なら最初の0からその次の0まで移動するのに6以上の目が必要です。ここで気づくと思いますが、実は「連続する1の数」+1以上の目が必要になります。つまり、連続する1の数の最大に1を加えて出力すれば正解となります。これは先ほど示した入力例でも成り立つことが確認できます。
続く問3のシミュレーションもすぐに解けて、後半3問に充分時間を残せました。
ここで大事なのは、「可能な限り部分点を取りに行く」事です。まず、問題を一通り見て、解けそうなものを解きます。ひとまず問5が一番自分に向いてるなと思ってそれから取りかかりました。
JOI王国には広大な森林がある．森林は長方形の形をしており，南北にHマス，東西にWマスのマス目状に分けられている．北からiマス目，西からjマス目(1 \leq i \leq H, 1 \leq j \leq W)の領域にはA_{i,j}本の木が生えている．ただし，北西の端の領域には木材加工工場があり，木が生えていない．すなわち，A_{1,1}=0 である．
木が生えていない領域には人が立ち入ることが出来る．また人は東西南北に隣接する領域に，その領域に木が生えていなければ，移動することができる．森林の外に出ることはできない．JOI君はJOI王国の公共事業として，木を伐採し，北西の端の領域と南東の端の領域を，相互に行き来可能にしたい．
木の伐採は以下のようにして行う．はじめ，JOI君は木材加工工場のある北西の端の領域にいる．JOI君は，現在いる領域と東西南北に隣接する木の生えていない領域に1分で移動することができる．また，東西南北に隣接する木の生えている領域から，1分で木を1本伐採することができる．ただし，木を1本伐採したら，そのたびに北西の端の領域にある木材加工工場まで伐採した木を運ばなければならない．木を運んでいる間も，JOI君の移動速度は変わらない．木を運んでいる間は，他の木を伐採することはできない．
条件を満たすように木を伐採するのにかかる時間の最小値を求めよ．ただし，伐採にかかる時間とは，最後に伐採した木を，木材加工工場に運ぶまでの時間とする．
この問題で注目するべきは、「時間の最小値」です。これを見ると「最短経路問題」を連想したいところ、その問題についての有効なひとつの解法としてダイクストラ法があります、奇遇にも去年の2lu3氏の部誌がそのダイクストラ法についてなので、一度目を通すと面白いと思います。まず、直ぐに思いつきそうな解法として各地点の最短到達時間でダイクストラするというのがありますが、これは木を切るというフェーズをほぼ無視しています。(ので誤り)
その解法で書いたソースを試しに提出したところ、28点(小課題2)のみが入りました(だいたい予想は出来ていましたが)
そこで、4問目が取れれば相当大きいのでどうすれば満点を得られるか少し考察したところ、どうやら「切る木の本数の最小」か「その点への時間の最小」のどちらかが更新されればダイクストラを続行すると言う風にすれば良さそうというような結論に至りました。そして実装したところ、100点を得ることに成功しました。
その後、問4と問6の愚直なシミュレーションをして更に16点を確保しました。
後日、本選ボーダーが334点と発表されました(なんでや!阪神関係ないやろ!)。僕は416点だったので比較的余裕を持って通過できました。
お待たせしました、ようやく本選の話です!
本選は、今年2月10~11日に筑波で行われました。交通費は大会側持ちなのでタダで筑波に行けちゃうわけですよ!(こぼれ話ですが、大阪駅から筑波に行くためには秋葉原を経由してJRからつくばエクスプレスに乗り換えることになるので、人の金でアキバにも行けます)
ところで二日間大会があるってどういうことって思われそうですが、何とJOIは宿泊付きです!この話は後でしますが、そのお宿とは…?乞うご期待です()
1日目の朝早くから電車乗って気が付いたらアキバにいました。アキバの雰囲気を味わっていました(ちなみに中の人は音ゲーマーだったりするのでゲーセンに行くなどした(ﾎﾞｿｯ))。ヨドバシカメラも梅田より巨大でビビりました。全体的には三宮と日本橋(大阪)を足して2で割ったような印象でした。
お昼に、ほかのJOIerと合流することになり、昼を一緒に食べるなどしました(JOIer同士でインターネットで界隈が成立していたりする)。(ここである程度互いを認知しないとコミュ障が発動することになる。)
昼ご飯を食べ終わったら、つくばエクスプレスに乗って筑波に向かいます。だいたい45分といったところ。
筑波に着くと、そこは思ったより田舎でした。そこから本戦の会場に向かいます。
その後、プラクティスが始まりました。
本選の競技形式を練習するものですが、結構ゆるゆるで、この間に参加者とコミュニケーションも取れたりします(本番では駄目ですよ?)。僕はささっと(とも行きませんでしたが^^;)終わらせて、ほかの参加者とコミュニケーションを試みていました。しかし、灘校生特有(?)のコミュ障が発動してしまい、なかなか思う通りにはいきませんね。世知辛いのじゃ〜
ただ、もともと界隈に混じれていた、ほかのイベントで数人面識があったのもあって、顔とハンネが一致していくのは感動の体験です。なんとかちょっとは溶け込めて、そのまま夕食会に。(僕にしてはコミュニケーション頑張った?)
次に始まったのは講演。ありがたいお話を聞くことになるのですが移動疲れでダウン。ごめんなさい…()
講演が終わると夕食会が始まります。立食形式で、旨い飯が供給されます。ここで始まるのが
自 己 紹 介
コ ミ ュ 障 キ ラ ー
初対面の人に自己紹介をするのがコミュ障にとって如何に難しいことか?そりゃ僕も青ざめましたよ、でもせっかくの機会、ここで自分を売り込まないでどうする?って必死こいて自分を売り込みました。
実はJOIerの間で名刺を配る文化があり、僕もこの日のために名刺を用意してそれも可能な限りばら撒きました。ちょっとは爪痕残せたかな?
飯はかなり美味しかったです。感動のクオリティ。(言ってしまうと、学校行事の10^9+7倍くらい美味しい)
いよいよお宿の時間です。
宿についた時、それはもうワクワクでいっぱいでした。ちなみに、到着後すぐに、AtCoderでコンテストが始まったので一部の方はそれに出るなどしていました。JOIの大会を知ったのが中2の春とかだったので宿泊は実に1年半以上越しの念願です。宿はどんな感じかなーという評判も界隈や先輩から流れてきていたりします。その多くが「独房」との大変誉高い評価だったので、僕も楽しみにしていました。
ホンマかいや、と思いつつ鍵を受け取り部屋に向かいます。部屋の鍵を開けてみました。すると、そこに飛び込んできたのは…金属製の机、棚、ベッド、古そうな暖房器具、そして何より部屋が狭いっ!「凄いな、ホンマに独房や」って気持ちになりました。(まぁ考察できる環境ではあるので競プロをしようと思えば出来るくらい)
風呂はよく覚えていないのですが、(確か)一般的な大浴場でした。冷蔵庫は共用、食べ物にマーカーで名前を書くシステム。(僕は名刺を挟んでいました。名刺の使い方の応用例(?)です。)ここでも参加者と交流を深められます。楽しい。
そしていろんな人と談笑しながら時間は過ぎていき、皆寝静まり始めました。僕はというと…寝られない!全然寝付けなかったのです。気分転換に部屋の外に出てみたのですが、隣にあるのは非常ドア。(ちなみに僕の部屋は廊下の端っこにあたる位置でした。)その非常ドアの文言がなかなかに怖くて、「このドアは外から開きません。門限は深夜0時です。」とのこと。その時0時を回っていたので、ドアの外に少し足を出すだけで臨死体験が出来ます。(しかもその時冬だったので寒い!)
そうして起きてる参加者とTwitterで交流したりどうぶつタワーバトルしながら時間を潰したりしていると、自然に(?)寝落ちに至りました。(この章宿泊施設かなり酷評してて怒られそう)
次の日の朝、無事に起床に成功した僕は宿で出される一般的な朝ご飯を食べ、バスで(昨日と同じ)本選の会場に向かうことになります。「いよいよなんだなぁ」って感じの気持ちになりながら、僕はバスに乗り込みました。
競技は4時間、静寂に包まれる中行われます。80台のPCと80人の競技者が並ぶのは壮観です。問題が入った茶封筒が配られ、「あぁ、いよいよなんだな」という気持ちにさせられます。
本選は、2完+部分点というのがセオリー、たいていの場合部分点勝負になります。
JOI君の部屋にはストーブがある．JOI君自身は寒さに強いのでひとりで部屋にいるときはストーブをつける必要はないが，来客があるときはストーブをつける必要がある．
この日，JOI君のもとにはN人の来客がある．i番目 (1 \leq i \leq N) の来客は時刻T_iに到着し，時刻T_i + 1に退出する．同時に複数人の来客があることはない．
JOI君は任意の時刻にストーブをつけたり消したりできる．ただし，ストーブをつける度にマッチを1本消費する．JOI君はマッチをK本しか持っていないので，K回までしかストーブをつけることができない．一日のはじめにストーブは消えている．
ストーブをつけているとその分だけ燃料を消費するので，ストーブをつけたり消したりする時刻をうまく定めて，ストーブがついている時間の合計を最小化したい．
まず、来客が来るごとにストーブをつけることを考え、そこからマッチを使うことを減らすために、つけっぱなしにする回数を増やしていきます。つけっぱなしにする位置は、時間が短いほうから貪欲法で選べます。これは割とすぐに解くことができました。
JOI国で美術展が行われることになった．美術展では，国中から集まった様々な美術品が展示される予定である．
展示される美術品の候補として，N点の美術品が集まった．これらの美術品には 1, 2, . . . , Nの番号が付けられている．それぞれの美術品には大きさと価値と呼ばれる値が定まっている．美術品i(1 \leq i \leq N) の大きさは A_i，価値はB_iである．
美術展では，これらの美術品のうちから1点以上を選んで展示する．美術展の会場は十分に広く，N点の美術品すべてを展示することも可能である．しかし，JOI国の人々の美的感覚のため，美術品の間で大きさの差があまり大きくならないように展示する美術品を選びたい．一方，できるだけ価値の大きい美術品を多く展示したい．そのため，次の条件を満たすように展示する美術品を選ぶことにした:
まず、大きさ順に品物を並べ替えることを考えます。ここで、選んだ最大の品物と選んだ最小の品物の中間の品物は、すべて選んだほうが良いことがわかります。すると、価値の累積和をとることによって任意の区間を選んだ時の最大化するべき値がO(1)で求まります。それから、選ぶ最大を1~N個目まで回して、その後それより前の区間のうち、外すと価値が最大化されるものを順次計算で求めて最終的な最大を求めます。(自分がした解法をはっきり思い出せず、解説を読み直しました())ここまでは割と速くいって、意外と行けるのでは?とか思いながら残りの3問に向かいました。
しかし残りの3問になかなか悪戦苦闘してしまい、問3と問5で愚直なシミュレーションで25点を何とか稼いで、問4で小課題狙いを実装してバグらせていたところ、時間切れになってしまいました…
昼ご飯はお弁当、まぁまぁ美味しかったです。その後、解説を聞きましたが解けなかった問題は難しすぎてあまり理解しきれませんでした。(いつか解きなおしたい)自分の暫定得点が225点、ボーダーは240前後だろうという話が出てバグらせたのを後悔し始めたのはこの時だったりします。
その後、参加者とお別れをして、大阪へ帰りました。
大阪に帰ってきたその日に、結果は分かりました。結果は…8点足らずで春合宿落ちでした…(僕が225点で春合宿が233点)問4の小課題をバグらせていなかったらと今でも後悔しています。僕の運不足、練習不足、そして何より実力不足です。ただ強豪ひしめく中で思ったより戦えてたというのはありました。正直落ちた直後はメンタルやられていたのですが、今は過去問埋めをする、蟻本を読むなどして来年はもっと強くなって帰ってきてやる、絶対に春合宿に行ってやるという気持ちまで戻すことが出来たので、精進を重ねたいと思います。
今回の本選、少し悔しい思いもしましたが、めちゃくちゃ楽しかったしいい経験にもなったので、来年も本選、できれば来年はその先の春合宿に行けるよう頑張りたいです。