ICPC 2024 アジア地区予選 台中大会 (2024/11/14-18)

ICPC 旅行

ICPC 2024 アジア地区予選 台中大会に、東京大学チーム Screenwalkers (E869120, square1001, KoD, 敬称略) のコーチとして参加しました。

アジア地区予選について

2024 年の ICPC Asia 地区予選については、Asia Pacific Championship (以下、プレーオフ) のサイトが詳しいです。ここでも簡単にまとめると、アジア地区予選には以下の 5 つの大会 (以下、リージョナル) があります。

各チームはこれらのうち 2 つ以下に参加することができ、各リージョナルの上位チームがプレーオフに進出することができます。プレーオフでは World Finals (以下、WF) に出場するチームが決まります。選抜基準についてはこちらが詳しいです。

海外リージョナル参加のメリット

注意されたいこととして、自国の予選を通過していなくても海外リージョナルに参加できるという点があります。日本でいうと、7 月の国内予選で落ちて横浜大会に出場できなかったとしても、台中・ソウル・ジャカルタ・ハノイ大会には参加することができ、そこで上位に入ればプレーオフや WF に進出できる可能性があります。

国内予選を通過して横浜大会に出場できるチームであっても、海外リージョナル参加によってプレーオフ進出の可能性を高めたり、リージョナルで優勝することで WF への進出を確定させる (ただし、同大学の異なるチームが異なるリージョナルで優勝した場合はそうとは限らない) ことができるなどのメリットがあります。

台中リージョナル参加までの手続き

今回の台中リージョナル参加にあたって、コーチとして行った手続きは以下の通りです。ただし、リージョナルや年によって異なるであろう点にご留意ください。

  • ICPC world site での参加登録
  • 参加登録締め切り後、メールで再度参加意志を問われたので、Yes と答える
  • コンテスタント・コーチの個人情報、参加費支払いのためのクレジットカード情報の送付

実は同じく東京大学のチーム SPJ も台中大会の参加登録を行っていたのですが、海外チームの 10 チーム制限に阻まれて参加できませんでした。枠を超える応募があった場合は申し込みが早いチームが優先されるルールを採用しているリージョナルが多そうなので、強い参加意志があるチームは締め切りギリギリではなく早めに登録を行うと良いと思います。リージョナルのホームページに選抜基準が書いてあることもあるので、隅までよく見ましょう。

渡航までの準備

10/07: 台中リージョナル参加日本勢の Discord に参加

参加チームが確定した直後に阪大チームコーチの kotamanegi さんが作ってくださった Discord サーバーに入りました。ここでは日本から台中大会に参加する会津大・東大・阪大・早稲田の参加者が集まって、飛行機や新幹線の割引、入国カードの事前作成、各々予約したホテルや飛行機の情報共有していました。日本から一緒に参加するチームが複数いたのは心強く、幸運でした。

10/10: 飛行機・ホテルの確定、ホテルの予約

コンテスタントの 3 人とミーティングをして、往復の飛行機とホテルを決め、ホテルは booking.com でその日のうちに予約しました。大会日程は 16(土、リハーサル)・17(日、本番)・18(月、観光) だったのですが、いいコンディションで臨むために早めに現地入りしたいことや、メンバーの授業の都合を鑑みて、最終日の観光は行かずに 14 日から 18 日で行くことになりました。

決定した飛行機・ホテル

ホテルは桃園が 1 泊 1 人約 10,000 円、台中が 3 泊 1 人約 13,000 円でした。台中のホテルは割と安いところが多かったです。

10/11: 飛行機の予約

中華航空の日本・台湾便を 4 人で使うと安くなるキャンペーンを利用しました。中華航空は LCC ではないのでキャンセルや荷物についても融通が利き、日本の ANA や JAL と比べるとかなり安いので、安心して使うことができました。割引の結果、往復 1 人約 48,000 円になりました。LCC でも 4 万円程度はかかると聞いたので、コスパはとても良かったと思います。

パスポート

既に作っていたので大丈夫でした。持ってない場合は作るのに約 1 週間かかるので、早めに申請すると良いと思います。

入国カードの作成

台湾に渡航するにあたってビザは必要ありませんが、入国カードは必要です。事前にウェブで作成してから行きましたが、機内や空港でも書けるのでそれほど問題にはならないです。

クレジットカードの枠一時引き上げ

4 人分の飛行機代の支払いにかなりかかったので、余裕を持って 50 万円に引き上げました。台湾はかなりカードが使える所が多く、全体の 8,9 割はカード払いだったと思います。海外で使うとすぐに制限がかかってしまうカードもあるようなので、事前に確認しておくと良いと思います。

荷造り

重い腰を上げて出発 2 日前くらいから始めました。とはいえ持って行ったのは服・日用品・充電器・パスポート・飛行機やホテルの予約確認書の印刷くらいです。事前に天気予報で台中は暑い (最高 30 度くらい) ことがわかっていたため夏服しか持って行かなかったので、4 泊 5 日でも余裕でスーツケースに収まりました。行く国のコンセントの形状や電圧は事前に調べておくと良いです (台湾ではそのまま使えました)。

両替

行きの成田空港で、E8 さんに 1 万円を台湾ドルに両替してもらいました。現金でしか払えなかったのは台中市街の飲食店や夜市だけだったので、4 人で 1 万円でちょうど使い切るくらいでした。市街ではどこで両替できるかよくわからないので、少しレートは悪いですが日本国内または行った先の空港で済ませておくと安心だと思います。

台風 25 号

大会 3 日前の 13 日に、台風 25 号の影響で大会がオンラインになる可能性があるという通達を受けました。要件としては、オンラインになった場合に備えてパソコンと、ビデオカメラやスマホでの録画環境を用意しろというものでした。録画はスマホでも大丈夫なようですが、容量が少し心配かもしれません。

結果的には台風は来なかったので杞憂に終わりました。

参加記

ここからは実際の参加記になります。

大会前々日 (11/14 木)

フライトの約 2 時間前の 17:30 に成田空港に集合することになっていましたが、余裕を持って 15 時前に家を出発して、京成線のアクセス特急で成田に向かいました。電車はスーツケースを持った旅行客で溢れかえっていましたが、羽田空港発成田空港行なので、誰が旅行帰りで誰がこれから旅行に行くのか見分けがつきません。幸運にも乗った次の駅で着席できて、成田空港には定刻通り 17 時前に到着しました。

改札の近くで KoD さんらしき人がいるのに気づきましたが、ここでは確証が持てなかったので話しかけられませんでした。結局第二ターミナルに着いたところで再度合流したので今度こそ話しかけ、無事に本人であるとわかりました。ターミナルにある店街を見たり、雨に備えてタオルを買ったりした後 E8 さん square さんとも合流します。

全員揃ったところでまず飛行機のチェックインを行いました。隣のホノルル行の便のカウンターは長蛇の列ができている一方でこちらは待ちがなく、スーツケースの受託と座席の確定をスムーズに行えました。時間がかなり余ったので、E8 さんに空港内の両替所で 1 万円を約 1,800 NTD に両替してもらい、展望デッキに繰り出した後レストラン街で軽く食事をしてから保安検査場に向かいました。

保安検査は通常のものですが、その後に国際線特有の出国審査があります。ここではパスポートをスキャンしてカメラに写った顔と照合する顔認証ゲートが整備されていてテクノロジーを感じました。私の場合は認証に結構時間がかかってしまったのですが。

搭乗ゲート

ここまで来れば搭乗までの関門は終わりです。ゲートで搭乗開始を待っていたのですが、第二ターミナルは LCC 専用の第三ターミナルと比べて広くて綺麗だなとこのときしみじみ思ったのを覚えています。使用する機体の到着が遅れた影響で、搭乗は予定より 20 分遅れの 19:30 に開始しました。機体は一昔前のエアバス A330 で、機内 Wi-Fi のサービスはありませんでしたが座席の柔らかさや広さについてはエコノミークラスとしては申し分ありませんでした。座席配置は 2-4-2 で、我々は 2-2 に別れて窓側の席に座っていましたが、機内では特に中央の 4 列の部分に空席が目立ちました。出発はやや遅れたもののフライトは順調そのもので、台北桃園空港にはほぼ定刻通りに到着します。搭乗時間は約 4 時間と長丁場で台湾が思ったより離れていることを実感しましたが、機内食があったりフライト情報をリアルタイムで確認できたりと十分に楽しむことができました。

着陸少し前から感じてはいたのですが、やはり台湾は暖かいです。しかし、それよりも成田を出てからというもの食事の際の崇拝の水しか飲んでいなかったことによる喉の渇きが気になりました。つつがなく入国審査を終えたあと手荷物受取所で給水所があったので急死に一生を得たので良かったですが、出発前に水をたくさん飲んでおくべきでした。

23 時半頃に全員が荷物を回収したところで、ようやく宿泊するノボテルに向かいます。空港直結の地下鉄駅から 1 駅先にあるのですが、地下鉄はクレジットカードでも通れる改札があって非常に便利でした。日付が変わるギリギリくらいの時間に着きましたが、この時間でもチェックインの行列ができていて驚きます。チェックイン時のカード支払いで、台湾ドルか日本円かどちらで支払うかを訊かれたときに手なりで日本円を選んでしまったため、ホテルの高い両替レートの影響で数千円をロストしてしまいましたが、これも高い授業料だと思うことにして観念しました。

ノボテルの部屋

部屋は広く綺麗で、今回はほぼ見るだけでしたが下の階にはジムやプールなども併設されており、1 万円という値段に対してはとても良い環境でした。もう遅かったので各々シャワーを浴び、適当にテレビで現地の番組を見たりしてから現地時刻 1 時半頃に就寝します。

1 日目感想まとめ
  • 無事に入国できて良かった
  • 地下鉄はクレジットカードが使えて便利だった
  • ノボテルがすごい

大会前日 (11/15 金)

2 日目は 8 時半頃に起床し、身支度を整えてからホテルの下の階で販売されていたパンを 1 つ買い、ホテルを後にします。チェックアウトの際に、チェックインの際の支払いで実は過剰な額を請求されていたことを謝罪され、払い戻しして改めて正しい額を今度は台湾ドルで支払うこととなりました。不意にミスがチャラになって僥倖です。

この日は台北を少し観光してからコンテスト会場のある台中に向かう予定でしたが、台風接近の影響で高速鉄道が午後計画運休となっていたため、早めに切り上げて台中入りすることになります。

