IOI 2012

Algorithm IOI

かきかけです

9/22 直前合宿

  • バスに乗って空港へ出発
  • 結局集合の 1 時間くらい前に着く。1 時間後のバスでよかった気がする
  • 合宿では、いくつかの問題の解説があった
  • りんごさんによる Sails の解説がぱなかった

9/23 Arrival Day 成田→フランクフルト→ミラノ→会場

9/24 開会式

  • 停電、▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂

9/25 Contest Day 1

  • バスで会場に向かう
  • 会場遠い
  • 着いたらもう取材の人がいていろいろ聞かれる
  • コンテスト例によって開始 30 分くらい遅れた
  • コンテスト開始。
  • IOI だと紙の問題がないとやりにくいので最初に全部印刷を投げる
  • 問題をみて、Scrivener が一番簡単そうだったので考える
  • Undo を Undo する意味不明な行為の解釈に困ったが、結局「n 個前の状態に戻る」だけだとわかり、木構造を考えればよさそうだとわかった
  • 木構造の下から m 文字目は Doubling を使えばすぐに求められるので、書いて送って通る
  • そのあと、Odometer と Rings の間をうろうろする。Odometer 40 点は書くだけだったので書いて通る
  • その後がよく分からないので Rings の自明な部分点を書いて、55 点
  • Rings 満点とかよくわからなかったので Odometer で点数を拾いに行く
  • 95 点とれたところで、Rings の（模範解答とは違う、実装がえらく面倒な）解法を思いついたので書くが、全く通らない
  • 残り 10 分のところであきらめて Odometer を 1 点改善する

9/26 Gardaland

  • Gardaland こわい＞＜
  • 調べたら恐ろしい装置とよくわからない装置しかなかった

9/27 Contest Day 2

9/28 Venezia

9/29 Sirmione 観光、閉会式

  • 雨が降っている。NAE
  • バスで Sirmione 中心部に向かう
  • みかんさん湖に落ちました
  • 普通に湖に入って鳥に触ろうと試みていてぱなかった
  • Tour of Sirmione なので難しい英語による解説があって大変だった
  • 閉会式会場に向かう
  • バスの中で、メダルの色によって席が違うようなことを言われてやばい
  • しかもメダルなしの人がどこにいけばいいか示されていなかった
  • 実はメダリストとそれ以外（Leader, Visitor 含む）でバスが分かれていたらしい

9/30 Departure Day 会場→ミラノ→ミュンヘン→

  • 朝、9:00 出発のバスでミラノ（マルペンサ空港）へ向かう
  • 9:00 に出発すると言ってたけど普通に 10 分くらい遅れた
  • バスの中では寝たり看板の表示を解読しようとしたりしていた
  • 空港ではめしを食べたりお土産のお菓子を買ったりした
  • 結局ミュンヘンには 15 分程度の遅れで着いた、でも乗り継ぎ 75 分…
  • でも手荷物検査ももはやなかったし出国（出 EU）審査もすごい簡単だったしゲートがすぐだったので 60 分でも容易だった
  • 成田行きは「手違いにより必要な薬を荷物室に入れてしまった」らしく 30 分程度遅れた

10/1 成田→文科省→家

TopCoder SRM552

Algorithm TopCoder

ひさしぶりに SRM した

250

一瞬「えっ＞＜」ってなるもちょっと書きだしてみたら（根拠もなしに）N≡0,2 mod 3 のときは全色同じずつ、N≡1 のときは 1 色だけ多くなるだろーって思って二分探索した

500

長方形 2 個選ぶ典型問題。
長方形 O(N^4) 通り全部調べて、「L と P の差」「右端/左端」ごとに可能な最大の面積を記録しておく。その後、右端/左端を拡張する（例えば右端だったら、より右の場所で区切ってもその長方形は使える）。そして、すべての区切り場所ごとに、左と右の差を全部試してくっつける。最後が O(N^5)。スライド最小値使うと O(N^4) でいけるらしいがそんな面倒なことしなくても通る

900

わかんね

結果

Challenge Phase 怖いので無視
oox 609.58 9位

Rating: 2401 -> 2513

IMO2012

Math IMO

（この記事は書きかけです）

銀（Plata）でした。

