day0
夜行バスにて仙台を発つ. 直前まで呑気にyukicoderの準備をしていたらバスターミナルに着くのがぎりぎりで危うくUTPC0次round敗退となるところだった.
day1(コンテスト前)
夜行バスの新宿着はAM5:00. いくら東京と言えど, この時間にやることは無い. 仕方がないので新宿から会場の日比谷まで散歩することにした.
国立競技場や国会議事堂のそばを通り抜け, 会場の位置の把握をしたのち, 東京駅に7:00前に着いた.
流石に歩き疲れたので東京駅前の広場で朝ご飯を食べつつUTPCの過去問を振り返る. 過去に解けていない問題を何問か考えたが, 紙もPCもない状態で解ける代物ではなかった.
しばらくすると近くの丸善が空いたので散策. 今回の旅のどこかで『エレガントな問題解決』という本を入手するのがサブクエストとしてある. 丸善内を隅々まで探し回ったが, どうやらおいていなさそうだった. 探索中にいくつか欲しい本はあったが, それらは他の書店でも買えそう&今荷物を増やしたくないという理由でパス.
時間も大分いい具合になってきたので会場への道中にあったタンメン屋で腹ごしらえをして, 会場入り.
会場は MC Digital のオフィス. 内装等にどこまで触れて良いのか分からないのでざっくりと述べると, とてもIT系らしいオフィスという感じがしてとても良かった.
他の参加者と談笑したり即席チームを組んだりchatGPTにチーム名を決めてもらったりしていたらあっという間にコンテストの時間となった.
チームメンバーは kiyoshi0205, karinohito, siganai の3名. チーム名は「無限の風」である. チーム名の深い意味はGPT君に聞いてください.
day1(コンテスト)
問題が難易度ソートされていないとのことで私は真ん中から見始めることにした.
最序盤にしたことと言えば, Fを見る→分からないのでGに行く→分からないのでHに行く→分からないのでIに行く→分からないのでJに行く→分からないのでKに行く→困るというムーブのみである.
順位表に動きが出るまでとりあえず設定が面白そうな I を眺めることにした. 結果的にはIは唯一の0AC問題だったのでそういった意味では外れ運だったかもしれない. 愚直を書いて見て, oeisに目ぼしい情報はない, 規則性がありそうで分からないという結果を得たところで, EにパラパラとACがあった. Eは得意な構築系だったので意気揚々とそちらへ向かう.
E問題
まず 偶数の時はOK.
奇数,
偶数の時不可というのはわりかし簡単に分かる.
問題は共に奇数の時である.
この手の場合は特殊な場合から考えると良いので, の場合を調べる. これは魔法陣の拡張の弱体化?になっているので, 魔法陣の構築を調べると, いい感じの構築が見つかる. 残るは
の場合であるが,
の場合は
から
列ずつ伸ばすことで簡単に派生させられる.
しかし, への自然な拡張が見つからない.
困ってしまったので, からの派生を諦めて,
列ずつ伸ばすの方に着目することにした.
の時は明らかに不可なので,
が作れるかがカギとなる. いくつか試してみると, 汎用的な構築が見つかるのでこれにて解決.
J問題
その後また数問ふらふら見た後, 解かれがちだったJに腰を据える. 条件をぐっとにらむと, 進法のようなものを考えると綺麗にまとまりそうである. 碌に証明はしなかったが, 方針は合っていると直感が告げていたのでそのまま実装. 後で高速化しようと思っていた場所を直し忘れてペナったものの, AC.
B問題
次にBを見る. 何となく, ほとんどの場合で損失は0になりそうである. excelで色々試すうちに, 長方形の塊を作って境界をギザギザさせると良さそうと気付く.
長方形のサイズや外周に沿った部分のギザギザ感によって黒マスの個数を調整しやすいのがありがたい. 都合の良い長方形を探す部分をプログラミングに任せると, 2ケース+ の場合だけ弾かれる. 仕方が無いのでこれらのケースを人力で構築して例外処理をする. 人力パートは小さいケースのみなのでさくっと見つけて完了.
H問題
ここで, siganaiさんからH問題が冪級数列の漸化式となったがそこで詰まっているという話が飛んできた. 見ると確かに厄介そうな形をしていたが, 一応閉じた形までは持っていけそうであった. そこから私が式変形をして, siganaiさんが途中経過を実装して合っているか確認ということをしばらくして, 無事に閉じた形に持っていけた. 別方針で変形をしていたkiyoshi0205さんとも一致したので式自体は合っていそう. 後は本当にあっているかやTLがほほ笑むかを祈ると, 無事にACとなった.
その後はC問題と格闘していたが全く本質にかすれずに終了. チームとしては10完12位. 今年も難しかったが解きごたえのある問題ばかりで面白かった.
day1(コンテスト後)
解説や懇親をするが5時起き2万歩walking5時間contestで流石に疲労困憊. 部屋の後ろの方でまったりとしていた. 会終了後時はその場にいた人達と夕食を食べに行くことに. その日はARCがあった上, その日の内に帰宅する人たちもいたため, さっくりと食べようとなる. すぐ入れそうなところに入るとそこは男性7名がパパっと食事をするのには似つかない空間が存在した. しかしそんなことより帰宅時間やARCの方が大事な人々なので急いで食事(これ自体は美味しかったです.)を平らげて解散.
宿をとっていなかったので最寄りの快活クラブへと向かうも満席. 私はARCを完全に諦め, ふらふらと上野の方へ向かった.
もうどうせARCには間に合わないので開き直って夜の上野をうろうろした. 夜の東京はうっかりするとデリケートなゾーンに侵入してしまいそうになるが, 若めのカップルが徘徊しているあたりなら一人でほっつき歩いても大丈夫そうという事で上野公園を少し散歩した.
いい感じの時間になったので上野の快活クラブへ. こちらは無事に入室できたのでそのままウトウトして一日が終了した.
day2
夜間8時間パックに間に合うようにむくりと起床. 近くのパン屋でパンを買って西郷隆盛のお尻を見ながら朝食をとる.
今日は17:00にバスタ新宿に行くまでの予定を何も決めていなかったので, とりあえず神保町に歩いて向かう. 神保町は案外近く, 書店群が開く前の時間帯についてしまう. 仕方が無いので江戸城に向かう. 9時開園まで時間があったので近くのベンチでセミナーの準備を少々する. 9時になったので再度入り口に向かうも開く気配なし. 改めて看板を見ると何と月曜は開かないと書いてある.
すごすごと元のベンチに戻り数学の続きをして時間をつぶす.
1時間ほどで神保町にある三省堂の本店が開く時間になったのでそちらに戻る.
三省堂は現在改修中だかで仮店舗になっていた. これはこれでレアなのでラッキー. 仮店舗と言えど, 中はちゃんと多フロアあり, 十分楽しめた.
ここで目当てであった本を見つけ, ついでにこれまた気になっていた『アルゴリズムの乙女たち』を購入した.
その後は明倫館や書泉グランデをはじめとして何店舗か回りながら適当な本を購入. 流石に歩き疲れてしまったので, 時間には早いが新宿へ向かう事とした.
疲れていると言えどWalkaholicな私は当然のように徒歩を選択. 新宿駅まで1時間半位の散歩をした.
追加でいくつか新宿駅周辺を散策した後, バスタ新宿から帰路につく.
ところでこの日は風が強かった. あまりに風が強いと首都高はとまり, 首都高がとまると迂回路の交通量が増えて事故も起きる. さらに時間は夕刻. 一般道は家へ帰る車でいっぱいである. こうして過去一番低速な高速バスの旅が始まった. さらに不運は重なるもので, あるところから全てのPA/SAが大型車満車であった. これでは休憩もできない. しかしバスの規定上定期的な休息は義務付けられているらしく, 予定外のPA/SAに入っては満車で素通りを何回か繰り返した. こうしてついに仙台の一つ手前のPA/SAまで来てしまった. 規定がどうなっているのかは知らないが, どうしても休憩を取らないといけないようで, ついに満車の中トイレ休憩に向かう人だけ降ろしてその間バスはどうにかするという手段がとられた. なんやかんやの果てに仙台駅に到着したころには終電もなくなっており自宅まで1時間弱のwalkingが追加されたのであった.