桃園空港から台北の中心駅までは地下鉄の快速で約 20 分の距離で、地下鉄ながら地上を走る区間も長く、右を見れば山、左を見ればビル群という光景が面白かったです。向かう先は台北の高層タワーである台北 101 で、台北駅からさらにメトロ線に乗り継いでいきます。こちらの路線ではクレジットカードは使えず、用意してもらった現金を使ってコイン上の切符を買いました。タワーの麓には 11 時半頃に到着しますが、地下一階はおそらく観光客で溢れかえっていました。予約していた新幹線までさほど時間がなかったので、受付では 89 階までのファストパス (1,200 台湾ドル) と 101 階までの追加チケット (380 台湾ドル) を購入しましたが、1 台湾ドルが約 4.8 円であることを考えると割と高かったと思います。

101 階に行ける時間は 13 時から 14 時までだったので、先に地下のフードコートで食事を済ませます。私が行った店はメニューが中国語しかなく、値段を指し示す元が台湾ドルか中国の元のことなのか判別できませんでした (実際はちゃんと台湾ドルでした) が、辛うじて何かを注文できたので及第点です。各々食事を取り、12 時半頃に今度こそ 89 階へと行きます。高かったですが、ファストパスのおかげで 1 時間くらいの待ちを回避できたようです。

台北 101 89 階からの眺め

89 階では台北の市街を見下ろすことができてもちろん綺麗だったのですが、空気が汚くて淀んでいたのが少し残念だったというのが正直な感想です。その他では大谷翔平選手の 50-50 が至る所で崇め奉られていたのが印象的でした。

この球体一体どれくらい重いんだろうか...

中のお店でマンゴースムージーを買ったのですが、前に並んでいたおばさんが勝手に私の支払いに対してクーポンを適用してきたのには本当に驚きました。自分としては安くなったのでありがたいのですが、あまりに不測の事態に唖然としました。13 時になったので、階段で 91 階に上がり、93 階でエレベーターを乗り継いで 101 階へと行きました。

台北 101 101 階

101 階は全体が緑や草花で覆われており、昔は VIP 専用だったようです。台北 101 は高さ 508 m で、101 階の高さは約 460 m とスカイツリーの最高展望台よりも高いことや、日本では 4,000 m の塔や 10,000 m のマンションの建築計画がかつてあったことを E8 さんらから聞いて勉強になりました。

だいぶ道草を食って時間が切羽詰まったため、急いで降りて台北駅に戻ります。エレベーターで昇降時に E8 さんらがかかった時間を測っていたのが面白かったです (昇りの方が速かったらしいです)。午前中に指定席予約してもらった 14 時半前の高速鉄道で台中駅へと向かいます。16 時以降は台風で運休の予定となっていて、エコノミークラスで乗車できる便としては最も遅いものだったと記憶しています。

高速鉄道の台中駅からは改めて在来線の台中駅を目指します。台中駅が離れた位置に 2 種類あるのがややこしく、高速鉄道の台中駅に直結している在来線の駅は新烏日です。在来線台中駅までは約 10 分ですが、運賃は 15 NTD (約 70 円) であり日本と比べると圧倒的に安いです。その分本数は 20 分に一本程度なのですが。

ここから三連泊となるツインスターホテルにチェックインした後は小一時間休憩して食事を求めて市街へと繰り出します。

小籠包と海老餃子

食事は街の良さそうな中華料理店に行きました。予約で結構人が埋まっていたようでしたが、19 時までという制限の下で 4 人で入ることができました。支払いが現金のみで E8 さんの手持ちが約 1,700 NTD でしたが、各々 1 品と 4 人で小籠包・海老餃子をシェアする形で 1,485 NTD だったので、色々な意味で味が良かったです。

満月と台中駅

食後は真っ直ぐホテルへと帰りましたが、綺麗な満月が覗いていて台風とは...という気分になりました。コンテスト本番は明後日ですが、当日の早起きに体を慣らすためにこの日は早く寝ます。

2 日目感想まとめ
  • 来なかった台風に狂わされてあまり観光できなかった
  • でも無事に台中入りできたので、コンテスト第一の観点からは良かった

大会 1 日目 (11/16 土)

いよいよ大会 1 日目で、この日は午後からリハーサルがあります。ホテルの朝食を食べてから 9 時頃くらいにホテルを発ち、辺りを少し歩いて回ってからバス集合の高速鉄道台中駅を目指します。ここで散策中に阪大メンバーの二人と偶然会い、泊まっているホテルや昨日の新幹線の運行状況について軽く情報共有をしました。

高速鉄道台中駅にはシャトルバスの発車 1 時間前に着いたので、そこで昼食を済ませる予定だったのですが、レストラン街が一風堂・すき家・大戸屋などの日本チェーン店のオンパレードだったためやむなく一風堂で食べることになりました。日本の店舗との違いはそんなにわからなかったですが、値段は高かったです。

シャトルバス車内。中で食べてる人が多かったのでそうすればよかったかも

出発ギリギリに ICPC 運営のシャトルバスに乗り込んで、会場のある亜洲大学に向かいます。当たり前ですが車内は台湾選手ばかりで、アウェーを思わされました。

横浜にもこういうのほしい

大学には 12 時すぎに着いてチェックインと記念撮影をしたのは良かったですが、その後コンテスト会場が開くまで約 30 分ただ待機する時間があったのが退屈でした (特に、この日の午前 0 時発の便で来た早稲田勢は眠くて大変そうでした)。

コンテスト会場の体育館

横浜大会とは違って会場にはコーチの分の椅子はなく、体育館の後方 2 階席から眺める形でした。まるで授業参観を見に来た保護者みたいな感じです。開会式やルール説明が行われたあと、いよいよプラクティスコンテストが始まります。しかし用意されていた順位表はあいにく動いていなかったので、特にやることがなくて早稲田コーチの suzuken さんや阪大コーチの kotamanegi さんと駄弁ったり自転車マシンで遊んだりしていました。

プラクティスの内容は今年の台中国内予選の問題そのままだったようですが、我らが Screenwalkers が優勝していて流石でした (もっとも、台湾の上位チームはちゃんとは取り組んでいなかったようですが)。終了後は私も下に混じってコンテスタントと話をしましたが、E8 さん square さんが台湾チームからの人気を博していてその影響力の高さには驚きました。私もその流れに便乗して台湾選手とお話しさせてもらい、好きな日本人競技プログラマーを何人かに聞いた結果、上がったのは chokudai さん・双子・maspy さんでした。

最後に配布されたミールボックス (中身はパン) をもらって会場を後にしたのですが、どうやらシャトルバスは既に出発してしまったようです。早稲田勢・阪大勢は疲れて座り込んでいましたが、その際に聞いた「今年 3 月のベトナム・ハノイでのプレーオフでも寒空の下バスを待たされて、日本勢で地べたでカードゲームをした」という話が印象的でした。その他にもベトナムの交通事情はカオスで、歩いて 10 分のところをバスで 1 時間かかったり、歩道を歩いてたら後ろからバイクがクラクションを鳴らして来たこと、krps さんがホテルのスリッパのまま会場に行ったことなどが面白かったです。

待つこと約 30 分でバスが帰ってきてようやく乗り込みますが、2 人だけ定員オーバーになってコーチの私と kotamanegi さんだけ次のバスになりました。幸いこちらも 5 分後くらいに来たので特に問題なかった上に大型バスを 2 人で貸切することができて気持ちが良いものです。高速道路の上から見える台中市街の夜景も強く印象に残りました。

台中駅から見る市街

帰りの電車は 20 分遅れていたため、ホームで 30 分以上待つことになり、在来線台中駅に着く頃には 19 時半を回っていました。駅前のファストフード店で軽く食事を済ませては 20 時すぎにはホテルに戻り、明日のコンテストに備えて風呂に入ったらすぐ寝ます。

3 日目感想まとめ
  • 日本勢はもちろん台湾勢とも話すことができて楽しかった
  • E8 さんは台湾でも人気
  • プレーオフ@ベトナムの話が面白かった

大会 2 日目 (11/17 日)

ついに大会本番当日が来ました。余裕を持って朝 5 時台に起き、身支度を済ませて 6 時半に出発します。高速鉄道台中駅のカフェで朝食を取って、今回は余裕を持ってシャトルバスに乗車。会場に着いてからは選手の荷物預けを行い、この日はすぐにコンテスト会場に入ることができました。しかし問題になったのがトイレットペーパー切れで、1 フロアのトイレで 1 つのペーパーを共有していたため地獄絵図が広がっていたようです。私は近くのコンビニのトイレを借りることで事なきを得ました。

コンテストは定刻の 9 時半に無事に始まり、この日は順位表が動いていてコーチ用の問題文も配布されたので、万全の状態で観戦できました。序盤は LGM の i_am_noob さん擁する NTU チーム std_abs が若干上回る形で Screenwalkers と上位を争っていて、中盤あたりで Screenwalkers が二完差をつけたところで安心して suzuken さん kotamanegi さんと一緒に昼食に行きます。台風でオンラインになる可能性があったのが嘘かのような見事な晴天で天気も 30 度近くあり、台湾に来てから一番の暑さでした。地元の飲食店に行ったので注文がかなり大変でしたが、餃子麺はコスパもよく美味しかったです (お茶が大量に砂糖が入っていてめちゃくちゃ甘かったですが)。

食事 (80 NTD)

会場に戻ると std_abs が二問通して完数で追いついたところで順位表凍結されていて、優勝争いは混戦の様相を呈しています。早稲田の 2get もあと一問通せばプレーオフが見えてきそうです。kotamanegi さんは阪大はもうだめだと言っていました。凍結後提出を見て、これは通ってそうこれは通ってなさそうなど想像を巡らせているうちにコンテストが終了します。

今年は横浜風船ある...？

我々もコンテスタント側に行って、2get と Screenwalkers の結果を聞きました。どちらも凍結後の提出で AC できたようで、特に Screenwalkers は時間差を考えれば優勝が確定していると教えてくれました。最難の N 問題を解いたときに E8 さんが泣き崩れたそうですが、上からは大量の風船で遮られて見えませんでした。何はともあれ、おめでたい限りです。

快晴

朝預けた荷物を回収してから大講堂に場所を移します。こんな綺麗な講堂がうちの大学にも欲しいものです。閉会式が終わったあと、いよいよお待ちかねの Yes/No が始まります。まずは各問題の FA 賞が授与されたのですが、Screenwalkers は凍結前で 5 個もらっていてウケました。110 チームあるうえに上位 10, 30, 60 チームはそれぞれ金、銀、銅メダルを表彰されるので、結構時間がかかりました。日本勢は全て銀メダル以上で素晴らしいです。早稲田はプレーオフに行ける見込みが高そうだったのも嬉しい報せです。最後は Screenwalkers と std_abs の決戦です。std_abs は凍結後に 1 問通して 12 完としましたが、Screenwalkers は 2 問通して 13 完だったのでここで優勝が確定します (改めておめでとうございます！)。厚かましくも表彰ではコーチの私も写りに行ったのですが、どうやら壇の中央にいたようでだいぶ目立ってしまっていたようです。