7/7 成田→（オクラホマシティ）→ダラス/フォートワース→

  • 横浜で、関東の JPN 2 人と合流
  • NEX に乗り、品川で JPN 全員が集まる
  • 空港に着いて、直前学習会のあと出発。JPN らは席が近くだった
  • DFW で乗り継ぎが 3 時間なのであまり遅れてほしくなかったが、少し遅れて成田を出発。満席だった
  • 機内では A's とか StrikerS とかを見て過ごす
  • 到着間際になって DFW への到着時間が急に増えたと思ったら、到着地マークが DFW からなぜかオクラホマシティに変更になった
  • DFW が（悪天候で）閉鎖されたとか言ってて、燃料もやばいのでオクラホマシティに着陸したらしい
  • 結局 DFW に 3 時間遅れて到着。本来ならもうブエノスアイレス行きに乗れない時間なのでやばくて、実際最初はもう無理と言われた
  • しかしブエノスアイレス行きもひどく遅れていたので間に合った
  • 乗り継ぎやばい人は他にもたくさんいたようで、アメリカン航空の窓口にすごいたくさん人が並んでいた

7/8 →ブエノスアイレス→マル・デル・プラタ

  • Arrival Day
  • ブエノスアイレスに 4 時間くらい遅れて到着
  • 寒い
  • 両替しようとするが、市内のほうがレートがいいと言われたのでまずバスに乗って移動
  • カミニートというところに着く。両替してもらう。闇レートで 5.2[ペソ/米ドル]。米ドルが不足しているらしい（つまり、逆の両替ができない）。公定レートは 4.5[ペソ/米ドル]らしい。このレートから、16[円/ペソ] という概算をした
  • カミニートは恐ろしいところで、歩いていると日本語で意味不明なことを言ってきたりして怖い。それに対して日本語で返すとやばいらしい
  • 通りが恐くて歩けないので港を見たりしていた
  • 昼食は市内のレストラン。肉料理が多い。パスタ食べたかったが注文が難しいのであきらめた。どうやら適当にパスタの種類とソースを指定すれば食べられたらしい
  • その後バスでいろいろ観光し、国内線空港(アエロパルケ)に着く
  • 荷物を預け、ゲートへ向かう。荷物検査がかなりいい加減な気がした
  • 空港の自販機で水を買う。500[mL] の水が 10[ペソ]。20[ペソ/L]。日本円に直すと 320[円/L]。高い
  • 空港ではネットに繋がらなくて NAE
  • 時間になったので飛行機に乗る。タラップがなくて飛行機の前までバスで移動するようになってた
  • すごい眠かったので寝た。いつのまにか離陸し、いつのまにか着陸していた。その間に飲み物などが配られたらしいが寝てたので知らない
  • IMO のバスで、ホテルに到着
  • 夜遅かったのでまず食事をした。肉が多い
  • その後、SUM ROOM (以後、合計室と呼ばれたりする)という名前だけではよくわからない部屋に行ってみる。言わば去年のゲームコーナー。ただ広く、ゲームもたくさんある気がする
  • アルゼンチンでは水道水が飲めるというアナウンスはなかった(オランダではあって、そのため水がほとんど配られなかった)
  • のに、水が配られなくてやばい。水不足の予感
  • ちなみに、最終的に IMO 期間中に配られた水は、試験日に計算用水として各日 1 本ずつ水が配られただけであった

7/9 開会式

  • 開会式会場までは各国選手がまとまって移動。途中信号機や道路があるが IMO は車より強いので構わず進める
  • 開会式会場まで JPN らは「Japanese SAMURAI」の帽子をかぶって移動した
  • 途中、多くの人(含む現地の人)に写真を撮られる
  • 帰りはまとまって移動しないので IMO は車より弱い
  • 昼食の後、水不足なので近所のコンビニ？に水を買いに行く
  • JPN らは、1 人 2〜3 本 1.5[L] の水を買った。1 本 9[ペソ]。6 [ペソ/L] でとても安い。アエロパルケでは 20[ペソ/L] だった。3 倍以上安い。

7/10 Day 1

  • 試験会場はホテルの中で大変近い
  • ただ、ホテルの大部屋とはいえ選手が全員入るためそんなに広くはなかった（隣との距離が短い）
  • ゆえに、近くの席でオレンジを食べる、指を鳴らすなどやられると大変に不快になる