Yes/No 最終盤

撮影の後は運営の方とお話しすることができました。WF でも頑張ってくださいということを言われましたが、実はまだ横浜の結果次第で WF に行けるかが変わるので、残念ながら苦笑せざるを得ませんでした。貰ったトロフィーと楯をしまってからビュッフェ会場へと向かいます。頭を使ったコンテスタントのことを考えてなのか安価だからなのかわかりませんが、炭水化物パーティーです。最後に早稲田・阪大と合わせて 3 チームで記念撮影をしました。

この日はちゃんと一巡目のシャトルバスに乗り込み、会津大を合わせた 4 チームで在来線台中駅の周りで観光に行きました。行った場所は第四信用合作社 (アイスクリーム屋) と夜市です。アイスクリームはダブルのサンデーで頼もうとしたところ、トリプルでも同じ値段だと言われてそうしたのですが、結構ボリューミーで最後は溶けてきて食べるのが大変でした。もちろんおしゃれなお店で美味しかったので満足です。

ワッフルを食べるのがむずい

後半は夜市へ向かいます。歩いている途中早稲田勢の krps さん k1suxu さん suzuken さんとお話しできました。お二人が昨年横浜に出たチーム hot-k-k1 での hotman さんのエピソードや麺屋こころでの例の事件と、krps さんのベトナムスリッパ事件を見比べて、krps さんが hotman さんに似てきているという話を聞いて、全員卒業してしまった sociability の後継者が現れたことに感動しました。

水餃子 10 個 50 NTD

夜市では krps さんと水餃子 10 個を買って食べます。krps さんは先程のアイスを食べすぎて吐きそうと言いながら食べたりと終始テンションがおかしくて、将来が心配で仕方ないです。腹の具合的にタージーパイが食べられなかったのだけ心残りとなりました。明日の観光には参加しないので、駅まで戻って日本勢とはここでお別れです。

ホテルに戻った後は、KoD さんにも手伝ってもらって、7 枚の FA 賞の紙の部分だけ剥がして持って帰ってもらうことにしました。

4 日目感想まとめ
  • Screenwalkers 優勝おめでとうございます！
  • 夜は日本勢で観光できて楽しかった (kotamanegi さんがキャリーしていただいてとても助かりました)
  • krps さん大丈夫？

大会翌日

5 日間の台湾もついに最終日を残すのみとなりました。トロフィーの寸法を測って、機内持ち込みに耐えるサイズであることを確認してから出発します。こういうときにやはり LCC ではない航空会社を使っていることのメリットが浮き彫りになります。

新幹線で空港まで移動し、お土産を買ってあとは帰るのみです。唯一の懸念材料であったトロフィーの機内持ち込みも無事に通って、つつがなく帰国できました。機内食のちいかわのマカロンが美味しかったことだけ注記しておきます。帰国後の税関だけあることを知らなかったですが、ここも特に問題ありませんでした。空港からは成田エクスプレスで豪遊して帰りました。

5 日目感想まとめ
  • 優勝するつもりならトロフィーの処置を考えておくと良さそうです

まとめ

非常に充実した 5 日間でした。運営の方々や日本・台湾選手を始めとして、お世話になった皆様に感謝申し上げます。12/21・22 の横浜も楽しみです。

ノープラン北海道 (2024/09/09-12)

交通 旅行

突然の思いつきで北海道に行った話です。

なぜ

お盆明けくらいから、会う人に「人生最後の夏休み」であることを指摘される回数が増えました。JAG 合宿や情報処理試験が後に控えていることを鑑みて、旅行に行くなら早めの方がいいと思ったので急遽行くことにしました。一回分だけ余ってた今季の 18 きっぷを消費したかったという意味もあります。ノープランだったのは、スカイメイト (後述) を使うためです。せっかく飛行機を使えるので、鉄道ではアクセスしにくい北海道にしました。

スカイメイトとは

日本航空 (JAL) の搭乗券を破格で買える革命的なサービスです。しかしながら無条件で使えるほど世の中甘くはなく、以下の 3 つの制約が存在します。

  • JAL カードまたは JMB 会員である。
  • 満 12 歳以上満 25 歳以下である。
  • 搭乗日の午前 0 時以降に予約する。

1 つ目は簡単に満たせ、2 つ目は不可抗力です。3 つ目が難しいところで、いつ乗れるかが不透明であるため、動的に旅程を決定するのが好きな人にはおすすめです。どれくらい安いかというと、東京・羽田から札幌・新千歳まで片道 1 万円足らずで行けました。

利用にあたってもう 1 つ罠があります。そう、予約する前に空港のカウンターまたは郵送手続きで「お客様情報」を登録しないといけないという点です。私は当日になるまでこのことを知らず、羽田空港に行って初めて予約できるようになったため、時間をロスすることとなりました。

レギュレーション

実際に縛りプレイをしていた訳ではないですが、実際の結果では満たされていたので、後付けをしています。

  • 飛行機及び宿泊の予約は、当日午前 0 時以降に行う

後先のことは考えず、毎日を貪欲に生きるというイメージです。

大まかなイメージ

事前の行きたい場所のイメージとして、新千歳から室蘭本線と函館本線を使って、室蘭・長万部・小樽・札幌の順にぐるりと一周し、3 泊 4 日程度で帰ってくるということを考えていました。行き当たりばったりなので、当然想定通りに行くはずもなく...。

実戦

0 日目

9/9 に日付が変わった午前 0 時、真っ先に JAL で新千歳行きのスカイメイトの便を検索する。空席がある最初の便は羽田 14:30 発。続いて 15:30, 16:30, ... の順で、遅くなるほど空きが多い状況であった。14:30 発だと到着は 16:00 になるので、遅いなあと思いながら仕方なしにこの便をポチる。「生年月日をご登録のうえ予約してください。」という表示が出る。JMB の会員になる際に生年月日を登録していて、カードも届いたので完全に油断していた。クレジットカードではないのでちゃんとした審査はされておらず、スカイメイトは年齢が超本質なので、言われてみれば当然の話だ。年齢確認をする方法を調べると、空港カウンターまたは郵送で身分証明書を提示するという 2 通りの手段があるらしい。こんなことなら郵送で事前に登録しておけばと後悔している間にも空席はみるみる埋まっていき、0 時半の時点で最速は 16:30 に。明日空港に行かないと始まらないので、何も考えずに寝ることにした。何も予約してなかったので、行けなかったら行かなければ良いという戦略を取れる点だけが心の拠り所である。かくして、何の成果も得られないまま 0 日目は終了。

1 日目

どうせ夜からしか動けないので、ゆっくり寝て 10 時頃に起床。空席状況を検索すると、昨日の時点では余裕のあった 16:30 の便が残り数席となっていた。行けるかもわからないし、行けたとしても新千歳に着くのが 19 時以降になることは必至である。羽田に行かないと何もできないので、昼を食べたら荷物をまとめて家を出る。

途中で暇つぶし用の本を買ったりした後、羽田空港には 13 時過ぎに到着。インフォメーションカウンターで聞いた JAL のカウンターに行くと、あっさり情報登録ができ、その場で予約もできた。搭乗するのはやはり 17:30 発 19:00 着の日本航空 525 便。

搭乗まで約 4 時間もあるので、空港内を探索することにした。インフォメーションカウンターで推された国際線の第三ターミナルに、ターミナル間を結ぶ無料送迎バスで向かう。タクシー乗り場や都心方面へ向かうバスが多々あり、バス停探しは非自明だった。約 5 分おきと山手線ばりの本数が運行されているにもかかわらず、車内は満員電車の様相を呈していた。第一ターミナルから第三ターミナルまでの移動時間も約 10 分かかり、大田区の 4 分の 1 を占める羽田空港の大きさを体感した。

PC を含む約 10 kg の荷物を背負って第三ターミナルに到着。第一ターミナルのカウンターで荷物を預けていれば良かったのだが、もう遅い。ラウンジで少し休憩した後、外国人向けで殿様商売な 4 階江戸小路を見物し、行きたかった 5 階展望デッキに向かった。デッキは晴れていて風通しも良くて居心地が良かったので、近くのカフェで飲み物を買ってしばらくここに居座ることに。他の writer が出題した JAG 合宿の問題を考察した後、16 時頃に退散。再び第一ターミナルに戻るが、ここでもバス停探しに苦戦し、二回ほど道を尋ねることになってしまった。

展望デッキ。羽田空港で一番好きなスポット

保安検査があっさり終わってしまったため生まれた暇を昼に買った本で潰していたら時間になったので、いよいよ飛行機に乗り込む。LCC に慣れた体にとって、JAL の広さ、機内設備の快適さはかえって新鮮だった。滑走路混雑のため 30 分遅れで出発。経験上北海道に行く飛行機は遅れるイメージがあったが、今回も多分に漏れない。飛行機に乗るときは、離陸の際の緊張感と着陸の際の安心感が私は好きである。機内では外をぼーっと眺めていたらあっという間に到着。到着間際の港湾、おそらく室蘭付近の綺麗な夜景が印象深い。

19 時半頃に新千歳空港に到着。すっかり日も暮れて少し肌寒い。もっと早く来れていれば室蘭まで行きたかったが、近辺で宿を探すことにした。選んだのは「ホテルウィングインターナショナル苫小牧」。料金は素泊まりで 9 千円と決して安くはなかったが、インバウンドの影響か 1 万円以下で泊まれる普通のホテルは数えるほどしかなかった。

千歳駅で千歳線に乗り換え、21 時頃に苫小牧駅に到着。北海道名物であるところのセイコーマートで食事を買ってからホテルに直行。余力があれば港の方まで散歩にいきたかったが、ロビーで柄の悪そうな方々が大声で喋っていて具合が悪くなったため断念。食事、シャワー、JAG 合宿の問題文校正の仕事を済ませ、いよいよ翌日の宿取りに着手する。

安定のセイコーマート。この見た目でめちゃボリューム多い

当初の予定では函館本線の長万部から小樽の間で宿を取りたかったのだが、いざ調べてみると最低価格で 1 万数千円してしまう。18 きっぷでそこそこ移動力があることをふまえ、函館、旭川、帯広など手広く調べてみたが、どこも同じような情勢だ。諦め半分で札幌を調べると、「ホテルルートイン札幌白石」が大浴場・朝食付きの 9 千円で残っていたので、迷わずそこに決定。1 万円切っているというだけで凄く安く見えてしまうのだから、夏の北海道は恐ろしい。さて札幌は室蘭本線と函館本線を乗り継いで行くにはあまりに遠いので、当初の予定を諦めて、「左辺を捨てて右辺で勝負する」方針に切り換えることにした。

宿取りで様々な可能性に思いを巡らせた結果頭が冴えてしまったので、テレビに備え付けの YouTube をだらだら見たりしてから午前 2 時頃に就寝。

2 日目

一人旅の朝は遅い。朝 9 時頃に起床してから身支度と大まかな旅程のイメージを済ませ、ギリギリの時間でチェックアウト。セイコーマートで 100 % りんごジュースを買って駅に向かったのだが、これが類を見ない美味しさだった。今夏 18 きっぷの最終日ということもあり、ここ苫小牧もキッパーで賑わいをみせている。この日の最初の目的地は登別。苫小牧から室蘭本線普通列車で室蘭方面に進み、約 40 分で到着。車窓からはいくつもの牧場と牛、馬が見え、北海道に来ていることを実感した。登別駅のホームは非常に長く、国鉄時代の、北海道鉄道全盛時代の、名残を感じられた。

いい感じの駅名標

温泉街はより内陸側にあるため、駅からさらにバスで 20 分程移動する。着いてからは、まずロープウェイを使ってクマ牧場を目指した。クマ牧場というのは聞いたことがなかったので興味津々である。

牧場では「アヒルの競争」という、キャッチーな名前をしているが実際には競馬のアヒルバージョンが行われていて人だかりができていたので私も参加することになった。レースに参加するアヒルには色のラベルがつけられており、競技プログラマーの私は問答無用で赤色の馬券ならぬアヒ券に 200 円をベット。レースが始まるやいなや赤のアヒルが先頭に躍り出て、いけると思いきや、飼育員が投げたエサに釣られて一気に後退。その隙をついた黒のアヒルに逆転優勝を許し、あえなく撃沈となった。黒のアヒ券を買っていた人も何人かいて、お金をもらっていたが、何円もらっていたのかは気になるところ。

赤コーダーしっかりしてくれー

完全にアヒルに気を取られてしまったが、ここの目玉はクマなのだ。エゾヒグマが飼育されているゾーンが雄と雌で 1 つずつあり、それぞれ約 5 匹ずつ飼育されている。ガラス越しで直に見える所では迫力があって怖いが、少し離れて餌やりされているのを見ると親しみが湧いてくるので不思議なものだ。これだけ至近距離でクマと対面できる場所も珍しい。もし山でそんなことがあったら即ち死である。

人間が投げる餌を食べるために口を開けるクマ

資料館を見てからロープウェイで街に引き返す。日帰り温泉の営業再開までまだ時間があったので、地獄谷を見に行った。登別温泉原泉の湧出地であるが、この日の湧き出しは控えめだったのが少し残念。奥まで行って引き返し、札幌ラーメン屋で腹ごしらえをしてから、目玉である温泉へと向かった。

登別地獄谷

この日行ったのは登別万世閣。温泉街にそこはかとなく漂う硫黄の香りから強酸性を想像していたが、それほど癖がなくて入りやすく、青みがかった白濁が特徴的だった。タオルレンタル込みで 1400 円で、綺麗で広い内湯・外湯に入れたので満足度が高い。事前にシャンプーやリンスを取ってから風呂場に行くシステムで、過剰に取って余してしまったことは反省...。

バスの時間まで少しだけ時間があったので、近くのミルキィーハウスでソフトクリームを食事。これは濃厚で分量も多く美味しかったのだが、バスの発車が秒読みだったため、あまり味わえなかった。次は余裕を持って来たい。

定刻のバスで登別駅まで引き返す。特に見所がなかったらもっと早く戻ろうと思っていたので、嬉しい誤算だ。再び室蘭線・千歳線を乗り継いで札幌・白石を目指す車内では翌日の宿を調べたが、やはりしっくりくるところはない。ちょうど日が暮れた頃に白石駅に到着。一旦ホテルで重荷を下ろしてから札幌の中心街へと繰り出すことにした。

白石は札幌駅から JR で二駅の位置であり、ホテルはその白石駅から徒歩 20 分となかなか険しい立地だった。夏の北海道で当日宿泊をするには、料金、立地、快適さ (プライバシー) の少なくとも一つは犠牲にしなければならない。札幌の住宅街を抜けてホテルに到着すると、一休みしてから再出発。目的地は札幌駅である。

再度駅まで戻り、電車に乗って札幌駅に到着。18 きっぷの恩恵で短区間でも気軽に乗れるのが地味にでかい。食事をしようと名前を聞いたことのある回転寿司屋のトリトンに行ったが、入店待ち多数のため既に打ち切られており、待つことすら許されなかった。営業終了間近の店も少なくなかったので、やむなく駅南側のフードコートで済ませることとなる。

食後は気分で駅前のカラオケ館に行った。何を歌っても採点の点数がほぼ同じなのでバグかと思いながら小一時間歌い続ける。ヒトカラは実は初めてなのだが、一人旅行の余興としてちょうどよく感じたので、明日もまた来ようかと思った。

22 時の札幌駅。駅舎すき

外に出るとすっかり夜が更けていて、心なしか街の灯も少なくなっている気がした。いい頃合いなので、白石のホテルに帰宅。着いたのは 23 時頃だった。想像以上に一日楽しめたのでこのまま大浴場で風呂に入って就寝、と行きたいところだが、最後の宿取りをしなければならない。これがまた億劫な所で、小樽か札幌に泊まりたいが今日ぐらいの値段のホテルはないし、明日帰るのももったいなくて気が進まない。長考の末プライバシーを捨てて、札幌のカプセルホテル「ちょい寝ホテル札幌手稲」を選択。値段は過去最安の 5 千円だったが、不安は尽きない。が、そんなことを考えてもどうしようもない。この日もだらだらしてから 2 時頃に就寝。長い一日だった。

3 日目

いつも通り 9 時に起床し、ホテルのビュッフェで食事をしてから出発。そんなにだらだらしたつもりはなかったが、チェックアウトした後スマホを見ると 10 時ちょうどで冷や汗をかいた。札幌駅でコインロッカーに荷物を預けた後、快速エアポート号で小樽を目指して再出発。小樽までは 40 km 40 分で、本数も多くて便が良い。ギリギリの時間に乗り込んだ車内は乗車率 8 割といったところで、小樽の人気ぶりを感じる。車内では lichess のタクティクスをやって、不正解を繰り返して瞬く間にレートを溶かした。負けると勝つまでやりたくなってしまう性分なので、こういうのを旅行中にやってしまうのをやめたい。

駅に着くと、とりあえず海の方に向かって歩いた。小樽の地理については何も知らなかったが、どの辺りが賑わっているかは経験則でわかる。進んでいくと突然廃線跡が現れ、鉄道好きとしては胸が小躍りした。ただ、このときは人が多かったのでまた後で来ることに。さらに進むと運河があり、岸にはレンガ造りの倉庫が立ち並んでいた。いかにも観光地ですというような場所だ。ここから奥は明らかに人が少なくなっていたのだが、気になったので一応海まで進んでみる。そこには埠頭があったという当然の結果だったのだが、空いていて海風も心地よかった。こういう観光地の裏スポット的な場所は好きだ。

小樽運河。観光船もあった

雲が淀んでいた午前とは裏腹に午後は時折晴れ間が差し込む。運河の隣の道まで戻って、南に足を進める。食事をしていなかったので、海鮮丼の店が立ち並ぶエリアから適当に選んだ店に入った。3 千円の海鮮 10 種盛りみたいなのを注文。写真で見ると何の変哲もない海鮮丼なのだが、嚙み切るのも容易ならざるほどの肉の厚さには驚かされた。これが北海道の魚かと思った次第である。

小樽の海鮮丼。とにかく肉が厚い

方向もよくわからず適当に歩いていると、日銀を始めとした様々な銀行の旧支店が立ち並ぶ場所に来ていた。5 年前に同じ北海道の港町である釧路に行ったときに日銀支店があったのを思い出したが、何か関係があるのかはわからない。ともかく、先ほどの廃線跡、運河の倉庫も合わせて、明治から昭和にかけての小樽の経済的な繁栄を感じられる場所だった。

どうやら北に進んでいたようで元の場所に戻ってしまったため、来た道を再度南下。すると、明らかに観光のメインストリートであるような場所に辿り着く。涼しさや雰囲気からどことなく軽井沢を想起したのは私だけだろうか。この通りでは、ルタオや北菓楼などの名だたる洋菓子店の本店が立ち並ぶ壮観が何より印象的だった。ルタオで試食したチーズ入りのラングドシャがシンプルに美味しかったのでお土産として購入。値段や常温保存可能性という観点からもちょうど良かった。

最深部には小樽オルゴール堂が聳え立つ。結論から言うとここがとても良くて、小樽に来て良かったと思わされるような場所だった。館は三階建てで、一階はオーソドックスなオルゴールが、二階と三階はジブリなどのキャラクターと関連したオルゴールが展示されている。数は夥しく、しかも自由に触って鳴らせるのだからこの上ない。上についたネジを回す一番シンプルなもの、箱型になっていて閉じると中断されるもの、紐を引くタイプのもの、車型になっていて鳴りながら走るもの、底のネジを回すと台座が回るものなど、多種多様なオルゴールがある。音色、妙に平成世代にマッチした曲選、ネジを回すと音が鳴るというシンプルなからくりに心を擽られ、隅から隅まで鳴らして遊んだ。さんざん遊んでおいて何も買わないのも心苦しいが、また機会があれば来たい。

小樽オルゴール堂。一推しスポット

メインストリートを後にし、山側の商店街らしき場所を見に行ったのだが、こちらは寂れているとまでは言わなくとも完全に人気がなく、まさに光と影という感があった。そのまま突っ切って駅まで戻ってもまだ 15 時だったので、改めて廃線跡を見に行くことに。ここは小樽市の旧手宮駅と現在の函館本線南小樽駅を結んでいた貨物線で、1880 年に開業して 1985 年に廃線となったようだ。廃線跡に来ると、やはり線路のど真ん中を歩いて Stand by Me をするのが楽しい。線路の末端まで行くことはできなかったが、旧手宮駅や南小樽駅まで残っているのかは気になるところ。

旧手宮線跡。北海道最初の鉄道だそう