試験について。

  • 問題用紙見た瞬間、2 が不等式でゲーッとなる
  • 1 はどうせ 1 だし解けるだろうと思ったらかなり手こずって、初等幾何の解法が分からず、複素座標を使って無理やり垂直を示して後は自明な幾何をした
  • 2 わからないので展開したものに相加相乗の不等式使って解こうとしたが n=3 の場合以外に使えず NAE
  • 3-1 はもう少し条件がゆるければ簡単なのでそれだけ解いた
  • 試験が終わって、他の人の結果を聞く
  • 1 は全員解けていた。

7/11 Day 2

  • 昨日とほとんど同じ
  • トイレ言っていいですかと聞いたら restroom を restaurant に聞き間違えられた

試験について。

  • 4 はどうせ 4 だし解けるだろうと思ったらけっこう面倒だった。
  • 5 は最初計算すればどうとでも解けるんじゃねとなって、ちょっと計算を試みたところ、直交座標でこんなやばい計算なんてしたことないので挫折する
  • 複素座標でも計算できそうにないのでやめる
  • 線分と円の交点とか言っててもう片方の交点見えないの気持ち悪いなーと思って円書いて交点書いていろいろしてたらいつのまにか解けてた
  • そのときはびっくりして思わず計算用紙に「magical girl」と書いてた
  • 6 は、n が小さい場合を実験して、必要条件(n≡1,2 mod 4) を発見し、示す
  • n=1,2 のときは自明に構成できるが、n=5,6 のときできなかったので n=1,2 以外できないことを示しそうになる
  • n=5,6 の解を発見し、さっきの必要条件が十分条件に見えてくる
  • n≡1, 2, 6 mod 4 のときはより小さいものから構成できたので書いた
  • 試験が終わって、他の人々（day2 が終わったので団長団も来ていた）に合流。
  • hos さんに、4 は解が本質的に 3 つあるという衝撃的な事実を知らされて NAE
  • 5 は模範解とほとんど同じだったらしく安心
  • 6 は部分的な結果がいくつか得られたので点ほしいと主張した

7/12 Recreation 1

  • 近くのスーパーなどに行った
  • どうやって出るんだろうと思わせる SALIDA が街中にあった
  • 戻ってきた後は、SUM ROOM に行く。
  • 人々がサッカーをしていた。サッカーのような難しいゲームはわからないので応援していた
  • 夜、点数開示が始まる。各人 1 問の点数が隠され、各問については各国高々 1 問が隠されるように点数が隠されて公開される。2 だけ公開されたが、隠されていた
  • この隠し方は random なのか arbitrary なのかわからない

7/13 Recreation 2

  • Aquarium に行った
  • 日本の水族館（行ったこと無いけど）を想起すると室内に水槽があっていろいろな魚を見るものだと思ったが、この Aquarium において室内にあるのはフードコートと土産物屋くらいなもので外は当然寒かった
  • ビデオ上映があったがすべてスペイン語。わからん
  • イルカショーが多くの部分においてトークショー（もちろんスペイン語）だった。Olympiada とか Hola とか Gracias ぐらいしかわからん
  • salida (スペイン語で「出口」の意) を連呼していた
  • バスがホテルの前に着いてもドアが開かず気分悪くなって挙句の果てに 2 回再発進してやばかった
  • 路上駐車は n つの大罪の 1 つに含まれるべき
  • 夕飯の後 SUM ROOM に行ってみたら点数が出てた。一番怖い 4 だけまだコーディネーションされてないので出てない
  • 6 が思ったより取れていた。わーい

7/14 Recreation 3

  • 午前中は人々がサッカーするのを見ていた
  • 午後は、近所の HAVANA の店に行ったり、海に行ったりした
  • 犬がやたら追いかけてきて怖かった
  • その後 SUM ROOM に行くと、Mathematical Odyssey というものがあることを知る。かなり大人数のチームが必要だったりそもそも内容がよくわからなかったりで最初は無視する予定だった
  • ―が、他の国の人に誘われて 4 人だけ出ることに（じゃんけんで決めたら高 3 の 4 人が出ることになった）
  • 全然 Mathematical じゃなかった
  • Athletic Odyssey と言ったほうが正しい
  • 夜、体調があまりよくないので早く部屋に戻ってきて寝る