15 時半発の快速列車で小樽を後にし、札幌へと戻る。電車は相も変わらず立席で、地元民の会話に耳をそばだてたり夕食のことを考えてたらあっという間に札幌に到着。空はまだ明るいが、並ばなくてもいいというアドバンテージを活かすべく早々に食事をすることにした。少考の末行ったのは「札幌ザンギ本舗」。ボリューミーなザンギ 4 つと小鉢 2 つもついて、900 円でいいの？というのが率直な感で、店員さんの愛想も良くて非の打ち所がなかった。

ザンギ 4 種盛り。赤いのは紅しょうがらしい

食事に成功してからは、東京を出る前に友人に勧められたサッポロビール博物館へ赴く。余談だが、こちらへ行く道中に昨日訪れたトリトンがあり、17 時の時点で既に外待ちが発生しているのを見て笑ってしまった。博物館は上から下に降りていくシステムで、上の階でサッポロビールの歴史の展示を見た後、下の階の試飲会場で飲むという流れになっている。サッポロビールは、ドイツのビール製造法を真似して北海道でやってみたら、独特の風味が出て発展したらしい。試飲ではサッポロビールクラシック 240 mL で優勝。アルコール度数は 5 % だったが、酒の弱さに定評のある私でも全く酔わなかったところに質の良さを感じた。おつまみなしでも飲みやすく、満足である。

優勝

館を出るとちょうど日が暮れて、レンガ造りの建物群と橙色の照明が情緒的な雰囲気を醸し出している。ここからは札幌大通りを目指す。真南に足を進めると、大通りらしき道とクロスするが、この時点では写真でよく見るような場所ではない。さらに西に進むと、すっかり暗くなった空に一際目立つテレビ塔が映る。このテレビ塔には展望台があるので早速登る。約 90 m の高さから望む札幌の夜景は綺麗だった。視界の奥まで住宅街が広がる東側、すすきのの歓楽街が眩しい南側、大通りが中央に構える西側、オフィス街の北側と、見る方向によって全然違う景色を味わえる。人口 190 万人を抱える札幌市の規模を体感できた。

テレビ塔から望む大通り

日課のカラオケ館に向かおうと札幌駅の目の前を歩いていたところ、見覚えのある人と目が合う。北大の同学年競技プログラマーの itigo さんっぽいなと思った瞬間には ICPC 横浜の青 T シャツを着ているのを認知して、確信に変わった。勢い話しかけてみるとドンピシャで、こちらの顔は覚えられていなかったものの「tokusakurai です」と名乗るとすぐに認知してもらえた。昨年の JAG 合宿で一言二言喋っただけなのだが、すぐに打ち解けて周辺の散歩に連れていってくれて嬉しかった。大通り沿いを歩きながら、ネカフェやカラオケでの夜の明かし方、札幌に存在する座標系、そこかしこで開かれる屋台祭り、就職先、北大の競プロ事情などの話をして非常に楽しかった。最後は時計台を経由して 21 時前に札幌駅で解散。あまりに突然の出来事だったが、あそこで機を逃さずに声をかけられて良かった。ここしかないというタイミングをしっかり掴めるように生きていきたいものだ。

朝コインロッカーに預けた荷物を忘れずに回収し、宿のある手稲に向かう。札幌駅から普通列車で 20 分の距離にある手稲駅は、札幌市手稲区に属する。宿は二段形式の木でできたカプセルホテルで、布団の隣に荷物を置く場所があって十分な広さだった。言うなれば、寝台特急サンライズ号ののびのび座席をそのままバージョンアップさせた感じである。利用者は私のような限界大学生が多いのかと想像していたが、中年以上の方が多くて意表を突かれた。共用のシャワールームが 2 つと洗面所 3 つ、各人が使えるロッカーなどの設備は十分で、人が増える前にとシャワーを済ませた。

3 日後から JAG 合宿があるので、明日には帰るつもり。スカイメイトの予約は日付が変わってからであり、イヤホンも持ってきてなかったので、1 時間ほど本を読んで暇を持て余した。0 時を回った瞬間に検索をかけると、新千歳を出る予約可能な最も遅い便は 15:10。想定より大分早かったが、ないものをねだってもしょうがない。疲れたしやれることもないのでそのまま就寝。

4 日目

長いような短いようなでついに最終日を迎える。9 時を過ぎ、多くの人が出て行って空いた洗面所で身支度を済ませてからまたもやギリギリの時間でチェックアウト。itigo さんから「ていね温泉ほのか」の休憩処で泊まれることを教わったので、次はこちらに来てみたい。手稲駅では地元のパンが売られていたので 1 つ購入。おまけでつけてくれたパンが買ったものより分量が多くて面白かった。時間の都合で札幌を割愛して千歳に直行。本当は 1 日目に行こうと思っていた千歳水族館へと向かう。

水族館は千歳駅から歩いて 10 分強の場所にある。ここの一番の売りはサケで、隣を流れる千歳川に直に面した水槽もある。他の魚と見比べて、サケは長くて鋭い顎が特徴的だ。時期が良ければサケの遡上が見られるそうだが、この日見られたのはウグイだけだった。隣の道の駅では鮭の海鮮丼を食事。水族館は空いていたが、こちらは混んでいて 10 分以上待たされたように思う。

これが、

こう！

千歳駅から新千歳空港までは二駅と程近い。出発 1 時間半前に新千歳空港に到着。発着する便の行き先を見ていると、国内線では北海道・東北、国際線では中国・韓国が多かった。土産を買い足してから搭乗。帰りは 10 分程度の遅れで無事に到着。京急蒲田から東急に向けて歩いているだけで汗が湧き出てきたところで、東京に戻ってきたことを実感した。

感想

ぱぱっと済ませようと思っていたのに、今回も一万字コースになってしまった...。スカイメイトとノープラン旅行は相性抜群なので、また思い立ったときにやりたいです。

瀬戸内しまなみ海道 (2024/07/28-29)

交通

瀬戸内しまなみ海道を自転車で走破したという話です。

瀬戸内しまなみ海道

瀬戸内しまなみ海道は、四国愛媛県今治市と本州広島県尾道市を、途中瀬戸内海上の 6 つの離島を経由して結ぶ全長約 70 km の道路です。本州と四国を結ぶ陸上の道としては他に明石海峡大橋と鉄道も通る瀬戸大橋がありますが、サイクリングロードが併設されているのはしまなみ海道に特有です。

出典：国土地理院ウェブサイト

今回は、前日 7/27(土) に松山まで移動し、7/28(日) から 29(月) の 2 日間にかけて、今治から尾道のルートをレンタサイクルで走行しました。

レンタサイクル

しまなみジャパンのレンタサイクルを利用しました。こちらは今治・尾道の他に経由する島にも貸出拠点があり、どこからでもレンタルと返却ができます。海道の途中で力尽きても、そこで返却してフェリーで渡るという選択肢も取れるようになっています。今回はロードバイクを借りたため、利用料金は 1 日あたり 3,000 円で、合計 6,000 円でした。

荷物の配送

しまなみ海道を渡った後もしばらく旅行を続ける予定で来たので、必要最低限以外の荷物は本州側に送る必要があり、ヤマト運輸を利用しました。今治と尾道の両駅の徒歩圏内にヤマト運輸の営業所があったので、営業所から営業所への配達をしてもらいました。もちろん配送の料金はかかりますが、走行中の荷物が軽くなったのはかなり大きかったと思います。

経由する離島

経由する島は、今治から尾道方面の順に、大島、伯方島、大三島、生口島、因島、向島の 6 つです。1 日目に今治から生口島まで行って宿泊し、2 日目は生口島から向島まで行き、最後の向島と尾道の橋は自動車専用なのでフェリーを使いました。

1 日目

朝 7 時半頃に起床し、松山を出発。今治駅についてからヤマト運輸に荷物を預けに行って、10 時頃にスタートした。

今治から大島

今治のレンタサイクル営業所を出てすぐのところからサイクリングロードは始まっていて、道路の脇にサイクリングロードであることを示す青い線が描かれていた。ロードバイクに乗るのは初めてで最初はバランスの取り方に苦労したが、すぐに慣れてその圧倒的な軽快さに魅了された。前輪は 2 段階、後輪は 8 段階でギアを変えることができる仕様で、大島へとつながる来島海峡大橋までの約 5 km はギアを上げて快走した。前輪のギアは左に、後輪は右についていたのだが、ギアを上げるときに押す方向が左右で異なるのが非自明に感じた。

橋の袂まで来ると、高度を上げるためのループ状の坂道が始まる。島を発つ際に橋を渡るために坂道を登って高度を上げ、島に下りるときは逆に坂道を下るという構図は、ここから最後までずっと変わらない。この坂道の繰り返しがしまなみ海道走破に向けての難所となる。

来島海峡大橋は、実はしまなみ海道の橋の中で最も高度が高かったのだが、まだ走り始めで十分な体力があったことからそれほど苦労はしなかった。やはりロードバイクの軽さと車輪のでかさはママチャリとは一線を画している。

最初の来島海峡大橋から望む瀬戸内海

当日の快晴、35 度を優に超える気温、坂道が相まって汗まみれとなった体を冷やす、平坦な橋の上を走っているときの海風は心地が良い。橋の中央を超えると下り坂が続き、登るときの苦労が嘘かのように爆走して島まで下りる。

大島から伯方島

大島は、経由する島の中では海道との共通部分が最も長く、島の中にある峠を越える必要もある。島に到着した後、スーパーで飲み物を調達しに行ったのだが、そこで地元の方からギアが外れたときの対処法を教わったのが非常に有益だった。後輪を回してチェーンを弛ませ、上側を引っ掛けるとのことである。

この大島の峠はしまなみ海道での最大の山場であると感じた。というのは、そこそこな傾斜の坂道が一直線上に続いて終わりが見えず、ループ状の坂道とは違って木陰もないためじりじりと焼かれるような感覚になったからである。

辛うじて峠を越えると、次の伯方・大島大橋に差し掛かる。このあたりが、橋を上って下りて島を渡ってというサイクルを体が理解し始める頃合いとなる。

伯方島から大三島

今治を出て 2 番目に着く島が、伯方の塩で有名な伯方島である。正午を過ぎていたので、道の駅に寄って食事。名産の塩を使った伯方の塩ラーメンを頂いた。これだけ汗をかいたので今日は塩分フリーデイである。

食事

食後は隣接するビーチで海水浴、する準備を用意していなかったので、裾をめくって足だけ海水に浸った。もっとも、同行者の一人は服を着たまま全身浸かって泳いでいたのだが。多くの海水浴客が押し寄せていたが、瀬戸内海の離島ということもあって暖かく澄んだ水質が評価されているのであろう。