7/15 閉会式

  • 午前中に、閉会式もやってないのに公式ページに結果（点数、メダル）が公表される
  • Mar del Plata（スペイン語で「銀の海」の意）
  • 閉会式は、席に整数が書いてあり、自分の点数の書いてある所に座るというかなりやばい席順だった
  • 閉会式の最後に、来年の開催地コロンビアについてのビデオが流れた。「（コロンビアについて）唯一問題なのは、帰りたくなくなるということです」と書いてあった。
  • この日の夜は、32:00 まで SUM ROOM が開いているらしい
  • 夜は farewell party。始まるのが遅くて腹減った
  • 普段のバイキング形式じゃなくてコース形式だった。
  • ので、終わった時にはかなり遅くになっていた
  • それから SUM ROOM に行ったが、閉まっていた
  • 開いてから、SUM ROOM でお土産交換などをした
  • ほとんどお土産を消費して、眠いので部屋に戻って寝る
  • 32:00 まで SUM ROOM が開いているので朝行ってみようかともなったが、眠いのでやめた

7/16 マル・デル・プラタ→ブエノスアイレス→

  • Departure Day
  • 朝食を食べたら、もうバスが着いてるとか言われた
  • 荷物を準備して、バスに乗る
  • ブエノスアイレスまではバスで 5, 6 時間かかった（行き飛行機でいったレベルの距離なので 5, 6 時間で済んだといっても正しい）。道路に意図的な段差が存在してかなり揺れる
  • エセイサ空港はかなり混んでて、本質的ではない理由で飛行機が遅れそうだった
  • マイアミに向かう集団があり、なぜか JPN が絡まれる。ダラス行きに乗るのではないか不安だったがマイアミ行きで安心した
  • 荷物を預けるときに変な質問（どこで荷物を詰めたかとか）をされた
  • 18 歳以下だと容易に出国できないという噂を聞いていたが、全く気にされず普通に通過できた
  • 手荷物検査がいい加減で、水を持ち込んでも無視されるらしいことがわかった（フラグ）
  • 水が高い。500mL の水が 17 ペソもする。34[ペソ/L]。アエロパルケ 20[ペソ/L] よりも高い。市内だと 6[ペソ/L]。でもアルゼンチンペソはアルゼンチン国外ではほとんど使えず、使い切る必要があるのでたいした問題ではない
  • 両替所があったが、ドル→ペソ はできるのに逆はできないらしい。国際線出発ロビーなのに。
  • 飛行機遅れて NAE
  • スペイン語のみでアナウンスすることが頻繁にあって、エセイサ国際空港の国際性を疑った
  • 搭乗のときになぜか荷物検査があり、液体を没収される。34 [ペソ/L] の水がたくさん残っていたのに没収される。NAE

7/17 →ダラス/フォートワース→

  • DFW に 1 時間遅れて到着。もともと 4 時間あるので余裕
  • 北半球暑い
  • 時間があったので Skylink に乗った。思いっきり揺れるし、それにも関わらずつかまるところが少ないアグレッシブな電車だった
  • ゲートで待っていたら呼び出し食らったのでなにかと思ったら席変更されたらしい
  • 案内が日本語という安心感。英語アナウンス聞く気がなくなる
  • 成田行き 90 分くらい遅れた。表敬訪問するかどうか不明になる
  • 機内は空いていて、JPN らは 1 人 2 席以上使えた。アメリカに向かう便は混み、逆は空くことが判明した

7/18 →成田、表敬訪問

  • 結局成田に 1 時間遅れて到着
  • 日本暑い。DFW より暑いかもしれない
  • 入国審査とか税関とか日本語で聞いてくるのですごい安心感
  • 疲れてたのでバスで帰りたかったが表敬訪問があった。NAE
  • スカイライナーは東京に向かうときは 160km/h から 130km/h に減速するので遅く感じる
  • 結局 5 時前とかに文科省着いたが表敬訪問やった
  • 帰り、目の前で急行が出ていって NAE だったが急行あっても荷物のために乗れなかったかもしれない

TopCoder SRM541

Algorithm TopCoder

writer やってました。

Div2 Easy(250) AkariDaisukiDiv2

f(X) = Waai + X + Akari + X + Daisuki なる string -> string の関数を考える時、S = f(X) なる (Waai, Akari, Daisuki, X) の組の数を求めよ。

問題名とかいろいろおかしいですが(ivan さんに「"Waai" "Akari" "Daisuki" って何？」って聞かれました)、2箇所の X の位置を決め打ちして比較するだけで解けます。

Div1 Easy(250) / Div2 Medium(500) AntsMeet

蟻がいて動いている。ぶつかったら消える。もはやぶつからなくなったときの蟻の数を求めよ。

最初は x, y の上限が10億で、それだとオーバーフローして悪質なので1億になりましたが、それだとこの問題セットでは難しすぎるので上限を 1000 として、0.5秒ごとに進めて試すだけで解けるようになりました。
しかし、1 秒ごとで試している人が非常に多く、想像以上の challenge ゲーになってしまいました。ちなみに、Example 2 を見ると 0.5 秒ごとで考えないといけないことがわかります。

Div1 Medium(550) AkariDaisukiDiv1

Div2Easy と同様に f(X) を定める。Waai, Akari, Daisuki は与えられる。f^k(S) = f(f(…f(S)…)) (fはk回) の中に、部分文字列として F は何回現れるか求めよ。

難しいとは思いませんでしたが、非常に tricky らしいので 550 になりました。
tricky なのでテストケースをかなり親切にしました。そうしたら正答率がけっこう高くなりました。Correct % は Easy のほうが低いです。これなら 500 でもよかったかもしれません。

まず操作をして S を F より長くします。すると、部分文字列を考えるべきパターンが Waai--S, S--Akari--S, S--Daisuki だけになります。これは、S の左/右 |F|-1 文字を覚えておくとやりやすいです。
これをやると漸化式のような形になります。 k が 1000万 もあるので、最後まで試すわけにはいきませんが 50 くらいからはもはや漸化式の定数部分が変化しなくなるので、そこから先は適当にやると解けます。

Div2 Hard(1000) NonXorLife

ライフゲームのようなことをする。1 秒ごとに、各マスについて、「そのマスおよび周囲4マスのうち、少なくとも1マスでも生きているなら次生きる」というルールで状態を変化させる。 K 秒後に生きているマスの数を求めよ。

K が 1500 しかないので、K^2 くらいのメモリを確保しても足ります。累積和のようなことをしたり、DP のようなことをしたりすると解けます。

Div1 Hard(1000) XorLife

Div2Hard とほとんど同じだが、ルールが「そのマスおよび周囲4マスのうち、奇数マスが生きているなら次生きて、さもなくば次死ぬ」に変わる。

問題名の通り、ルールは「排他的論理和」です。(これがネタバレだったという説もありますが、ルール見れば少なくとも操作が xor であることは自明なはずです) このルールにはよい性質があり、2 秒後の状態は「自マスと、そこから上下左右に 2 マス離れたマス」にのみ依存します。
これを使うと、2n 秒後の状態を求めたいときは、盤面を mod 2 で座標が一致するもの同士で分けてしまい、n 秒後の状態を求めることで対処できるようになります。
奇数秒の場合でも、1 秒進めてやると偶数になるので、同じことができます。
これをそのまま使うだけだと何もうれしくないですが、これをやると盤面がどんどん小さくなり、途中から高々 3*3 にしかならなくなるので、(盤面, 秒数) でメモ化すると解けます。(秒数も、log K 個くらいしか考えなくてよいです)
実装は難しくなく、この方針なら多分適当にやっても（例えば、map に vector を放り込むなどしても）通ります。

この問題を最初に出した時は、盤面が8*8で、「生存マスが M を超える最小の時間を求めよ」という問題でしたが、上の問題でも十分に難しいと言われたのでこっちになりました。結局 1 人しか通していないので、やっぱり十分難しかったようです。

JOI春合宿2012 Day4 「Copy and Paste」

Algorithm JOI

想定解法は「永続平衡二分木」を使うものですが、そんなもの一般人には書けません。そこで、一般人にも使える道具だけを使って点数を取りに行く試みをしました。

続きを読む