次の大三島橋までは程ない道のりとなる。

大三島橋上の案内図。海道の高度の変化がわかって面白い。

大三島から生口島

大三島は経由する島の中で最も大きいが、途中はどこにも寄らず黙々と漕ぎ進める。次の生口島とを結ぶ多々羅大橋の手前のフードコートつき土産処に立ち寄り、一服と記念撮影をしてから 1 日目の最終目的地である生口島に向けて再出発。時刻は 15 時前で、照りはピークを越していて幾分か走りやすくなっていた。

多々羅大橋 with 石碑

1 日目最後の橋上りだったが、この頃には既に坂道を上る際に自分にとって最適なギア (前輪が 1、後輪が 5, 6) を見つけており、最初と比べて高速かつ楽に上れるようになっていた。

橋上でも県境が明示されている。

多々羅大橋の橋上を境に、ここからは広島県尾道市となる。

生口島

しまなみ海道は島の東側を通るのに対し、この日の宿は西側に位置していたので、しばし海道と別れることに。生口島にも海水浴場があり、伯方島で服ごとダイブした彼がまた入りたいというので私も付き合うことにし、他の人たちとは別行動となった。私もここでは泳ごうと思い上の服だけ脱いだのだが、伯方島の海よりも冷たかったのでなかなかダイブする気になれなかった。時間をかけて少しずつ着水していき、最終的には全身浸かって設置されている浮島まで泳いだ。海に入るのは久しぶりで、泳ぎに難はないものの足場がないというのはプールでは味わえない感覚である。カップルや陽気なグループ客ばかりの中、我々は着衣したまま何をやっているのだろうか。

海水浴客で賑わう瀬戸田サンセットビーチ

宿

しばらく浮島で屯した後、灼熱の砂浜を素足で渡り、サイクリングを再開。Airbnb で取ってもらった宿に一直線に向かった。宿では皆と合流し、初手入浴。皆疲れていたので、食事は地元のスーパーに買い出ししに行き、焼いて食べる用の豚肉・鶏肉と人数分のカップ焼きそば U.F.O. 爆盛り、明朝の食事を購入。宿のフライパンを使って焼きそばパーティーの様相を呈したが、U.F.O. の量が多くて最後は完全に食傷になった。

寝室は 2 つあったが、同じ部屋の人達はすぐ寝てしまったため、無駄に元気が有り余っていた私は別の部屋に行って雑談をした後、0 時 30 分頃に就寝。

2 日目

この日は訳あって 8 時頃に起床したが、出発したのは 10 時頃。脚は特に問題がなかったが、上半身に少し筋肉痛があった。

生口島から因島

1 日目に約 50 km 走ったので、残りは約 1/3 の 25 km。1 日走って走り方のコツを掴んだこともあって、ここからはサクサク進む。生口橋を渡り、次の島はもう尾道側から数えて 2 つ目である因島となる。

因島から向島

因島でも寄り道せずに最後の向島までノンストップで走り続けたが、傍目でも柑橘類の八朔の名産地であることがわかった。さらに、ここ因島は囲碁の本因坊秀策の出身地でもあり、記念館もあるようだった。今回は立ち寄ることができなかったが、またの機会があればぜひ寄っておきたい島である。

向島から先はフェリーなこともあり、自転車で渡るのはこの因島大橋がラスト。

向島から尾道

尾道まであとわずかとなった。しまなみ海道の車道は尾道駅より大きく東に逸れた尾道大橋を通るのだが、自転車では通れない。代替手段として、尾道駅のちょうど対岸にある港から自転車を載せてフェリーに乗ることとなる。

向島は割に大きく、フェリー港まで約 10 km 程あったが、ここまで来ればウイニングランに他ならない。実際には小一時間ほどかかっていたようであるが。フェリーは約 10 分に一本という頻度で運航しており、料金も自転車を合わせて 110 円と非常に安い。走行距離自体も数百メートルと短く、地元の高校生の足となっていることがわかった。

向かって左が向島、右が尾道。両島の近さがわかる。

尾道に到着した後は自転車を返却し、2 日間に及んだサイクリングもついに終了となった。

感想

当初の想定では猛暑と坂の上下で走破できないのではないかと思っていた部分もあったのですが、実際にやってみると風も涼しくて下り坂は楽なので意外と余力がありました。しまなみ海道サイクリングの通行料無料は 2026 年 3 月までらしいので、これを見ている方はぜひお早めに行きましょう。

甲斐大和駅周辺散策 (2024/07/09)

旅行

大菩薩嶺に登るために甲斐大和駅からバスで登山口まで行こうとしたところ、バスが全日運休の日だったという話です。

大菩薩嶺とは？

山梨県甲州市と丹波山村にある標高 2057 m の山です。登山口が標高 1600 m の位置にあり、約 4 時間で山頂まで往復できる初心者向けの登山コースがあります。昨年の 8 月に碓氷峠を越えたのを大学の同期に知られてしまい、今回は登山に誘われました。

碓氷峠越え (2023/08/22) - トークサクライ

登山口までのアクセス

出典：国土地理院ウェブサイト

甲州市は大月市と甲府市の間に位置しています。JR 中央本線の駅で言うと、甲斐大和 (地図中 B)、勝沼ぶどう郷、塩山 (地図中 A) の 3 つがあります。登山口のある上日川峠には、甲斐大和駅から栄和交通のバスが出ています。

都内から電車で行くと、新宿から高尾まで約 40 分、高尾から甲斐大和まで約 1 時間、甲斐大和から上日川峠まで約 40 分で、乗り継ぎが良ければ 2 時間半くらいで着けます。ただし、朝のバスは平日で 8:10, 9:50 の 2 本、休日でも 8:10, 9:20, 9:50 の 3 本しかないので、日帰りで行く場合は朝早く出発する必要があります。土休日は毎日運行していますが、平日は運行日が決まっていることにも注意が必要です。

バス時刻表

当日の予定

朝 8 時前に高尾駅で集合して、高尾 8:01 発の中央線甲府行に乗って 9:04 に甲斐大和駅に着き、9:20 発のバスに乗る予定でした。実際は、京王線の遅延の影響で同行者の高尾到着が遅れたため、40 分後の甲府行に乗ることになります。この時に漸くバスのダイヤが平日と土休日で違うことに気づきましたが、どのみち乗ることになるであろう 9:50 分発のバスは平日も運行しているので、特に問題ないだろうと思っていました。

列車は 3 分遅れで 9:44 に甲斐大和駅に到着します。駅前の広場にあるバス停でバスを待っていたところ、同じく登山客であろうおばさんから「今日はバスは運行していない」と言われ、そこで初めて平日は毎日運行してるわけではないことに気づきます。

代替案として、塩山駅からも登山口に向かうバスが出ていることを教えてもらいましたが、その行先は上日川峠とは別の登山口で、より山頂から離れているため、登山を断念して甲斐大和駅周辺でハイキングをすることになりました。

ハイキングコース

以下の地図の経路が実際歩いた経路になります。

出典：国土地理院ウェブサイト

A は甲斐大和駅、B は景徳院、C は竜門峡入口、D はやまと天目山温泉です。

甲斐大和駅から景徳院

甲州市の中心駅は塩山駅で、駅前は閑散としています。駅前では、広場にある武田勝頼公の銅像が一際目を引きました。武田勝頼が自害し、事実上武田家が終焉した地がこの近辺の田野という地区であり、それを語り継ぐために銅像が作られたようです。広場の前の坂を上るとすぐそこに甲州市立大和中学校がありましたが、人がいる気配はありません。どうやら、数年前に統廃合によって廃校となったようです。

甲斐大和駅前広場にある武田勝頼公像

景徳院・竜門峡方面へ続く道は、県道と林道の 2 つがあります。そこで、行きは林道、帰りは県道で行こうと考えていましたが、林道が工事により通行止めになっていたため、やむなく県道を往くこととなりました。景徳院までは 2-3 km の緩やかな坂道となっています。

景徳院から竜門峡入口

景徳院は、田野で自害した武田勝頼やその親族を弔うために、徳川家康の命で建立されたもので、墓や自害の際に座ったとされる生害石があります。その他にも、この周辺は大きい墓地が複数ありました。

景徳院を後にすると、登山用に買ったおにぎりを食べてから竜門峡へと向かいます。道中には、「蕎麦切り発祥の地 甲州市」を謳う蕎麦屋があったのが印象強いです。蕎麦切りというのは現在でいうところの通常の蕎麦で、昔は蕎麦がきや蕎麦餅として食べられていたところ、麵にして食べるというのは画期的だったようです。

竜門峡入口までは日川の横を約 1 km の道のりです。

竜門峡入口からやまと天目山温泉

竜門峡に入って、ここから先はいよいよハイキングらしいコースとなります。遊歩道の入口には熊注意の看板がありましたが、やはり山となると熊は避けては通れません。

クマー

遊歩道では、最初は日川の上を歩きます。川が近くを流れていると、せせらぎも相まってとても涼しく感じられるものです。しばらく進むと下り道になり、川まで降りることができます。

日川渓谷

川の流れは急で、渡るのにも一苦労しましたが、その分川の真ん中に立ったときは迫力を感じられました。こうして川に触れていると、子供の頃に地元の川に入って遊んでいたことが思い出されます。

傾いた橋

その後も渡るのが不安になるような橋や坂を上りながら川沿いを進み、最後に斜面を登ると再び県道に出ます。ハイキングでちょうどよく汗を流したところに温泉があったので、迷わず入ります。

やまと天目山温泉

温泉は料金 520 円で露天風呂もついていて、非常に満足のいくものでした。pH 10.3 の高アルカリ性で肌がぬるぬるする泉質と 35 度程度の適度なぬるさが相まって、彼此 1 時間近く入っていたと思います。

風呂を上がった後は、友人が持参していた非常食用のドライカレー (大学で余った分を配ってるやつ) を、魔法瓶で運んでもらったお湯を使って作りました。しっかりとカレーの風味があって思っていたより美味しかったですが、味は単調でボリュームがあるため最後の方はやや食傷気味になりました。

低気圧によりパンパンに膨らんだじゃがりこ

食後は眠気に襲われて小一時間横になった後、17 時頃になって温泉を後にします。温泉にいる間、雨がぱらついていたようでした。

帰り道

帰りは甲斐大和駅まで国道に沿って直線で向かいます。日が暮れてきて少し肌寒いくらいでした。往路は紆余曲折合ってかなり時間がかかりましたが、復路は呆気ないくらいにあっという間でした。

絵に描いたような円形の虹

甲斐大和駅のホームに着くと、綺麗な円形の虹がかかっていました。

感想

まさかのバス運休で想定とは全く違うことになりましたが、こういう行き当たりばったりな時こそ旅行は面白いともいえるので、今回は非常に良い経験になったと思います。甲斐大和駅周辺も、歴史と自然が交錯していて楽しめました。

第13回 SQLコンテスト (2024/06/23)

SQL

第 13 回 SQL コンテストに参加しました。最終結果は 4 完 100 点で 12 位でした。

最終結果

近況報告

最近はあまり SQL に触れられていないですが、いくつか初心者用の SQL コンテストがあったので、それで少しリハビリをして臨んでいます。

コンテストの振り返り

問題 1

名前の 2 文字目が田であるような行だけ抽出する問題です。これに対しては、SUBSTR 関数を使って一致判定すればよいです。

開始約 1 分後に AC。

SELECT
    MEMBER_CODE AS CODE,
    LAST_NAME AS L_NAME,
    FIRST_NAME AS F_NAME
FROM
    MEMBER_MST
WHERE
    SUBSTR(LAST_NAME, 2, 1) = '田'
ORDER BY
    MEMBER_CODE DESC

問題 2

ITEM テーブルにあるデータについて、同じデータが ITEM_HISTORY テーブルにも存在するか、また存在するならば名前が変わっているかを判定する問題です。2 つの表を結合したいですが、ITEM テーブルにのみ含まれる情報も表示したいので、INNER JOIN ではなく LEFT OUTER JOIN を使うのが適切です。

開始約 5 分後に AC。この位置の問題としてはいつもより簡単な印象を受けました。

SELECT
    ITEM.ITEM_CODE AS CODE,
    CASE
        WHEN ITEM_HISTORY.ITEM_NAME IS NULL THEN ITEM.ITEM_NAME
        WHEN ITEM.ITEM_NAME != ITEM_HISTORY.ITEM_NAME THEN ITEM.ITEM_NAME
        ELSE NULL
    END AS NAME
FROM
    ITEM
LEFT OUTER JOIN
    ITEM_HISTORY ON ITEM.ITEM_CODE = ITEM_HISTORY.ITEM_CODE
ORDER BY
    CODE DESC

問題 3

LINE_ID と SEAT_NO の組に対して 0 か 1 が割り当てられているデータに対して、LINE_ID が同じかつ SEAT_NO が 3 連続している箇所であって、全てに 0 が割り当てられているものを列挙するという問題です。各 LINE_ID, SEAT_NO の組 (x,y) に対して、LINE_ID が同じ x で、SEAT_NO が y 以上 y+2 以下の座席に対する 0 の個数を求めるというアプローチを取りました。この値が 3 であることが、(x,y),(x,y+1),(x,y+2) 全てに 0 が割り当てられていることの必要十分条件となります。また、ウィンドウ関数を用いることによって、簡単かつ効率的にこの値を求めることができます。

開始約 12 分後に AC。いい方針をすぐに思いつけたので素早く解くことができました。また、私自身が書いた記事が自分の役に立ったので良かったです。

WITH T1 AS(
    SELECT
        LINE_ID,
        SEAT_NO,
        SUM(1 - RSV_STATUS) OVER(
            PARTITION BY LINE_ID
            ORDER BY SEAT_NO
            ROWS BETWEEN 0 FOLLOWING AND 2 FOLLOWING
        ) AS CNT
    FROM
        SEAT_RESERVE
), T2 AS(
    SELECT
        LINE_ID AS LINE,
        SEAT_NO AS SEAT_F,
        SEAT_NO + 2 AS SEAT_T
    FROM
        T1
    WHERE
        CNT = 3
    ORDER BY
        LINE DESC,
        SEAT_F ASC
)
SELECT
    *
FROM
    T2

問題 4

同じ人に対するデータが 2 つ以上あるものに対して、直近 2 つのデータの差分を計算するという問題です。これはかなり素直な問題で、RANK 関数を用いて直近 2 つのデータを抽出し、さらに前問同様にウィンドウ関数を使って 2 つの差分を計算することができます。

開始約 12 分後に AC。最終問題としてはかなり容易でしたが、問題文の読み取りとエラー処理に時間がかかった影響で出遅れてしまいました。

WITH T1 AS(
    SELECT
        MEMBER_CODE AS CODE,
        CHECKUP_DATE AS CK_DATE,
        WEIGHT,
        RANK() OVER(
            PARTITION BY MEMBER_CODE
            ORDER BY CHECKUP_DATE DESC
        ) AS RANK,
        COUNT() OVER(
            PARTITION BY MEMBER_CODE
        ) AS CNT
    FROM
        HEALTH_CHECKUP
), T2 AS(
    SELECT
        CODE,
        CK_DATE,
        RANK,
        WEIGHT - SUM(WEIGHT) OVER(
            PARTITION BY CODE
            ORDER BY RANK ASC
            ROWS BETWEEN 1 FOLLOWING AND 1 FOLLOWING
        ) AS CHG_WT
    FROM
        T1
), T3 AS(
    SELECT
        CK_DATE,
        T2.CODE,
        LAST_NAME || FIRST_NAME AS NAME,
        ROUND(CHG_WT, 1) AS CHG_WT
    FROM
        T2
    INNER JOIN
        MEMBER_MST
            ON T2.CODE = MEMBER_MST.MEMBER_CODE
    WHERE
        RANK = 1
        AND ABS(CHG_WT) >= 4.999 
    ORDER BY
        CHG_WT DESC,
        T2.CODE DESC
)
SELECT
    *
FROM
    T3

感想

今回は全体としてかなり簡単だったと思いますが、スムーズに解くことができたのは良かったと思います。

線形計画と分離問題

組合せ最適化

有界多面体における線形最適化問題が解ければ分離問題も解けることを見ていきます。前提知識として、楕円体法によって分離問題が解ければ線形最適化問題が解けることを用います。

多面体

ここでは、多面体と関連する用語の定義を確認します。\mathbb{R}^n の部分集合 P であって、行列 A\in\mathbb{R}^{m\times n} とベクトル b\in\mathbb{R}^m を用いて

 

P=\left\{x\in\mathbb{R}^n\mid Ax\leq b\right\}

 

と表されるものを多面体と呼びます。つまり、多面体とは有限個の半空間の交わりです。

用語

支持超平面
超平面 \left\{x\in\mathbb{R}^n\mid c^\top x = \delta\right\} は、\max\left\{c^\top x\mid x\in P\right\} = \delta を満たすとき、P の支持超平面であると言います。
面
P とその支持超平面の交わりは、P の面と呼ばれます。P 自身も P の面です。
端点
x\in P は、\{x\} が P の面であるとき、P の端点であると言います。
ファセット
P 自身を除いた P の面の中で極大なものは、P のファセットと呼ばれます。
妥当不等式
P を包含する半空間 \left\{x\in\mathbb{R}^n\mid c^\top x\leq\delta\right\} について、不等式 c^\top x\leq \delta は P の妥当不等式と呼ばれます。
ファセット定義不等式
P の妥当不等式 c^\top x\leq\delta は、超平面 \left\{x\in\mathbb{R}^n\mid c^\top x = \delta\right\} と P の交わりがファセットであるとき、P のファセット定義不等式と呼ばれます。

P が 2 次元平面上の凸多角形であるとき、端点は頂点に、ファセットは辺にそれぞれ対応します。P が 3 次元空間上の凸多面体であるとき、端点は頂点に、ファセットは面にそれぞれ対応します。

分離問題

分離問題とは、多面体 P と点 y を入力として、y が P に含まれるかを判定し、もし含まれないならば y と P を分離する超平面を 1 つ求めるという問題です。後者では、具体的には P の妥当不等式 c^\top x\leq\delta であって c^\top y\gt \delta を満たすものを求めます。

例：一般グラフの完全マッチング多面体

多面体 P が Ax\leq b の形で明示的に与えられるならば、y が全ての不等式を満たすかを確認すれば、分離問題は自明に多項式時間で解くことができると思われるかもしれません。この指摘は至極真っ当なものですが、実際には P は明示的には与えられず、指数本の定義不等式が存在する場合も考えられます。具体例として、一般グラフ G=(V,E) の完全マッチングの特性ベクトルの凸包 P を考えてみましょう。

 

P=\left\{x\in\mathbb{R}^E\;\middle|\;\begin{array}{l}x(e)\geq 0\quad(\forall e\in E) \\ x(\delta(v)) = 1\quad(\forall v\in V)\\ x(\delta(S))\geq 1\quad(\forall S\subseteq V\textrm{ with }|S|\textrm{ odd}) \end{array}\right\}

 

1 行目と 2 行目の不等式はそれぞれ |E| 本、|V| 本しかないので、分離問題を解く際には愚直に代入することができます。3 行目の不等式は奇カット不等式と呼ばれるものであり、全部で O(2^{|V|}) 本の不等式があります。この多面体 P に対して分離問題を解く際には、y が与えられたときに y(\delta(S))\lt 1 となる奇数の部分集合 S\subseteq V を見つけることができれば十分です。この問題は奇数の最小カットを求める問題に帰着でき、多項式時間で解くことができます。以上が、P の不等式は明示的には与えられなくても分離問題を解くことができるような例です。

楕円体法：分離オラクルを用いた線形最適化

楕円体法は、多面体 P の分離問題を解くオラクルを高々多項式回呼び出して、P 上の任意の線形最適化問題 (すなわち実行可能領域が P である線形計画問題) を解くアルゴリズムです。具体的には、ベクトル c\in\mathbb{R}^n に対して

 

\max\left\{c^\top x\mid x\in P\right\}

 

の最適解であって、P の端点であるものを求めます。ここではアルゴリズムの詳細については割愛します。

多面体が不等式の交わりとして明示的に与えられる場合の線形計画問題では、全ての不等式を満たすかを愚直に確認することで分離問題を多項式時間で解くことができるため、楕円体法によって線形計画問題の多項式時間アルゴリズムが与えられていることになります。

線形最適化オラクルを用いた分離

ここからは、本題の線形最適化を用いた分離アルゴリズムについて扱います。具体的には、0 を内部に含む有界多面体 P について、その双対多面体 P^* に楕円体法を用いることで、線形最適化オラクルを用いた分離が可能となります。以降では、P の分離問題を \textrm{sep }P、線形最適化問題を \textrm{opt }P のように略記します。

帰着の関係

P が 0 を内部に含まない場合でも、P の内部の点 x_0 を 1 つ求められれば、P を -x_0 だけ平行移動することによって同様の議論が適用できます。

多面体の双対

有界で 0 を内点に含む多面体 P\subset\mathbb{R}^n を考えます。P の端点を x_1,\dots,x_k とします (つまり、P は \{x_1,\dots,x_k\} の凸包になります)。このとき、P の双対多面体 P^*\subset\mathbb{R}^n を以下のように定義します。

 

P^*=\left\{y\in\mathbb{R}^n\mid x_i^\top y\leq 1\quad(\forall i\in \{1,\dots,k\})\right\}

 

この双対多面体 P^* について、以下の性質が成り立ちます。

  • P^* は 0 を含む有界多面体である。
  • (P^*)^* = P である。
  • P の端点と P^* のファセットは一対一対応する。また、P のファセットと P^* の端点は一対一対応する。

双対多面体の例 (赤同士と青同士がそれぞれ対応)

(a) \textrm{sep }P から \textrm{opt }P^* への帰着

(P^*)^* = P を用いると、(c) で後述する「\textrm{sep }P^* から \textrm{opt }P への帰着」から直ちに従います。分離したい点が P に含まれない場合、分離不等式としてファセット定義不等式が得られるという点が重要です。

(b) \textrm{opt }P^* から \textrm{sep }P^* への帰着

楕円体法によって、P^* の分離オラクルを用いて P^* 上の線形最適化問題を解くことができます。

(c) \textrm{sep }P^* から \textrm{opt }P への帰着

P^* における点 y_0 の分離問題を P 上の線形最適化を用いて解きます。具体的には、線形計画問題

 

\max\left\{y_0^\top x\mid x\in P\right\}

 

を解いて、最適端点解 x^*\in\{x_1,\dots,x_k\} を得ます。ここで、

 

P^*=\left\{y\in\mathbb{R}^n\mid x_i^\top y\leq 1\quad(\forall i\in \{1,\dots,k\})\right\}

 

であることを思い出しましょう。{x^*}^\top y_0\leq 1 ならば、y_0\in P^* です。{x^*}^\top y_0 \gt 1 ならば、P^* と y_0 を分離する P^* の妥当不等式として、{x^*}^\top y\leq 1 が得られます。従って、P^* の分離問題を解くことができました。y_0\notin P^* の場合、数ある分離不等式の中で特にファセット定義不等式を得ることができます。

まとめ

今回は、多面体の線形最適化問題と分離問題の等価性について見ていきました。この関係性は組合せ最適化問題に対する多項式時間アルゴリズムを作る上で非常に強力なツールとなっています。例えば、劣モジュラ関数最小化に対する最初の多項式時間アルゴリズムは、分離問題の線形最適化問題への帰着に基づいています。また、分離問題において分離不等式としてファセット定義不等式が得られるという点も重要で、これによって最小値だけではなく最小値を達成する解を求めることも可能となっています。

参考文献

[1] B. Korte and J. Vygen. Combinatorial optimization, volume 2. Springer, 2012.

第12回 SQLコンテスト (2024/04/21)

SQL

第 12 回 SQL コンテストに参加しました。最終結果は 4 完 100 点で 11 位でした。

最終結果

近況報告

最近はデータベースを使って AOJ の提出検索をするアプリを作っているのですが、API でいつ提出データを取得するか (一括で取得するか、クエリが飛んできたタイミングで取得するか) の設計で悩んでいます。余談ですが、かっつくんが平日の日中に投げまくってるのを観測できて面白いです。

コンテストの振り返り

問題 1

データベースに新たに行を挿入する問題です。INSERT 句を使えばよいですが、列がたくさんあるのと追加行が 2 つあるので結構面倒です。

列名と値を 1 個ずつ写経して開始約 5 分後に AC。

INSERT
    INTO DEPARTMENT
    (
        DEPT_CODE,
        START_DATE,
        END_DATE,
        DEPT_NAME,
        LAYER,
        UP_DEPT_CODE,
        VALID_FLG,
        UPDATE_USER_NAME,
        USER_UPDATE_DATETIME
    )
    VALUES
    (
        '1100',
        '2024-04-01',
        NULL,
        '営業1課',
        2,
        '1000',
        '1',
        'TANAKA',
        '2024-04-01 00:00:00'
    ),
    (
        '2200',
        '2024-04-10',
        NULL,
        '製造2課',
        2,
        '2000',
        '1',
        'YAMADA',
        '2024-04-10 00:00:00'
    )

問題 2

文字列から空白を取り除き、さらにその先頭 10 文字を取得する問題です。前者は REPLACE 関数を、後者は SUBSTR 関数を使うことで実現できます。また、値が NULL のときの場合分けは CASE 句や IFNULL 関数を使うことでできます。

開始約 11 分後に AC。実装は問題 1 よりも軽かったです。

SELECT
    EMP_CODE AS CODE,
    EMP_LAST_NAME || EMP_FIRST_NAME AS NAME,
    EMP_ENG_NAME AS ENG_NAME,
    IFNULL(SUBSTR(REPLACE(EMP_ENG_NAME, ' ', ''), 1, 10), '未入力') AS CUTOUT_STR
FROM
    EMP
ORDER BY
    CUTOUT_STR DESC,
    CODE DESC

問題 3

2 つのテーブル ITEM と ITEM_HISTORY を比較し、どちらかのテーブルにだけある行や、両方にあるが変更されている行を検出する問題です。2 つのテーブルを ITEM_CODE をキーとして外部結合したいですが、SQLite では左外部結合しかできないので、ITEM に ITEM_HISTORY を左外部結合、ITEM_HISTORY に ITEM を左外部結合の 2 通りを試し、それぞれの結果を UNION 句で結合させればよいです。

開始約 26 分後に AC。ここもノーペナで乗り切ることができました。

WITH T1 AS(
    SELECT
        ITEM.ITEM_CODE AS CODE,
        ITEM.ITEM_NAME AS NAME,
        CASE
            WHEN ITEM_HISTORY.USER_UPDATE_DATETIME IS NULL THEN 'ADDED'
            WHEN ITEM_HISTORY.USER_UPDATE_DATETIME != ITEM.USER_UPDATE_DATETIME THEN 'UPDATED'
            ELSE 'UNCHANGED'
        END AS COMP_RSLT
    FROM
        ITEM
    LEFT OUTER JOIN
        ITEM_HISTORY ON ITEM.ITEM_CODE = ITEM_HISTORY.ITEM_CODE
    WHERE
        COMP_RSLT != 'UNCHANGED'
), T2 AS(
    SELECT
        ITEM_HISTORY.ITEM_CODE AS CODE,
        ITEM_HISTORY.ITEM_NAME AS NAME,
        CASE
            WHEN ITEM.USER_UPDATE_DATETIME IS NULL THEN 'DELETED'
            ELSE 'UNCHANGED'
        END AS COMP_RSLT
    FROM
        ITEM_HISTORY
    LEFT OUTER JOIN
        ITEM ON ITEM.ITEM_CODE = ITEM_HISTORY.ITEM_CODE
    WHERE
        COMP_RSLT != 'UNCHANGED'
), T3 AS(
    SELECT
        *
    FROM
        T1
    UNION ALL
    SELECT
        *
    FROM
        T2
    ORDER BY
        CODE DESC
)
SELECT
    *
FROM
    T3

問題 4

2024-03-01 から 2024-03-28 の 4 週間分のデータを曜日ごとに集計するという問題です。初動でカレンダーを調べた結果、2024-03-01 が水曜日であることがわかったので、まずは日付から曜日の数値を (日曜が 0、月曜が 1 というように) 算出して、曜日ごとに件数と売上の総和を計算しました。ここで問題となるのが件数が 0 の曜日も表示しなければならないという点ですが、0 から 6 の値のみからなる別のテーブルに左外部結合し、IFNULL 関数を使って NULL を 0 に置き換えるという方法を取りました。ここまで来れば後は表示フォーマットを整えるだけですが、売上額を 3 桁ずつカンマ区切りするのが思いの外面倒です。問題をよく見ると売上額が 10^9 未満であるという制約があるので、10^3 未満のとき、10^6 未満のとき、10^9 未満のときの 3 種類で場合分けをしました。各場合の表示方法については競技プログラミングで慣れていたので、時間が切迫する中でもミスなく書くことができました。

前半パートで文字列や小数を整数に変換する必要があるなど手間取ってしまったため最後は時間との勝負になりましたが、終了 2 分前に書き終えて一発 AC を取ることができました。

WITH T1 AS(
    SELECT
        (CAST(SUBSTR(SALES_DATE, 9, 2) AS INTEGER) + 4) % 7 AS TYPE,
        COUNT(*) AS CNT,
        SUM(SALES_AMT) AS AMT
    FROM
        SALES
    WHERE
        SALES_TYPE != 2
        AND UPDATED_NO IS NULL
        AND SALES_DATE BETWEEN '2024-03-01' AND '2024-03-28'
    GROUP BY
        TYPE
), T2 AS(
    SELECT 0 AS TYPE
    UNION ALL
    SELECT
        TYPE + 1 AS TYPE
    FROM
        T2
    WHERE
        TYPE < 6
), T3 AS(
    SELECT
        T2.TYPE,
        IFNULL(CAST(ROUND(CNT * 0.25, 0) AS INTEGER), 0) AS AVG_CNT,
        IFNULL(CAST(ROUND(AMT * 0.25, 0) AS INTEGER), 0) AS AVG_AMT
    FROM
        T2
    LEFT OUTER JOIN
        T1 ON T1.TYPE = T2.TYPE
), T4 AS(
    SELECT
        CASE TYPE
            WHEN 0 THEN '日'
            WHEN 1 THEN '月'
            WHEN 2 THEN '火'
            WHEN 3 THEN '水'
            WHEN 4 THEN '木'
            WHEN 5 THEN '金'
            WHEN 6 THEN '土'
        END AS WEEK,
        AVG_CNT,
        CASE
            WHEN AVG_AMT < 1000 THEN AVG_AMT
            WHEN AVG_AMT < 1000000 THEN (AVG_AMT / 1000) || ',' || (AVG_AMT % 1000)
            WHEN AVG_AMT < 1000000000 THEN (AVG_AMT / 1000000) || ',' || ((AVG_AMT / 1000) % 1000) || ',' || (AVG_AMT % 1000)
        END || '円' AS AVG_AMT
    FROM
        T3
    ORDER BY
        TYPE ASC
)
SELECT
    *
FROM
    T4

感想

今回もなんとか全完することができました。内容的には安定してきましたが、カラム名などの typo が目立つのでタイピングの速度と正確性が課題点だと感じています。