Nim で yukicoder の最短時間を取って遊ぶ その2

やっていきで現在425問といて58問最短になった. ☆3からはみんな最短取るやる気を出してきたので最短が難しくなってた.... getchar_unlocked()の力だけで倒せる問題は置いておくとしてその他の問題を備忘録.

No.697 池の数はいくつか

https://yukicoder.me/submissions/312381

愚直に地図中の池の数を数えるだけ. queueや再帰を使ったりして何周もするように書いてしまうと遅いので, 最低限のunionfindを使って一回で実行・計測すると最短を取れる.

No.634 硬貨の枚数1

https://yukicoder.me/submissions/312348

この問題は予めある程度結果を計算できる. Nimでは const C = (proc():seq[int] = ... )() と書けばコンパイル時定数代入として 150万回まで計算できるので最短を取るのは容易.

No.554 もconstが使えて楽.

No.523 はconstにすると150万回を超えたので渋々埋め込み. No.502 も. No.027 も.

No.537 ユーザーID

https://yukicoder.me/submissions/310597

SFFやミラーラビンで殴ると最短が取れる.

No.414 も. No.376 も. No.312 も

No.342 一番ワロタｗｗ

https://yukicoder.me/submissions/311076

unicodeの文字列処理.Nimで何も考えずに書くだけで意外にも最短を取れた.

No.304 鍵

https://yukicoder.me/submissions/304950

ランダムに鍵を試すだけのコードだが,何となく乱数のシードを 61725 にすると最短を取れた.

No.233 めぐるはめぐる (3)

https://yukicoder.me/submissions/313061

二つの順列を組み合わせて無駄な名前を作らないようにするのがまず第一条件. その上でstringを経由している暇はないため,全て char* で管理して unordered_set<size_t> に喰わせるときには hash<string>() にして喰わせると string 的な気持ちで書いたまま最短が取れる.

No.120 傾向と対策：門松列（その１）

https://yukicoder.me/submissions/312133

sort も priority_queue も必要で,Nimの標準ライブラリのそれではとてもじゃないが速度が足りない. なんと Nim のソートは マージソートなのだ！ 素直にC++で書いて最短.

No.50 おもちゃ箱

https://yukicoder.me/submissions/313570

BitDP. 最初は関数を作って再帰的に書いていたが, 実はn個の(O(n*2n)の)bitDPは for i in 0..<(1 shl n) って外側に書いて回すといい感じに回ってくれる.簡潔に書けて速くて便利.

No.009 モンスターのレベル上げ

https://yukicoder.me/submissions/313351

Nimの雑に書いた自作PriorityQueueではC++のそれには勝てなかったが, この問題の性質上,ある程度探索すると答えは早めに出るので打ち切っていいハズなので 現状の最短より10msくらい早い時間で打ち切るようにしたらACだったので発想の勝利.

Nim で yukicoder の最短時間を取って遊ぶ

はじめに

最近 Nim で yukicoder をやっています. 競技プログラミングとしてアルゴリズムを考えて楽しむのもいいのですが, 個人的にはどれだけプログラムをチューンできるかというISUCON的な遊び方をして楽しんでいます. yukicoder では最短実行時間をとるとゆるふわポイントが貯まり,ポイントランキングが可視化されるため,やりがいがあります. 現在やるだけの問題(☆2以下)を yukicoder で250問程解き,25問について最短時間を取得しました.

yukicoder.me

というわけで,この記事では,アルゴリズム的な改善は全て済んでおり,後は I/O など競技プログラミング的には問題の本質ではないところに改善の余地があるコードを想定し,これを 1ms でも速くして最短時間をとるメモを書きました.

自然数入力

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    var k = getchar_unlocked()
    if k < '0' : break
    result = 10 * result + k.ord - '0'.ord
let n = scan()

自然数の入力の取得には,Nimの場合 stdin.readline().parseInt() が, C++の場合 std::cin >> n や scanf("%d",&n) などがありますが,速ければ正義なので,スレッドセーフを気にしない getchar_unlocked を使って自分で自然数を組み立てる手があります.感覚的には,1000個以上変数があると効いてくる様子.

自然数出力

proc putchar_unlocked(c:char){.header: "<stdio.h>" .}
proc printInt(a:int32) =
  template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
  template mod10(a:int32) : int32 = a - (a.div10 * 10)
  var n = a
  var rev = a
  var cnt = 0
  while rev.mod10 == 0:
    cnt += 1
    rev = rev.div10
  rev = 0
  while n != 0:
    rev = rev * 10 + n.mod10
    n = n.div10
  while rev != 0:
    putchar_unlocked((rev.mod10 + '0'.ord).chr)
    rev = rev.div10
  while cnt != 0:
    putchar_unlocked('0')
    cnt -= 1

# 直で書いたほうが速い
  proc printInt(a0:int32) =
    template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
    template put(n:int32) = putchar_unlocked("0123456789"[n])
    proc getPrintIntNimCode(n,maxA:static[int32]):string =
      result = "if a0 < " & $maxA & ":\n"
      for i in 1..n: result &= "  let a" & $i & " = a" & $(i-1) & ".div10\n"
      result &= "  put(a" & $n & ")\n"
      for i in n.countdown(1): result &= "  put(a" & $(i-1) & "-a" & $i & "*10)\n"
      result &= "  return"
    macro eval(s:static[string]): auto = parseStmt(s)
    eval(getPrintIntNimCode(0,10))
    eval(getPrintIntNimCode(1,100))
    eval(getPrintIntNimCode(2,1000))
    eval(getPrintIntNimCode(3,10000))
    eval(getPrintIntNimCode(4,100000))
    eval(getPrintIntNimCode(5,1000000))
    eval(getPrintIntNimCode(6,10000000))
    eval(getPrintIntNimCode(7,100000000))
    eval(getPrintIntNimCode(8,1000000000))

getchar_unlocked の対として putchar_unlocked があり,これを使う手があります. 32bit整数xを (int32)(0x1999999A * (int64)(x)) で x / 10 相当のことが出来るのは知らなかったです...

配列確保

# x = newSeqWith(n,stdin.readLine().parseInt()) 相当
var x : array[100010,int32]
for _ in 0..<n : x[i] = stdin.readLine().parseInt().int32

yukicoder の実行時間の結果はテストケースで最も時間のかかったものとなります. 最も時間のかかるテストケースは,制約ぎりぎりのサイズの配列が必要になることが多いです. そのため,実行中に動的に配列を確保するよりも,始めからグローバル変数として制約の限界まで固定長の配列を確保しておく方が高速なことが多いです. 制約的に32bitで済むなら配列を int (64bit) から int32 (32bit) に変更しておくことで更に高速化できる可能性があります.

コンパイル時計算

let X = (proc() : seq[int] =
  return @[] # ... 実行時に計算される
)()
const X = (proc() : seq[int] =
  return @[] # ... コンパイル時に計算される
)()

素数表など,コンパイル時に予め計算しておくことが出来る場合があります. Nim の場合, 定数代入 let ではなく, コンパイル時定数代入 const を使って代入するだけでコンパイル時に計算してくれます.

Nim で プロファイリング結果を FlameGraph にする

この記事は KMC Advent Calendar 2018 - Adventar 7日目の記事です. ついでに、Nim Advent Calendar 2018 - Qiita の 7日目の記事でもあります. 前日のKMCアドベントカレンダーの記事は dnek_ さんの 運ゲー排除マインスイーパー💣脱Unity計画（Android編）＆SATによるソルバー改良 - dnekblog でした. がんばりますねー.

はじめに

Nimっていう最高の言語があるんですけどご存知でしょうか？ 過去のアドベントカレンダーでもその素晴らしさを語っているので, ご存知でない人はぜひ御覧ください. この記事では Nim は version 0.19.0 を使用しています.

プロファイリング

コードを書いていてパフォーマンスがあまり出ない時,どこがボトルネックとなっているかを調べることは重要です. プロファイリングをせず,ただ闇雲に時間がかかってそうと思った場所を直すという方法は往々にして思った結果が出ないものです.

幸いなことに Nim ではデフォルトでスタックトレースプロファイラーが搭載されています.

プロファイリングの手順は以下のとおりです.

  1. プロファイリングしたいNimのファイルに import nimprof を記述する.
  2. Nimのコンパイル時のコマンドに --profiler:on --stackTrace:on を加える

これで実行すると, profile_results.txt という以下のようなスタックトレース結果が生成されます.

total executions of each stack trace:
Entry: 1/510 Calls: 961/8114 = 11.84% [sum: 961; 961/8114 = 11.84%]
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssign 3422/8114 = 42.17%
  assign.nim: genericSeqAssign 3447/8114 = 42.48%
  matrix.nim: deepCopy 3415/8114 = 42.09%
  target.nim: tryUpdate 2486/8114 = 30.64%
Entry: 2/510 Calls: 948/8114 = 11.68% [sum: 1909; 1909/8114 = 23.53%]
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssign 3422/8114 = 42.17%
  assign.nim: genericSeqAssign 3447/8114 = 42.48%
  matrix.nim: deepCopy 3415/8114 = 42.09%
  target.nim: tryUpdate 2486/8114 = 30.64%
...
...

例えばこれは最近書いている解析用のプログラムの結果のものなのですが, この結果からtryUpdate関数のdeepCopy関数でのgenericSeqAssign, 要は大きな配列のコピーがネックとなっていることがわかります. これでも十分分かりやすいですが,できればもう少し視覚的に分かりやすく表示したいものです.

Flame Graph

Flame Graph の形式を用いることで, 上図のように視覚的に分かりやすく結果を見ることができます. Flame Graph の読み方などに関しては, (Go言語版の記事ですが) https://deeeet.com/writing/2016/05/29/go-flame-graph/ などが分かりやすいです.

さて, このFlame Graph の SVG を生成するPerlのコードはGithubにて公開されており, Go や Java など色々な言語 の Flame Graph を生成することができます, ただ,残念ながら調べた限りだと Nim の Flame Graph を生成するものはまだ無いようです.

Flame Graph 生成

無いなら作るしかないですね.早速作ってみましょう. 上記リポジトリに有る flamegraph.pl というファイルに,例えば以下のような入力を加えて実行すると, 図のような Flame Graph を作成することができるようです.

func1;func2 10
func3 8
func4;func5;func6 3

分かりやすいですね.

あとは profile_results.txt の結果をこの形式に変換すれば良さそうです. というわけで変換スクリプトを書いてみました.

profile_results.txt を flamegraph.pl 形式にするやつ · GitHub

いい感じに変換できてそうですね. スクリプトのご利用はご自由にどうぞ.

さいごに

以上、プロファイリングは大事でFlameGraphは見やすくて便利ということでした. ここまで読んでくださり、ありがとうございました.

Nimに興味を持たれたら、 Nim Advent Calendar 2018 - Qiita を読んだり、 Nim programming language | Nim を読んだりしてください.

明日のKMC AdventCalendar は Kana_kmc さんによる 16年間を振り返って整理する です.

追記

当初予定していたアドベントカレンダーの内容は,「太古のPythonを眺めてみる」でした. 便利なことに https://www.python.org/ftp/python/src/Python-0.9.1.tar.gz を解凍して configure して make すれば Python 0.9.1 という太古のバージョンを特に苦もなく動かすことができます. 太古のPythonでは,1タブ8スペースだったり != が <> だったり,classに__init__が無かったり文法がいろいろ違って楽しい...ということを書こうとしたのですがあまり深い内容が無かったのでやめてしまいました. 他の(virtualenvで取れないような)太古のバージョンも, https://www.python.org/ftp/python/src/ から容易に得ることができ,過去の遺産を残しているPythonはすごいなあと思いました.

isucon8本戦は低レイヤーがネックにならない良問だった

TLDR;

  • ISUCON8に参加した
  • 感想戦は41万点出た
  • ISUCON8本戦は低レイヤーがネックにならない良問だった

はじめに

ISUCON8に参加してきました. 私のチーム(百万円ドブリン)の状況は @nakario のブログに詳しく書いてあるのでそちらをご参照ください.

うちのチームでは @nakario が Goをゴリゴリゴリゴリと書きWebアプリケーション自体を高速化し, @aokabi が MySQL と Nginx を触ったり複数台構成の準備をしていました. 二人のプロがいるので僕は踊っているだけでよくて最高でした.

やったこと

予選

匿名関数を剥がしたり,高速化後のデッドロック要因の select ... for update の for update をなんとなく消す役割をしていた様子. 怪しいところを消すガチャ要員です.

本戦

Dockerを剥がしたりbcrypt をなんとかしようとしていました. pprof だけを見ると bcrypt しかCPUを食っていなかったからですね. CPUはネックではなかったので直す意味はなく,これは完全に罠だったので反省.

bcrypt について

結論としては signup の時のハッシュ化するときの cost を デフォルトの 10 から 4 (最低値)にする程度で十分です. ハッシュ化は 2^{cost} 回行われるため,この変更だけでハッシュ化は64倍早くなり,signup処理はほぼ一瞬になります.

bcryptが大変そうに見えるsigninは,実は成功するユーザー数はとても少なく, 例えば成功したユーザーのハッシュ化のコストを4にするなどの小手先の技では効果はありません. signinを完全に潰すには, DBに保存されているハッシュ値から元のパスワードを当てて全てコスト4にして保存するしか方法はありません. なお,もしもそれが出来たら bcrypt の脆弱性を見つけたのと同値ですのでISUCONより先にセキュリティ系の学会あたりに報告したほうがいいと思います.

ちなみに問題設計としては,signin はBan処理の実装だけで十分なようになっていました. ユーザーが多くなってくると, info や runTrade 関係の処理がネックを占めてくるようになり, signinのbcryptの比重は自然に減っていくため手を付ける機会は永遠に訪れないのです.

感想戦

本戦当日では5000点程度で終わってしまいましたが, それはそれとして日曜日に集まって感想戦をやっていました. これは賞金をもらえないので意味は無いように思えますが, どこまでチューニングできるものなのかを知れて大変楽しいものです.

twitter.com

最終的に41万点くらいでたので満足です.

41万点への道のり

https://github.com/aokabi/isucon8f (現在非公開repoですがそのうち公開してくれると思います)

感想戦では,aokabitが複数台構成を行い, nakario がISUCON8 本選問題の解説と講評 : ISUCON公式Blog に書かれている高速化作業を全部やってくれました.すごい.

goroutineの数でshare機能の有無を決めたり, singleflightを取り入れたり,Ban機能を実装したり,ロウソク足を改善したり,LIMIT 1 を入れたり, send_bulk をやったりを全部nakarioがやってくれました. すごすぎる. それを aokabi が4台に分散させたところで 6万点くらいまでいっていました.

更に最後に nakario が info の N+1を消したり クッキーを活用したり といった処理を入れたところで20万点くらいまで行きました. 最終的にはコネクション数がネックになっていたように見えたので info の N+1 を消したりクッキーで不要なSQL通信を減らすと得点が爆上がりしたのを見ると面白いなあという感じです.

20万点からあと上げる作業では,要はコネクションを安定させながらユーザーを増やせばいいので, アプリに db.SetMaxIdleConns(1024) を加えてコネクションプールをしたり, nginxの設定でgoのアプリとの間のkeepaliveを設定したりしてコネクションを安定させました.

(編集注: nakario,aokabi担当分に関して,僕が間違った解釈をしている可能性があるので鵜呑みにはしないでくださいね).

ISUCON8本戦は低レイヤーな部分がネックにならない良問

ISUCON本戦まで,毎週日曜日にISUCONの過去問や公開社内ISUCONを解くという集まりをやっていました. その中でISUCON8本戦がすごいなあと思ったのは低レイヤーな部分がネックにならない作りになっていたところです.

低レイヤーについて,ここでは 標準ライブラリの実装では遅いので高速化する箇所 と定義します. 標準ライブラリでは様々な入力ケースに対応する必要があるので得てしてオーバーヘッドがかかります. これを高速化する作業は著しく保守性を損なうため通常のWebアプリケーションでは絶対にいじりたくない場所ですが, なんでもありのISUCONならこれをやる必要が出てきてしまうものです.

以下,過去問でそのレイヤーを見てみます.

ISUCON7本戦の低レイヤー

https://github.com/nakario/isucon7f2 ここでの低レイヤーは BigInt と json化 です.

BigIntの高速化については ISUCON7本戦でBigintを殺したかった話 - (/^^)/⌒●~*$ a(){ a|a& };a にて考察しています. json化の高速化作業は,リフレクション的な作業がgoで行われるのが遅い原因なので, json化するGoのコードを生成する fastJson を導入すれば消すことが出来ます.

ISHOCON2 の低レイヤー

GitHub - nakario/ishocon2 ここでの低レイヤーは PostのFormの読み込み と Goのテンプレートエンジンのレンダリング です.

Go の PostForm では,Formが1つしかなくても複数あった場合を想定して, フォームが1つの場合の解析と,複数の場合の解析と二度解析してしまいます. ですので標準ライブラリを読みながら複数の方の解析をしないPostFormを作ることで2倍位早くできます.

Goの標準ライブラリには html/template があり,大体のレンダリングエンジンにおいてこれを内部で使用しています. ただ,これは構文解析やeval的な操作をしてしまうので余計なオーバーヘッドがかかってしまいます. 解決方法は fastJsonと同じで,要はGoのコードにしてしまうことです. これを解決するために,.tmpl ファイルを静的解析して .go のファイルを生成するNimのコードを書いたので,よければ使ってください.

yisucon の低レイヤー

GitHub - nakario/yisucon ここでの低レイヤーは Goのテンプレートエンジンのレンダリング です.同じなので割愛.

ISOCON1 での低レイヤー

GitHub - Muratam/ishoisho1111: 158160点 ここでの低レイヤーは Goのテンプレートエンジンのレンダリング と 時刻のパースです.

時刻のパースはどうしてもformatの解析ののちscanという二度手間を挟んでしまうので, 直書きしてしまうことで解決します.

低レイヤーについて

以上見たように htmlやjsonを生成してユーザーに返すリクエストが多い問題では, どうしてもこういった低レイヤー部分がネックの一つになってしまうという問題があります. 今回の問題を41万点までチューニングしたわけですが, 一つもこういう低レイヤーの部分が表面化せず,良問だったなあと思いました.

例えばもし今回問題設計のバランスが悪ければ bcrypt のハッシュ化がネックになり得たわけで, 頑張れば定数倍高速化出来たのかなーとかちょっと思ったりしていました.

どうも過去問では僕はこういった部分ばかり率先して担当していたようで(低レイヤーは楽しいので), 今回の問題でずっと踊るしか出来なかったのはISUCON8本戦が低レイヤーが問題にならない良問だったからかなあと思いました.

最後に,ISUCONやそれに類する問題を作成・運営してくれた方々すべてに最上級の感謝を込めて結びとします.

18きっぷで46都道府県行ってみた

はじめに

8/23~9/10の期間でやってみました. 18きっぷは一日2380円で日本全国のJRが乗り放題という券で,お金はないが時間のある学生にとっては夢のようなきっぷです. 今回の旅は電車の中でふらふら～とコーディングしたり,つらつら〜っと全国の街や村を眺めながらついでに全国を巡ったりすることが目的です.

18きっぷ旅のよいところ

全国を巡ると,例えば「ここに最上川があったのか〜」とか「尾道近くにあるじゃ〜ん」といった発見的な楽しみが味わえます.なんならそのまま寄り道していくこともできます.これが18きっぷ旅の最大のよいところだと思います.

あとは,各地各地で人はきちんと生きていて,それぞれの人生を歩んでいるんだなーという感覚を味わえるのも鈍行列車の旅のよいところですね. 90分に一本しかない電車を逃さないように滑り込む中高生の群れを見たり,休日に家族連れが多かったり,車窓の渓谷が絶景だったり,台風直前の列車は満員だったり,福島原発付近の代行バスの運転手と地元の学生が楽しそうに進路の話をしていたり...と時間によって変化する色々な景色を味わえます.

もちろん,各地のおいしいものを食べたり,各地の温泉に浸かったり,といったことも全国を巡っているので楽しめますが,これは別に18きっぷでなくても楽しめる気がします.

18きっぷ旅の悪いところ

まず,当初思い描いていた「電車の中でふらふら～っとコーディング」は残念ながら不可能です...朝から晩まで電車に乗っていると充電はすぐに尽きますし,ギガもどんどん減っていきます.これは本当に残念.

あとは,トラブルが起きにくいのは欠点ですね.自転車旅と違って,路線図や時刻表は誰でも得られるので,僕が考えたルートよりも良い(トラブルを回避している / 経路が短い / 乗り継ぎが楽 など) ルートを僕に提示できるので,必然的にトラブルが回避されてしまいます. 個人的にはトラブルのせいで仕方なく野宿するハメになったり,仕方なく何kmも歩くことになったりしたかったのですが,皆さまが情報を提供してくれたので大きなトラブルもなく乗り越えられてしまいました. ｲﾔｰｻﾞﾝﾈﾝﾀﾞﾅｱｰ 「城崎温泉では外湯巡り券のある宿がお得」などといった知見情報も皆さまが提供してくれたので旅を効率的に楽しめることができ,限界旅のつもりだったのが,普通に楽しい旅ができてしまいました.感謝.

18きっぷ旅の下準備

旅で一番大事なのはやはり宿でしょう. まず最低ランクの宿として日本には(ある程度の街には)1500円程度で宿泊できるネットカフェがあるので,予めネカフェがあるかどうかを調べておくと安心できます. 最悪の場合でも終電でそこに泊まればその日は自由に行動できますからね. 大きな街には4000円程度で泊まれるビジネスホテルが,都会の街には3000円程度で泊まれるカプセルホテルがあるので,自分の体力と財布と相談しながらどこに泊まるか決めていきましょう.平日なら19時くらいから予約しても大抵間に合います.

次に大事なのはやはり体力ですね. 体力が無くなってくると旅を楽しめなくなってくるので,定期的に体力を蓄えながら進んでいきましょう.例えばネカフェ連泊はしんどいので,疲れたらネカフェに泊まらずきちんとビジネスホテルに泊まったりなどが考えられます. 始発から動いて終電までいけば当然長距離進むことができるのですが,そのために体力を失い道中を楽しめないのは一番の損です.寝過ごしてもいいのできちんと睡眠を取ったり,徹夜でお酒を飲んでMPを回復したり,要所要所で手を抜いて楽しんでやっていきましょう！ 最善に見える選択肢は体力がなければ成し遂げられないのですから！

一日目 (8/23 木)

一日目は朝の5時に寝てたところから開始しました. これには深遠な理由がありまして,civilizationという国を操作して発展させるボドゲを徹夜でやっていたせいですね. 普通にやっていればあと3時間は早く寝れたのですが,@base64 に領土を植民地化されボロ負けしたのでムキになってやり続けていたのが原因です. 結果朝11時に @nana さんからのslackコールで起こされ,日本一周がスタートしました. ところでこの日は台風が来ており,乗っていた電車が運休になってしまいました.島根まで行くつもりが兵庫の城崎温泉までで終わってしまいました... 仕方が無いので温泉でゆっくりすることにします. ⬆台風が来てることを全く感じさせない城崎温泉の図

知らない場所についたら,まずはGoogleMapでネカフェを探します. ネカフェは最低ランクの宿とはいえ,大きな街には必ずあり,更に当日いきなり行ってもほぼ確実に泊まれるので最悪のときの手段として備えておくと安心できるものです. 当然,城崎温泉にも...と思ったのですがなんと城崎温泉にはネカフェはありませんでした.温泉街が過ぎてネカフェなどはなく普通の宿しか無いようです.ほえー.

宿を探していると @nonylene 先生から「どっか泊まるなら外湯巡り券くれるとこのほうがいいよ（1200円するので）」とのこと 城崎温泉には7つの外湯があり,そのフリーパス付きのところに泊まるとお得なのです. じゃらんで調べて5000円の外湯巡り券をくれるビジネスホテル みよし宿 に決定. ここのオーナーさんは話し好きのようで, 「私はねぇ...システムの穴を突くのが好きな性格でねぇ...この外湯巡り券には"10時まで有効"と書いてあるが...実は10時までに中に入ってしまえば後はそのまま入り浸ってても問題がなくてねぇ...ところでお客さん...明日は12時にならないと電車が復旧しないそうじゃないかい...」 とのこと.なるほどね.他にも安くておいしい店の情報を教えてもらったりしました.感謝.

その日の夜はオーナーさんに教えてもらった店に行ったり外湯巡りをしたりしました.台風は深夜に通過したので全く被害に合わなかったです.ふふー. 温泉街でゆっくりできてとても体験が良かった一日目でした.

一日目 まとめ

  • 知見
    • 電車は台風ですぐに止まる
    • 城崎温泉で泊まるなら1200円するので外湯湯巡り券くれるとこのほうがよい
  • 費用7380円内訳
日数 都道府県 費用 18切符効用 距離 駅数 宿代
1 京都 兵庫 7380円 210円 158km 3 5000円
総計 2 県 7380円 210円 158km 3 5000円

⚠ 18切符効用 : 18切符のおかげでお得になった金額 ⚠ 駅数 : 駅メモでチェックインした駅数

二日目 (8/24 金)

というわけで二日目です. 台風の影響により午後になるまでは運転が再開されないようなのでこの日は朝から外湯めぐりです.ふふー. 温泉でのんびりした後は,山陰本線を沿って日本海側をえんえんと沿っていきます.

⬆ 夕焼けがきれいです

鳥取・島根といえば,僕は数ヶ月前に 吉田寮祭のヒッチレースに参加して無一文で鳥取と島根の県境の山奥から無一文で帰ってきた のですが,そのときの帰り道が9号線沿いでこれが山陰本線の線とほぼ同じなので,ヒッチハイクで通った道が電車からよく見えるんですよね.その道と思いを振り返りながら電車に乗って行けたのはなかなか趣深かったです.特にヒッチハイク難所岩美あたりが見えたときには大変だったなあという思いがしみじみとやってきました.

宿は3400円のビジネスホテル. 益田にはネカフェがあったような気がしますがビジネスホテルに何故か泊まっているのでこれは一日目でビジネスホテルの贅沢さを知ってしまった顔をしていますねぇ.

二日目 まとめ

  • 知見
    • サンダルで電車に乗ると足が寒くてつらい
    • 電車はヒッチハイクよりも予定通りに行ける点ですごい.
  • 費用5780円内訳
日数 都道府県 費用 18切符効用 距離 駅数 宿代
2 兵庫 鳥取 島根 5780円 3560円 356km 23 3400円
総計 4 県 13160円 3770円 514km 26 8400円

三日目 (8/25 土)

三日目は今までの遅れを取り戻すべく大移動をしました. 今回のルートは海岸線を行きたかったので福岡までは山陰本線を通り,佐賀・長崎をちょっと踏んでのUターンは嫌だという理由で長崎→熊本のフェリーを使うことにしました.

僕は日本の地理には詳しくなく,どこも知らない土地という点では同じなので,それなら...と地名に依って行ってみたいかどうかを判断したりしています. 九州にはめだかボックスの登場人物の名前が到るところに出てきてすごいですね(安心院さんが好きです).人吉まで頑張って行ったのも実はそういう理由だったりします.

⬆山口県長門市の駅の売店でコンパス時刻表を購入.JRの線かどうかもひと目で分かるし,どの電車がどういうルートでどの駅に着くのかひと目で分かるので大変便利です.ただ,臨時列車が別ページに載っていたりして損をすることがあるのでコンパス版よりはJTB版の方がよいそうです.実際問題として乗れるかもしれなかったトロッコ列車に乗れなかったりしました...

福岡は昔自転車で行ったことがあったのでちょっと懐かしい気分に浸りながら通過. 千葉・滋賀と並んで日本の首都の一つである佐賀もよくわからなかったので普通に通過. お昼過ぎごろに長崎は諫早に到着.お金と時間とスケジュールに余裕があれば軍艦島に行ってみたかったなーというのがちょっと思うところでした.

⬆諫早駅付近の食事処が閉まっていたのでぶらぶらとスーパーを拝見して発見した謎の食品オキュウト.海藻加工食品らしい.よくわからないけど寒天みたいな味でした.

⬆多比良町駅(長崎) ⇔ 長洲 (熊本)を結ぶフェリー.昨日の予報ではこの時間帯雨の予報だったのに見事に晴れてラッキーでした.45分440円とお得なフェリーです.

宿は4kのビジネスホテル.人吉も城崎温泉と同じパターンでネカフェが無かったような気がします.ネカフェなら1.6kで済むというのに豪遊しすぎですね.とはいえビジネスホテルにはネカフェにはない温泉が付いていたりするので何やかんや言ってコスパは悪くなかったりするので適宜使っていきましょう.

三日目 まとめ

  • 知見
    • 熊本駅で160円払うと地の底より這い出しくまモンを拝める
    • 知らない土地のスーパーに行くと謎の食材が手に入る
    • ポケットサイズの全国路線時刻表は便利！
  • 費用7940円内訳
  • 今日の読めなかった地名
    • 鳥栖 (なんか有栖っぽいのでとりすと読んでしまう)
    • 長洲 (某プロレスラーのせいでちょうしゅうだと思っていました)
    • 小倉 (おぐらと無限に勘違いしてしまう)
日数 都道府県 費用 18切符効用 距離 駅数 宿代
3 島根 山口 福岡 佐賀 長崎 熊本 7940円 6680円 494km 58 4000円
総計 9 県 21140円 10450円 1008km 94 12400円

四日目 (8/26 日)

(編集注 : 宗次郎駅じゃなくて宗太郎駅ですね) 四日目で九州もおさらば！この日は特徴的な乗車区間が多い日でした.

⬆まずは人吉(熊本)⇔吉松(鹿児島)区間からスタートです.この山越え区間は景色が綺麗なためかなんと普通列車が観光用列車しか運行していないんです.この日はちょうど休日だったため家族連れが多く,景色・アナウンスに加えて楽しそうな親子の情景を楽しめました.

18きっぷで鹿児島から稚内まで行った記事にも書かれている吉松駅(鹿児島)の駅前温泉にて一息.ここの温泉は温度が程良いぬるめと程良いあつめに分かれていて今回の旅で入った中でも結構好みの温泉でした.そういえば鹿児島といえば桜島が有名ですがあそこって本当に火山灰対策グッズが売られているんですかね？行ってみたかったかも.

⬆宮崎県都城駅にある石碑.この市では必ず真実しか話せないとかだったら社会主義核心価値観ぽいななどと考えたり.

宮崎⇔大分は普通列車が一日朝夜二本しか運行していないヤバい区間があります. ⬆左 : その区間の途中の駅市棚で下車して撮った時刻表.あまりにも疎！ ⬆右 : しかもこの区間は普通列車なのに運行本数が少なすぎるからか特急用の車両に乗れたりします.たのしい！

一日二本なんて初めて見ました.のんのんびよりの住民が利用している線は確か二時間に一本しか無かったはずで,田舎すぎてやばいな～と思ったものですが,これを見た後だと二時間に一本もあるなら余裕じゃんと錯覚してしまいそうです.

さて,先程の区間を越えると深夜に臼杵(大分)に着くので,そのままフェリーで数時間かけて八幡浜(愛媛)に向かいます.節約のため,宿はフェリーで済ませます.ちなみにこのフェリーでは車積のない乗客は僕一人だけだったので、旅客用入り口からではなく⬆のように車用口から直接入ることになったりしてちょっとおもしろかったです.

さらば九州〜

四日目 まとめ

  • 知見
    • 一日二本しか普通列車のない区間があり,特急用列車に乗れる
    • 観光列車いさぶろう(人吉⇔吉松区間)は指定席を買うと便利
  • 費用5460円内訳
    • 18きっぷ 2380円
    • フェリー代 2310円
    • いさぶろう指定席 520円
    • 吉松駅前温泉 250円
日数 都道府県 費用 18切符効用 距離 駅数 宿代
4 熊本 鹿児島 宮崎 大分 5460円 4510円 294km 61 0円
総計 12県 26600円 14970円 1302km 155 12400円

五日目 (8/27 月)

一日で四国を全部巡ります.

深夜3時に八幡浜(愛媛)に着いたフェリーからスタートです.宿のつもりだったフェリーでは3時間しか寝られず,仕方がないので待合室で日が明けるまで待機.

⬆日が明けた朝6時前のフェリー付近.みかん段々畑への朝焼けがきれいでした.

フェリーターミナルから八幡浜駅までは徒歩で30分程度. 歩いていると突如パイプオルガンの音色のBGMが流れ始め,テンションが上がっていきます.曲名は八幡浜漁港の唄というらしく,朝6時を知らせる時報のようです. 昔は全国にあったらしいですが,現在では八幡浜を含めて6台しか残っていないらしい.聞けてラッキーかも.

⬆愛媛県八幡浜駅⇔愛媛県宇和島駅間は,2ヶ月前の大雨による災害の影響で代行バスが出ていました.18きっぷで乗れます.いつもの電車とは違う気分が味わえてちょっと楽しい.

⬆愛媛県宇和島駅→高知県窪川駅へ向かう予土線.車窓から見える四万十川すごい！ ちなみにこの区間の岩井⇔窪川だけはJR線じゃないので18きっぷで通過できず,追加の210円を支払う必要があるので注意です.

⬆四万十川なのでうなぎ絶滅に貢献しました.

四国を回っていると袈裟をかぶったご高齢の方をたまに見かけます.お遍路巡りですね. お遍路巡りは通常時計回りに巡っていくので(順打ち),反時計回りに向かう僕とは会わないはずですが,様々な理由であえて険しい道とされる反時計回りで巡る人もいるようです(逆打ち).日本一周も実質お遍路のでかい版みたいなものなので旅が終わる頃にはきっと僕の徳も無限に溜まっているでしょう.

そのまま列車で高知駅へ.

⬆高知駅では酒盗(辛口)を買ってみました.酒盗は鰹の塩辛で,「盗まれるように酒がなくなっていく」のが語源の一つらしいです.後で食べたのですが確かに日本酒にはすごく合うのですがとても塩辛い！初めて買うならまずはみりんなどでもうすこしマイルドに味付けされた甘口の方を買うべきだったかもしれません.

阿波池田(徳島県西部)をちょっとだけ踏んで徳島も制覇.瀬戸大橋の近くの香川県坂出駅まで行って終了.宿は5k朝食付きビジネスホテルを取ってますね.フェリーできちんと寝られなかったから回復のためです.

五日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
5 愛媛 高知 徳島 香川 7590円 3550円 354km 88 5000円
総計 16県 34190円 18520円 1656km 243 17400円

六日目 (8/28 火)

本日で西側完全制覇です！

⬆瀬戸大橋を越えると岡山に着きます.この時点で広島県だけ踏めていないため,広島県尾道を観光してから岡山へUターンし,京都へ戻ることに決定.

⬆ 瀬戸内海の街,香川県は坂出からスタート

⬆瀬戸大橋を電車で渡り本州へ帰還

そのまま尾道へ.楽しい.海沿いの街はやっぱりいいですね. 尾道は急斜面の上に街が作られており,狭くて急な生活道路が多い面白い街並みをしています.そこを通る郵便バイクを見かけまして,えっこの道バイクで行けるの...と驚いた記憶があります.以前お正月に実家でウルトラマンダッシュを見ていたときの舞台が尾道で,重量ある荷物をこの街並みの中運んでいた姿が印象に残っていたので行けてよかったです.

尾道を14時半頃に出発し,次の元号相生(兵庫),僕の地元高槻(大阪)を経由して京都へ戻ります.途中大雨で運転見合わせになったり,兵庫県で @lv100 くんオススメのドルフィンステーキに寄ろうとしたら臨時休業だったり,@siotouto さんのソウルフード姫路の駅そばも食べ残ったり,ねねっちが卒業したり,さくらももこ氏が無くなったりしましたが些細なことです. 神戸まで来てしまえば京都までは夜遅くまで高頻度で電車がありまして,今まで通ってきた地方の電車との格差を思い知らされます.日本酒セットを盗み(比喩), 部室の @suzusime の院試終了飲みをし6日目は終了です.宿を我が下宿にすることで宿泊費を抑えます.

六日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
6 香川 岡山 広島 兵庫 大阪 京都 2380円 5020円 414km 153 0円
総計 20県 36570円 23540円 2070km 386 17400円

七日目 (8/29 水)

東京まで行く消化試合の日です.

⬆コミケに18きっぷで向かう場合このルートになるので,同じ道を利用した人も多いのではないでしょうか.

部室で夜遅くまで飲酒して,目が覚めると10時でした.@suzusimeの院試終了祝いでめでたかったので仕方ないですね.

⬆東側を廻るに当たってこの日調べずに書いたガバガバ地図.北陸や茨城がかわいそう.脳内がこんな状態でも日本一周はできるので便利な時代です.

いつものコミケルートですが,自転車で京都から東京まで5日かけて行った経験に比べると,電車は早いなあという気分になります.サンダルは車内では寒いのでスニーカに履き替えたり,東北に備えて服を長袖にしたりできたので,京都に下宿があって一旦寄っていけると便利です.

本日の宿は東京の @nana さんの出張先の家が自由に使えるとのことだったのでありがたく使わせてもらうことにしました.

七日目のまとめ

  • 知見
    • ガバガバ脳内地理でも日本一周はできる
  • 費用2380円内訳
日数 都道府県 費用 18切符効用 距離 駅数 宿代
7 京都 滋賀 岐阜 愛知 静岡 神奈川 東京 2380円 5830円 499km 185 0円
総計 26県 38950円 29370円 2569km 571 17400円

八日目 (8/30 木)

今日は関東をくねくね踏んでいきます.

⬆ 友部 ⇔ 小山 で往復が無駄に発生しています.東京→ 新松戸 → 浦和 → 小山 → 友部 の順で行けば往復をしなくて済んだのですが,千葉県の存在を完全に忘れており失敗しました...あちゃー.

⬆栃木県小山で織物体験ができました.小山では観光案内所に本場結城紬のコーナーが併設しています.京都から来ましたと言うと「西陣織は詳しいですか？」から会話が始まって（僕は全然西陣織を詳しくないので）これ逆に西陣織館とかで京都弁で言われたら畏怖するかもなと思いました...

茨城にはガルパン町おこしで有名な大洗があります.時間に余裕があったのでちょっと寄り道していくことにしました.アニメで町おこしと言えば他にラブライブ！の静岡県沼津市にも行ったことがありますが,そこと比べても大洗は気合の入り方が強くて素敵でした.閑散期のはずですが大洗にもオタクくんはそれなりに居て実際5,6人くらいと遭遇しました.

⬆大洗ガルパンラッピング列車. こいつは大分変態的な列車です.ラッピング列車自体はよくあるものですが(例:鳥取コナン列車 / 高知アンパンマン列車) ,この列車はなんと内側までガルパンキャラが到るところにラッピングされています.さらにこいつは人吉⇔吉松のような観光列車と違って普通に市民が利用しています.実際地元の中高生はまるで普通の列車のようにこの内部までガルパンに染まった列車を利用しているのです. 観光地という非日常的な場所を萌え化させることで収益をあげることには脳の理解も割とすんなりいくのですが.普段の日常で市民が利用するような街がこうなってしまうと,非日常的な萌えを求めて来てしまった自分だけがおかしいかのような錯覚に陥いってしまい僕は脳がバグってしまいました.とりあえずめちゃくちゃ興奮してしまい,大洗は最高だったので,とりあえず大洗ガルパントラベルガイドブックを買って町おこしに貢献していきました.大洗最高.

大洗観光を終え,福島県いわき駅にて宿を探します.いわき駅にはカプセルホテルがあったのでそこにしました. カプセルホテルは十分な都会にしかないレアな宿泊場所です.大きい街でもビジネスホテルまでしか,もうすこし大きい街でも大抵ネカフェまでしかありません.カプセルホテルは3k程度の値段帯で,ビジネスホテルよりも格安で,更にネカフェに比べてもきちんと睡眠が確保でき,お風呂に入れるという点で素晴らしいですが,隣室が近いのでネカフェ同様いびきのうるさい客の隣に当たると辛いという問題があります.利点欠点を把握した上で的確に利用していきましょう.

八日目のまとめ

  • 費用6230円内訳
  • 今日の読めなかった地名
    • 我孫子 (我そんしに見えて自己紹介してるのかなって思った)
    • 常磐線 (ときわせんだと思ってた)
日数 都道府県 費用 18切符効用 距離 駅数 宿代
8 東京 埼玉 千葉 茨城 栃木 福島 6230円 3070円 379km 91 3210円
総計 31県 45180円 32440円 2948km 662 20610円

九日目 (8/31 金)

今日は東北を攻めます！

東北には今までそんなに興味はなかったのですが,東北ずん子ファミリーの台頭によりかなり興味がでてきており,わくわくしていました. いわき駅からスタートし,朝焼けの綺麗な常磐線を北上していきます.

⬆ 福島県富岡駅 ⇔ 福島県浪江駅 間 を結ぶ代行バス.福島第一原発事故の影響によるもの. このバスに乗車して発射までしばらく待っていると,運転手のおじさんと中高生らしき少女との談笑が聞こえてきました.どうやら少女の進路について決まった様子.災害の影響で毎日の通学が代行バスとなり,しかも留まる決断をしたため通う人数も少ないとなるとこのような光景が生まれるのだなあとしみじみとしました. 時間になり,バスが出発します.あの事故からすでに7年ほどが経過しており,街並みはほぼ復興しているといっていい状態でした.しかしながらどうやら商業施設は軒並み放置されたまま撤退しているらしく窓ガラスが割れ廃墟になったコンビニやゲームセンターなど,時折不穏な光景が目に入るのが印象的でした.バスをよく見てもらうと分かるのですが前に張り紙が貼ってあり,「車内での撮影はマナーとモラルを守りましょう」と書かれてありました.また,帰宅困難区域に差し掛かると,「窓を開けないでください」とのアナウンスがありました.色々邪推してしまいます. 廃墟になった商業施設の写真を上げたり,復興した街並みの様子の写真を上げたりしたいところですが,この区間に関しては上手く伝えられそうにないのでぜひ自分で行ってみてください.

⬆宮城県は仙台を過ぎると「松島や ああ松島や 松島や」 の 松島が！行ってみたかったかも！

⬆秋田県横手駅で一回食べてみたかったイナゴの佃煮を購入.見た目こそイナゴですがよく考えると生きているイナゴをあまり見たことが無いため普通に食べれました.

⬆東北きりたんが好きなので一度食べてみたかったきりたんぽ鍋を秋田駅で購入.きりたんぽだけをむしゃむしゃ食べるとそんなに味はなく、きりたんぽをご飯代わりに（雑炊のように）食べると鍋の具の味が生きて美味しいなあという感想です.

そのまま @takemaru さんと青森駅で合流し共に北海道へ向かいます. 青森⇔北海道を渡る手段は二種類あり,一つはフェリーで函館まで向かう方法,もう一つが18きっぷオプション券を使って追加料金を払い新幹線に乗って向かう方法です.行きしなは宿も兼ねてフェリーで向かうことにしました.

ついに明日は北海道！

九日目のまとめ

  • 費用4380円内訳
  • 今日の読めなかった地名
    • 小牛田
日数 都道府県 費用 18切符効用 距離 駅数 宿代
9 福島 宮城 岩手 秋田 青森 4380円 7230円 653km 142 0円
総計 35県 49560円 39670円 3601km 804 20610円

10日目 (9/1 土)

北海道に着き,9月になりました.

⬆フェリーで函館へ着き,@jf712 , @bu4 の待つ札幌まで向かいます！

@takemaruさんと共に秘境駅小幌へ寄り道. あえて電車ではなく秘境度合いを知るために車道から向かいます.長万部駅からタクシーで国道を進み,途中で降ろしてもらい徒歩で小幌まで向かいます.小幌駅までの獣道はここのトンネルが目印です. ここのタクシー代や,列車の特急区間の乗車券代金,ほかにも以降の同行時のホテルの基本代金などなど,@takemaru さんには旅を手厚くサポートしてもらいました！感謝！

⬆ 小幌駅へ向かう獣道.旧花背峠のような山道.さすが秘境駅.

⬆小幌駅. この駅は「秘境駅」であることを売りにしていて,駅ノートが置いてあったり観測員さんが毎日手記を綴っていたりしています.

⬆左から順に 駅ノート入れ / その中身 / 中にあった東方同人誌(北海道観光名所が描いてたりします) / 小幌の同人誌 / 小幌駅ノート / ついでに駅ノートに僕も書いてみました. 駅ノートを読むと,小幌で一夜を過ごしてみた人がいたりしてすごいです.現時点で既に10冊目だそうで見ていて楽しかったです. 観測員さんを観測していると草木の手入れなどもしており,観光所としての秘境駅はこうして作られているんだなあとちょっと感心したりしました.観光所にもなっていないけど誰も殆ど降りない本当の意味での秘境駅とはまた別の存在になっており,実際電車が来たときには数十人もの人が小幌で降りていまして,ちょっとしたイベント会場っぽさが出てきました.ここには日に数本程度しか電車は止まらないとはいえ,室蘭方面から来た列車の20分ほどあとに室蘭方面へ向かう列車が来るという時刻表になっていまして,それなりに手軽にアクセスできるようです.

⬆夜は札幌で @jf712 , @bu4 と合流し,サッポロビール園でジンギスカンを食べて優勝！

宿はじぇにさんの家に泊めてもらいました ♡

10日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
10 北海道 2380円 3860円 412km 64 0円
総計 36県 51940円 43530円 4013km 868 20610円

11日目 (9/2 日)

⬆青森へ帰ります！行きしなはフェリーを使ったので帰りは18きっぷオプション券で津軽海峡を越えます！ 18きっぷオプション券(2300円)を購入することで,以下の恩恵が受けられます. - 五稜郭駅から木古内駅までの道南いさりび鉄道を利用可能 - 木古内から奥津軽いまべつへの新幹線が利用可能

そもそも木古内から奥津軽いまべつへの新幹線ですら3760円もかかりますのでこれは非常にお得な券ですね！

北海道の最北端の稚内まで電車で向かうか迷ったのですが,京都を恐怖に陥れた台風がこの時期日本に来ていまして,これが来るとフェリーが止まって流石に帰れないだろうということでこのようにすぐに引き返すルートとなりました. 結果的に見るとこれは大成功で,台風が来た後北海道を大地震が襲っています.もし稚内に行っていたとすると台風がきて帰れないところに北海道地震がおきてインフラも止まり絶望に瀕していたという未来が待っていたので北海道を離れていて本当にラッキーでした. (地震に見舞われた北海道の皆様はお疲れ様でした.)

本日の宿は大鰐温泉のtakemaruさんによさげな民宿を取ってもらいました.感謝！

11日目のまとめ

  • 費用6180円内訳
    • 18きっぷ 2380円
    • 18きっぷオプション券 2300円
    • どこかで特急に乗ったと思うがこの日は自分でルート構築してなかったので忘れました...
    • 大鰐温泉宿代(追加分) 1500円くらい？
日数 都道府県 費用 18切符効用 距離 駅数 宿代
11 北海道 青森 6180円 7360円 423km 62 1500円
総計 36県 58120円 50890円 4436km 930 22110円

12日目 (9/3 月)

東北の日本海側をガーッと攻めます！

⬆大鰐温泉から奥羽本線でそのまま秋田にいくのもつまらないので,リゾートしらかみに乗る五能線を通って秋田へ向かいます.

⬆五能線を通るため,全席指定席の観光向け普通列車リゾートしらかみに乗ろうとしたのですが,満席でした...と思っていたところ takemaruさんが料金専用補充券を使い,深浦で一旦席を変更することで乗車券を確保することに成功していました.すごい.

⬆この列車,途中でいきなり三味線の演奏が始まったりします.さすが観光列車.

⬆秋田県にあった例の甲子園への垂れ幕.嬉しかったんだろうなあというのが伝わってきます.準...

⬆秋田でtakemaruさんとお別れをして日本海側を沿って山形まで向かいます.

⬆ ここまで旅のログ取りに駅メモをずっと使用しており,そこで一番使っているキャラクター 象潟いろは のデザインの元となった きらきらうえつ の列車を発見.Pietで実行できそうな絵柄がかわいい.このTシャツ欲しいなあ.

⬆大雨の影響で代行バスが出ていました....代行バスって到るところで出ているんですね... 最上川沿いを走る区間でしたが,残念ながら夜遅く明かりもなく最上川をこの目で確認することはできませんでした.

山形のかみのやま温泉で宿を取り,本日は終了.

12日目のまとめ

  • 知見
    • 指定席が満席でも料金専用補充券を使えば途中で席を帰ることで乗車できる場合がある.
  • 費用5880円内訳
  • 今日の読めなかった地名
    • 象潟
日数 都道府県 費用 18切符効用 距離 駅数 宿代
12 青森 秋田 山形 5880円 5620円 438km 117 3500円
総計 37県 64000円 56510円 4874km 1047 25610円

13日目 (9/4 火)

⬆かみのやま温泉(山形) からスタート.ここの足湯は人に入らせる気を微塵も感じさせない温度設定になっていてすごかったです.この温度だと絶対やけどしてしまうと思うんですが,住民の方々は平気なのでしょうか...

⬆山形県でしたので ずんだもちが売っていました. 最初口に入れるとやや甘い餅にたいしてずんだの味が広がり、一瞬うーん？？？みたいな感想になるのですが、噛めば噛むほど親和してきてあれ意外に合うみたいな感覚になって不思議な食品です. もともと食べる気はあまりなかったけど東北ずん子ファミリーのせいで気になって食べてしまいました...

この日は猛烈な台風が京都を襲っていました.部室も一部崩壊したようで,大変そうでした.一方その頃僕の居た新潟ではそのへんで猫がゴロゴロしている程度には平和でして,余裕の表情を浮かべておりました.ぶらぶらと新潟観光をし,時間が余っていたので夕刻ころに @nana さんイチオシの会津若松(福島)へと向かいます.

⬆...なんてフラグを建てていたら見事に列車が止まってしまいました... 許容風量超過による運転休止だそうです. 小一時間ほど待っていると,整備員の方々がやってきまして,乗客を誘導していきます.呑気な感想ですが,線路の上を歩けたりしておもしろかったです. しばらく待っていると代行タクシーがやってきました.会津若松まで50km程もあったのですが,なんとその区間全てタクシーで無料で行けるとのこと.まじか.タクシーメーターがどんどん上がり,2万円に差し掛かったところで会津若松へ到着.二万円もの金額を提示しているタクシーメーターは人生で初めて見たのでなかなか興奮しました.

さて,会津若松に到着した時点で23時でしたので殆どの食堂は閉まっていました.予想外の事態のせいで晩飯など食べておらず,かなりピンチです.こんなときでも慌てず騒がず行きましょう.大きな街だと「24時間営業のフリーWifi有り高速バスターミナル」というものがあります.高速バスを待っている乗客のフリをしながらPCをWifiに接続し,付近の情報を丹念に調べます.どうやら喜多方ラーメンの店がまだ開いてるらしいと分かり,無事晩ごはんにありつけました.

そろそろお金も厳しくなってきましたので,本日の宿はネカフェに決定.タクシーに2万円かけて2千円のネカフェに泊まるという行為を振り返りながらその日は眠りに包まれました.

13日目のまとめ

  • 知見
    • 人数が少ないと代行タクシーが出ることがあり,二万円ほどの区間を乗車可能
    • 24時間営業のフリーWifi有り高速バスターミナルは頼りになる
  • 費用3980円内訳
  • 今日のかわいい地名
日数 都道府県 費用 18切符効用 距離 駅数 宿代
13 山形 新潟 福島 2980円 3020円 277km 71 1600円
総計 38県 67980円 59530円 5151km 1118 27210円

14日目 (9/5 水)

⬆せっかく会津若松に来たので午前は鶴ヶ城を見ていきます.

@kebus , @kurimotz と新潟のぽんしゅ館で待ち合わせということで,のびのびと新潟近郊を巡ります.新潟近郊には 三条・吉田など京大付近っぽい地名が多く不思議な感じがします.キリがよかったのでコインランドリーで洗濯してたらブラックガムが上着をダメにしてしまいました.

ぽんしゅ館で日本酒飲み比べ. 「のぱ」ってやつが頭おかしいくらい甘口でビビりました. ぽんしゅ館では日本酒5種を500円で飲み比べでき,かなりオトクなのでぜひ利用してください.

⬆ 本日の宿 BOOK-INN . 実態は普通のカプセルホテルなのですが,本棚を模した構造になっており,遊び心があります.アイデアをひと手間加えるだけで特別な感じをだせるのはなかなか賢いなーと思います.

14日目のまとめ

  • 費用6880円内訳
    • 18きっぷ 2380円
    • 宿代 3500円 (カプセルホテル Book INN)
    • ぽんしゅ館日本酒飲み比べ 2セット 1000円
  • 今日の読めなかった地名
    • 七日町 (なのかじゃないよ)
日数 都道府県 費用 18切符効用 距離 駅数 宿代
14 福島 新潟 6880円 970円 168km 54 3500円
総計 38県 74860円 60500円 5319km 1172 30710円

15日目 (9/6 木)

この日は新潟から東京まで南下する日でした.

安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！安中榛名！

⬆途中の水上駅で廃墟となったホテルを発見.こういうところには裏社会の人間が住んでいたりしてそうでちょっとわくわくしてしまいます.入ろうとしたら階段が今にも崩れ落ちそうだったので諦めて退散.

高崎で @kebus たちと一旦解散.彼らは安中榛名ではなく前橋に行くらしい.デレマスのイベントが近いうちにあるとかないとか.正しい選択だと思います. 安中榛名を満喫し,高崎で再度合流して東京へ. @prime , @chick , @tuda , @nana さん達と秋葉原で合流し,飲み！感謝ァ☆ そのまま東京西部の羽村の @yu3 さんの家へ泊めてもらうことに！感謝ァ☆

15日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
15 新潟 群馬 埼玉 東京 3860円 4200円 401km 149 0円
総計 39県 78720円 64700円 5720km 1321 30710円

残り6県駆け巡っていきます. ラストなんで巻いていきましょう.

16日目 (9/7 金)

本日は諏訪探訪の日です. (with @kebus @takemaru)

⬆上諏訪駅のホーム内にある足湯. 温泉街の駅の付近には足湯があることは多いですが,ホーム内に足湯がある駅はなかなかありません. かみのやま温泉の足湯と比べても適温で,スペースも広くのんびり温まれますのでかなりよいです.

諏訪五蔵めぐり 上諏訪には5つもの酒造が珍しいことにまとまって経っており,それぞれの蔵を歩いて巡って試飲できるコーナーがあります.以前2つ目でkebusドクターストップをかけられていたので今回はその続きを埋めに来ました.

16日目のまとめ

  • 費用5380円内訳
日数 都道府県 費用 18切符効用 距離 駅数 宿代
16 東京 山梨 長野 5380円 640円 163km 55 3000円
総計 41県 84100円 65340円 5883km 1376 33710円

17日目 (9/8 土)

北陸を埋めちゃいます (with @takemaruさん).

⬆ 諏訪⇔ 糸魚川 への大糸線では滑らかな山が多く,スキー場がよく見えます. スキー場は冬しか見たことがなかったのですが,夏に見るとスキーの滑るところだけキレイに山が禿げていておもしろいですね.スキー場近くの山は管理されていて木の生え方も規則的になっていたりします.これくらいの斜面の駅に近い山って結構各地にあると思うのですが,スキー場になってるところって案外少ないような気がします.

⬆ 石川県は和倉温泉. 宿代の大部分など @takemaru さんには色々サポートしてもらいました. 感謝. 和倉温泉といえば りゅうおうのおしごと！ の 雛鶴あいちゃん の旅館の場所ですね.あいちゃんかわいい.

17日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
17 長野 新潟 富山 石川 9340円 210円 270km 87 4000円
総計 43県 93440円 65550円 6153km 1463 37710円

18日目 (9/9 日)

地元へ帰ってきました！

⬆ 青春18きっぷは 9/10までしか使えないので明日で終わりです. 福井から直接京都駅まで行ってもショートカットできるのですが,京都の最北端あたり行ったことなかったのでちょっと寄り道しています.

⬆ 和倉温泉の足湯スペースから見える大荒れの日本海. 今回の旅では殆ど雨が降っていなかったのですが流石にそろそろ運が着きたのか雨が降ってきています.おかげでこの足湯場には休日なのに誰もいませんでした.

⬆ 小浜まで向かう途中で見かけた湖地帯.これって湖なんですね？ 池・沼・湖・潟・湾 の違いってなんなんでしょうね...素人の僕にはこれは潟に見えます... 小浜駅にはオバマがいるかなーと思いましたが別にいませんでした.今はトランプですもんね.ここの区間では一番海が近いところで（曲がっているわけでもないのに）速度を大きく落としていて観光列車と同じだなあと思いました.

⬆そしてやはり止まる山陰線.. 最初の日と同じで本当にすぐ止まる区間です.

最近高槻(大阪)の実家にもなかなか帰ってなかったので今日は実家に寄って帰ることにして終了.

18日目のまとめ

日数 都道府県 費用 18切符効用 距離 駅数 宿代
18 石川 福井 京都 兵庫 大阪 2380円 5450円 478km 167 0円
総計 44県 95820円 71000円 6631km 1630 37710円

19日目 (9/10)

残していた南海を行きます.

⬆ @pastak さんから確保を頼まれていた和歌山のフリーペーパーを確保. 意外とすぐには見つからず,和歌山市内を結構探し回ってしまいました.こういうクリエイター特集記事が地方フリーペーパーにあることってあるんですね.

⬆ 和歌山アニメイトにて,こいかぜ彩を購入 和歌山では以前 高垣楓さんを追って熊野古道に行ったり , 地酒 高垣の一升瓶を買って自転車で帰京したり したことがあります.和歌山と高垣楓くらいの距離感が一番好きなのかもしれません.

⬆ 奈良リニア！これで京都に勝つる！

⬆ 一周を終えたツイート

19日目のまとめ

  • 費用4140円内訳
    • 18きっぷ 2380円
    • こいかぜ 彩 1660円
    • うめぼし 100円
  • 今日の読めなかった地名
    • し、柴島…
    • に、忍海…
    • め、名手...
    • た、柘植...
日数 都道府県 費用 18切符効用 距離 駅数 宿代
19 大阪 和歌山 奈良 三重 滋賀 京都 4140円 2590円 304km 170 0円
総計 46県 99960円 73590円 6935km 1800 37710円

まとめ

19日間の一周経路

台風がなければ 1,2 日目が, 特に予定が無ければ 13,14,15 日目 や 16 , 17 日目 の部分は一日で行けて4日短縮でき,18きっぷは15日分(3綴)で足ります. 早朝から深夜まで行く限界プランだと最短9日で一周を達成できるようですが,精神・体力的に大変なので,都合と予算に合わせてやっていきましょう.

19日間の費用内訳

日数 都道府県 費用 18切符効用 距離 駅数 宿代
1 京都 兵庫 7380円 210円 158km 3 5000円
2 兵庫 鳥取 島根 5780円 3560円 356km 23 3400円
3 島根 山口 福岡 佐賀 長崎 熊本 7940円 6680円 494km 58 4000円
4 熊本 鹿児島 宮崎 大分 5460円 4510円 294km 61 0円
5 愛媛 高知 徳島 香川 7590円 3550円 354km 88 5000円
6 香川 岡山 広島 兵庫 大阪 京都 2380円 5020円 414km 153 0円
7 京都 滋賀 岐阜 愛知 静岡 神奈川 東京 2380円 5830円 499km 185 0円
8 東京 埼玉 千葉 茨城 栃木 福島 6230円 3070円 379km 91 3210円
9 福島 宮城 岩手 秋田 青森 4380円 7230円 653km 142 0円
10 北海道 2380円 3860円 412km 64 0円
11 北海道 青森 6180円 7360円 423km 62 1500円
12 青森 秋田 山形 5880円 5620円 438km 117 3500円
13 山形 新潟 福島 2980円 3020円 277km 71 1600円
14 福島 新潟 6880円 970円 168km 54 3500円
15 新潟 群馬 埼玉 東京 3860円 4200円 401km 149 0円
16 東京 山梨 長野 5380円 640円 163km 55 3000円
17 長野 新潟 富山 石川 9340円 210円 270km 87 4000円
18 石川 福井 京都 兵庫 大阪 2380円 5450円 478km 167 0円
19 大阪 和歌山 奈良 三重 滋賀 京都 4140円 2590円 304km 170 0円
総計 46県 99960円 73590円 6935km 1800 37710円
日数 都道府県 費用 18切符効用 距離 駅数 宿代

⚠ 費用: 食費を含まない ⚠ 18切符効用 : 全く同じ経路・区間の乗車降車を18きっぷを使わずに行った場合と比較 ⚠ 駅数 : 駅メモでチェックインした駅数 ⚠ 距離 : 駅メモによる計測

3週間程ずっと旅をしていたようですが 計10万円以内でなんとか収められたようです.フェリーを宿として利用したり,格安のビジネスホテルやネカフェを利用したりして節約していきましょう.部員にサポートしてもらったり,部員の家に泊めてもらったりカンパを下さったりなど支えてくださった皆様には感謝の念を申し上げます.

日本一周で約7000km程の距離を移動したようです.地球の半径が約6300kmなので,この距離があれば地球の中心まで行くことが実質的に可能と言えますね.

駅メモによると日本には9400駅程度存在するらしいので,今回寄った1800駅でもまだまだ行っていない駅が存在することが分かります.網のように張り巡らされてるんですねー.

地方に比べると都会はやはり駅数が多いことが分かります.だいたい駅は3kmに一本程度の割合であるようです.北海道だと5kmに一本だったり,東京だと1kmに満たない間に一本あったりもしますが.

都会は混んでいるのは大変つらいですが,それでも駅の割合も多いし電車の密度も高くてやはり便利だなーと思います.田舎の列車は一時間〜数時間に一本しかないこともままありますが,そのぶん人は少なくて横になって寝ている人やビールを飲んで足を伸ばして寝ている人なども多く,自由な感じがします.

難読駅名まとめ

※ 難読さには個人差があります. 高槻が実家の僕からしたら枚方を読めない人なんて信じられませんが世間的にはそうでもないこともありそうだったりしますからね.

経県値マップ

https://uub.jp/kkn/km_new.cgi?MAP=44333442332243424224233335543334333343332343330&NAM=%E3%82%80%E3%82%89%E3%81%9F&CAT=%E7%94%9F%E6%B6%AF%E7%B5%8C%E7%9C%8C%E5%80%A4

今回の旅だけを見るとこんな感じになりそうです.

のりつぶしMAP

http://www.noritsubushi.org に 宿泊場所を追記したもの. 薄い水色の線は今回通らなかったJR線です.

駅メモ！

駅メモはログに有効活用させてもらいました.今まで殆ど使っていなかったので,ほぼ19日間の結果といえます. 最初10万位程度だったのにたった三週間で2500位程度にまで上がるのはちょっとおもしろかったです. いろは・ハル・るる・るり のしりとり編成にしています.みらい・ルナもベンチに居ます.この6人は全員この旅だけでLV50になりました.赤新駅ばっかりですからね.

さいごに

こういう思いで始めた日本一周ですが,日本全国を廻りたいという欲望は無事叶えることができました. やってみてわかったのですが,鈍行列車の中でコーディングすることは充電・圏外・揺れなどの影響で不可能でした.M1の人々はみんなインターンに行って働いているのに自分だけ全国を廻ってのうのうとしている状態は控えめに言って最高でした. ありがとうございましたー.

46都道府県巡ってきたので安中榛名駅についての怪文書を書く

はじめに

此の度機会がありまして,18きっぷで46都道府県を巡ってきました. f:id:CHY72:20181002200417p:plain こんな感じのルートでございます. モラトリアムの夏休みの期間を利用して三週間ほどかけて行ってまいりました. 10万円程度で巡れまして,顔写真付きのその詳細についてはKMCの内部記事に書いてありますので興味の在る方は入部してください.

安中榛名駅が好き

安中榛名駅をご存知でしょうか. ご存知でない方は http://ja.uncyclopedia.info/wiki/安中榛名駅 を読んでください. 上記の通り歴史的経緯で何もない山の中に建造されてしまった新幹線停車駅です. ところで僕は安中榛名駅が大好きで日本一周で巡った中でも最高の駅だと思ったのでそれについて書こうと思います. なおこの記事は大好きな安中榛名について思うがままに書いているので過分に怪文書になっていますので注意してください.

観光地と原風景について

安中榛名がなぜ良いかを語るにあたって,まずは「観光地」について述べましょう.

旅の中で1800駅程度巡りましたが,巡った中でも観光地的な駅は多かったです.

f:id:CHY72:20181002202550j:plain

これはJR九州の熊本にある人吉⇔吉松を結ぶ観光列車いさぶろうで,以下のような楽しみが味わえます.

  • 日本三大車窓の矢岳越えの景色がよい
  • 車内観光アナウンスが流れて分かりやすい
  • 山内の各駅では10分程停車し,記念撮影が行える.
  • マスコット的な駅弁おじさん(だったっけ？)が居る
  • 駅には観光列車の乗客向けの売店がある
  • 地元の人の観光客へ向けての手を振ってくれる運動が見れる.

いかにも観光という感じがします. なんと理想が詰め込まれた光景でしょうか.

f:id:CHY72:20181002203957j:plain

これは兵庫の城崎温泉で,見ての通りまさしく理想的な温泉街ですね.

f:id:CHY72:20181002205026p:plain

変わりどころだと,ここ北海道は小幌も理想的な観光地駅でしょうか. 山と海に囲まれたまさに理想的な秘境駅です. 高度に観光地化しており,ここの風景を撮ったコンテストが開かれていたり, @Lavendelstrauss 氏管理の元,旅用のノートが置かれていたり観光用の同人誌が置かれていたりします. 直ぐに往復できる列車が一日一回あり,僕が訪問した際は2,30人程の乗客が降りていました. 市も観光地としてこの駅を廃止しないようで,まさしく観光地として祝福された駅です.

f:id:CHY72:20181002210922j:plain

ああ,最後にここ茨城は大洗も観光地でしょう. 寂れた街が人気漫画で全面的に町おこし！理想的です！

以上紹介した駅は理想的な原風景の願望を叶えてくれる想像通りの観光地です. さて,「観光地」という言葉を多用してきましたが,改めて観光地を「理想的な原風景の願望を叶えてくれる場所」として定義しましょう.

「矢岳越えと古き良き村」を叶えてくれる観光列車いさぶろう, 「理想的な温泉街」を叶えてくれる城崎温泉, 「理想的な秘境駅」を叶えてくれる小幌駅, 「町おこしに成功した街」を叶えてくれる大洗駅,どれも私にとっては素晴らしい観光地です. (なお,「観光地」については学問的にきっと様々な知識が世には蓄えられているのでしょうが,今回はポエミーな気分なので清々しく無視することにします.)

何かありそうで何もない安中榛名駅

前節で,観光地について述べました. 良く言えば原風景を叶えてくれる風景は,悪くいうと紋切り型の風景なわけでして, 好きではあるのですが,心の隙間が埋まらない,虚ろな気持ちもほんのり抱えてしまうわけです.

これを埋めてくれるような場所はあるのでしょうか.

今までの観光地の反対の存在「何もない風景」の駅はどうでしょうか. このような駅は地方の田舎の電車に乗ってみれば日本中どこにでもあります. 当然その駅は現地の人にとっては意味のある風景なのですが, 何も知らない人からすれば緑やただの街だけが広がるただの何もない駅です. しかしながら其の駅も「何もない風景」という原風景を叶えてしまう駅になってしまい, 結局は紋切り型の枠から離れることはできません. 「田舎の路線に乗って田舎の何もない場所を探索」！ああ！原風景！ 元から何もないことを期待され,何もないことに満足される風景よ！

何もないことを期待されてるのがマズいんでしょうか. 歴史的・立地的に何もなさそうな場所に何もなかった. それはなんと予想通りの風景でしょうか...

何かありそうに期待されていながら本当は何もない...そういう塩梅がちょうどよく,心の隙間を埋めてくれるのではないでしょうか.

知名度の無いもの,寄ろうとするオタクが少ないものほどいい.....

...

...

...

...

...

...

...

そこで 安中榛名駅の登場です！！！ この駅は新幹線しか止まらず！！！ 更に日常の「安中榛名」さんの名をそのまま冠している！！！ いかにも何かありそう！！！

隣の新幹線の止まる高崎駅から1200円も払わないと行けない！ 新幹線しか止まらないのでこの方法で行くしか方法はない！ 胸が高まる！いかにも何かありそう！

f:id:CHY72:20181002232738j:plain

道中の車窓！新幹線で高崎駅から8分です. 新幹線でしか行けないからきっとすっごいところなんだろうなー！

f:id:CHY72:20181002221829j:plain

駅のホーム！ 新幹線が停まる駅なのに3人位しか降りなかったぞー！おっかしいいなあああ！！！ やっぱりなにもないのかなーーーーー！！！！！！！

f:id:CHY72:20181002232533j:plain

駅のホームにある旗！ 個人的に大好きな旗です！ 「梅林」「温泉」「湖」「ゴルフ」「果物」と書いています.なお

  • 梅林 : これは正しいかもしれない
  • 温泉 : ここではなくバスでずーっと行った先の磯部駅の磯部温泉のもの
  • 湖 : ここから山を越えた裏にある榛名湖のこと.なお道がなく安中榛名駅からは行けない
  • ゴルフ : ただっぴろい場所の換言
  • 果物 : 「桃」とか「梨」とか具体性がない.目立ったものがないからね

と,見るも無残な「何かありそうで何もない」を臨世させた最高の旗です！ ここまで何かありそうで何もない旗を見たことがありますか！最高！

f:id:CHY72:20181002222557j:plain

通路！何かありそうで何もない！ いっぱい貼ってあるけれど肝心の安中榛名に関する観光情報は一切何もありませんです！最高！

f:id:CHY72:20181002222828j:plain

駅の構内！新幹線が止まる駅だけあっていかにも何かありそう！ 観光案内所に行くと手書きの登山案内地図がもらえます！ なお観光案内はそれしかありません. やっぱりなにもないじゃん！！！！！！！！

売店も何か売ってそうだけど絶妙に何もない！

f:id:CHY72:20181002232834p:plain

お昼ご飯！ 峠の釜めし弁当！ なお,この釜飯弁当は食べ終わってしまうと窯が付いてきてしまう！

本当に何もないわけではなくてこれはある意味名物的な存在として「在る」と言っていいものかもしれない...？ でも逆に「「徹底した何もない」という何かありそう」が壊されて何かありそうで何もないに拍車をかけているなあ！最高！

f:id:CHY72:20181002232650j:plain

駅全体！整っていて何かありそう！ でも本当はやっぱり何もなくてその結果駐車場は無料です！ なにもないやんけ！

f:id:CHY72:20181002223613j:plain

十分に満喫したのでこの日は続きに予定があり,バスで帰還しました. 駅から150mほど離れたところにバス停っぽいところがあります. なおバス停にはおばあちゃんが居て,「駅前に停まってるあのバスなんでここ(バス停)に来ないんかなあ」とずっと一緒に話していました！ 何かありそうに見えて内容がなかった！最高！

最後に

日本一周は楽しく,そして何かありそうでやはり何もない安中榛名駅はどう見ても最高.

ツイキャスエンジニアインターンシップ2018応募前チャレンジでランキング1位を取った

はじめに

モイ！ツイキャスエンジニアインターンシップ2018 - TwitCasting の応募前チャレンジというおもちゃがあったので遊んでみました.

Hit&Blowというゲームで点数を競えるチャレンジです. これは,'0123456789'のように10桁の重複しないランダムな数字が与えられ,それを予想するゲームです.

例えば'0123456789' が正解だったとして 「答えは'1023456789' ですか？」とリクエストを投げるとツイキャスサーバーから 「8箇所あたっています(hit=8)」などと返ってきますのでそれを元にして正解を探索することができます.

見事「答えは'0123456789' ですか？」と正答できれば,ツイキャスサーバーから「正解です！インターン応募フォームはこちら！」と返ってきます.

募集要項のどこにも「これを解くプログラムを公開してはいけない」とは書いていなかったので,募集期間(7/11:23:59:59)を越えたので公開します.

解法

途中過程で n4ru5e氏と1位を争ってなかなかそれはそれで楽しかったので,途中の過程も書きたいのですが,めんどうなので最終解法だけ記述します.

このチャレンジでは並列にリクエストを送ることが可能です. そしてこのチャレンジの点数は正解までに掛かったラウンド数(試行回数)ではなく,単純にチャレンジ開始から掛かった時間のみで点数が決まります.

以上の前提と,ネックはCPU的な計算時間よりもネットワーク方面に落ち着くことから,なるべく並列にリクエストを送れるような戦略を取るのがよいことがわかります. また,問題の難易度を3~10で選べるのですが,10以外は点数が出ないので10にします.

戦略としてはこうです.

  1. ゲーム開始のフラグを送る.
  2. 並列にn個のリクエストを送信する.
  3. 返ってきたn個のhit数の列のパターンからあり得る答えリストを作成する.
  4. その答えリストを送信する.

こうして, 1. 2. 4. の三回の通信と,3.の答えリスト作成を如何にして最小にするかという問題になります.

並列に送信するn個のリクエストについて

正解としてありえるのは 0123456789 の順列なので 約360万通りしかありません. ですので,ランダムに作成したn個のリクエスト ([0123456789,6574839201,...,7564312098] など) に対して返ってくる Hit数の列([0,0,5,...,0,1]など)を予めメモして置くことが可能です.これなら先に計算しておくことでチャレンジ中でも一瞬で答えリストが求まりますね.

nの値は小さすぎるとパターンが少なく答えリストが大きくなってしまい本末転倒となります. 逆にnが大きすぎると答えはほぼ1択にできますがそれを求めるまでに通信する量が多くなり時間がかかってしまいます. 試行の結果 n=10 くらいがちょうどよかったので n=10にしました.

ランダムに10個のリクエストを作成すると約360万通りの正解候補に対してhit数の列は 70万程度のパターンになります. ただ,毎回ランダムな10個のリクエストを作成するのもアレなので,もうちょっとよいリクエスト(hit数の列の取りうるパターン数が多いもの)を考えたいものです.

そこでNimで遺伝的アルゴリズムを使ってよいリクエストを探索するプログラムを書いて一時間くらい回してみました.

{.emit: """#pragma GCC target ("sse4")""".}
proc popcount(n:int64):int{.importC: "__builtin_popcountll", noDecl, .}
proc memset(m:ptr ,ch:int,n:int):void{.importc:"memset",header:"string.h",noDecl.}
import sequtils,strutils,strscans,algorithm,math,future,macros
import sets,tables,random,intsets,strformat

const shift = 4
const n = 10

proc getAscending(n:int):seq[int] =
  result = @[]
  for i in 0..<n:result &= i
proc getRandom(n:int): seq[int]=
  result = getAscending(n)
  result.shuffle()

proc toHash(query:seq[int]): int =
  result = 0
  var s = 0
  for q in query:
    result += q shl s
    s += shift

proc fromHash(hash:int): seq[int] =
  result = @[]
  var h = hash
  for i in 0..<n:
    result &= h and 0xf
    h = h shr shift

proc getPermutations(n:int): seq[int] =
  result = @[]
  var permutation = getAscending(n)
  result &= permutation.toHash()
  while permutation.nextPermutation():
    result &= permutation.toHash()

var maxValue = 0
let permutations = getPermutations(n)
const bits = [1,7,49,343,2401,16807,117649,823543,5764801,40353607]
proc getHitPattern(permutation:int,queries:seq[int]) : int =
  result = 0
  for i,query in queries:
    let h = query xor permutation
    let hit = 10 - popcount(
      ((h and 0x11111111_11111111) shr 0) or
      ((h and 0x22222222_22222222) shr 1) or
      ((h and 0x44444444_44444444) shr 2) or
      ((h and 0x88888888_88888888) shr 3))
    if hit >= 7 : return 0 # hit=8,10の探索は誤差なので速度のために諦める
    result += hit * bits[i]

const seven10 = 282475259+10
var table : array[seven10,bool]
proc check(queries:seq[int]) :int{.discardable.}=
  stdout.write queries.join("")[0]
  stdout.flushFile
  if queries.len() != queries.sorted(cmp).deduplicate().len() : return 0
  memset(addr table,0,seven10)
  var size = 0
  for permutation in permutations:
    let hitPattern = permutation.getHitPattern(queries)
    if table[hitPattern] : continue
    table[hitPattern] = true
    size += 1
  if size <= maxValue: return size
  maxValue = size
  let answers = queries.map(fromHash)
  echo(($answers).replace("], ","],\n "))
  echo size," patterns"
  echo size.float / permutations.len().float," mean"
  return size

# GA
const gaNum = 16
const queryNum = n
var queries = newSeqWith(gaNum,newSeqWith(queryNum,getRandom(n))).mapIt((v:0,q:it))
while true:
  let preQueries = queries
  var nowQueries = newSeq[tuple[v:int,q:seq[seq[int]]]]()
  var th = 0.5 * (maxValue / 70_0000) * (maxValue / 70_0000)
  for i in 0..gaNum:
    for j in (i+1)..<gaNum:
      var p = preQueries[i].q
      var q = preQueries[j].q
      if rand(1.0) < th / 5: q = newSeqWith(n+1,getRandom(n))
      var r = newSeq[seq[int]]()
      for k in 0..<queryNum:
        if rand(1.0) > 0.5: r &= p[k]
        else: r &= q[k]
      for k in 0..<queryNum:
        while true:
          if rand(1.0) < th / 2:
            swap(r[k][rand(n-1)],r[k][rand(n-1)])
          else: break
      nowQueries &= (r.map(toHash).check(),r)
  let nexts = (nowQueries & preQueries).sorted((x,y)=> y.v - x.v)[0..gaNum]
  queries = nexts.sorted((x,y)=> y.v - x.v)
  echo queries.mapIt(it.v)

結果,

{
  {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
  {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
  {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
  {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
  {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
  {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
  {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
  {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
  {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
  {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
}

が得られました.

821843通りのパターン数となって結構いい感じです. このリクエストだと答えリストを最大5個送信するとして3割くらいの確率で成功できます.

Go言語で並列に高速に通信する

アルゴリズムはほぼ最速なので,あとは通信部分です.

Nim -> Python -> NodeJs などと送信する言語を変えたりしましたが,結局はGoに落ち着きました. goroutine が強いのと通信に関する標準ライブラリが出揃っているのとコンパイルできるのが強いですねという感じです. 並列に送信するのは goroutineですぐにできますし,便利ですね.

実行するサーバーは39ff氏の前回のFizzbuzzの考察 (kblog: ツイキャス新卒採用2019で遊んだ) でも速いと書かれている通り,ConoHaでやるといい感じです. AWSとかIDCFクラウドとか東京の知人に託すとか色々しましたが,結局ConoHaが一番でした.

ここまでの戦略で,多分1177k後半くらいになると思います.

ゲーム開始から終了までに 70ms くらいかかる速度です.

HTTPSの高速化

このままの状態では 1179kを超えることができません. ここから先はHTTPS通信を高速化していきます. この問題ではKeep-Aliveは無効・HTTP2通信はできないなどの制約がありますがチューニングは可能です.

CipherSuitesを変える

HTTPSのCipherSuitesをクソ雑魚なものに変えて高速化します. Go言語だと tls.Config をいじることでそれが実現可能です.

config := &tls.Config{ 
  CipherSuites: []uint16 { tls.TLS_RSA_WITH_RC4_128_SHA, }, 
}

この手法はnonylene先生がふと言いだした手法で僕には思いつけなかったですね…

これで 1178k後半くらいになります.

ゲーム開始から終了までに 60ms くらいかかる速度です.

予めTLSのコネクションを16個貼る

最後のチューニングです.

Go言語の tls.Dial を使って通信を全て直書きします.

conn := tls.Dial("tcp", "apiv2.twitcasting.tv:443", config )

これを予め使用する16個分ゲームID取得に先駆けて取得しておき, 以降

data := `{"answer":"` + answer + `"}`
conn.Write([]byte(
    "POST /internships/2018/games/"+id+" HTTP/1.1\n" +
    "Host: apiv2.twitcasting.tv:443\n" +
    "Authorization: Bearer " + token + "\n"+
    "Content-Length: "+ strconv.Itoa(len(data))  +  "\n" +
    "\n" + data + "\n"))

のように予め取得した conn を用いて通信直書きでオーバーヘッド無しに回答を送信します.

これで1179.5k が出ます.ゲーム開始から終了まで40msくらいの速度です. 以上のチューニングによって 1位になることができました.やったぜ.

回答コード

package main

import (
  "crypto/tls"
  "encoding/json"
  "net"
  "runtime"
  "strconv"
)

const allow2ndNum = 5
const sleepSecond = 10

func initEnv() {
  cpus := runtime.NumCPU()
  runtime.GOMAXPROCS(cpus)
}

func getConns(n int) []net.Conn {
  config := &tls.Config{
    InsecureSkipVerify: true,
    CipherSuites: []uint16{
      tls.TLS_RSA_WITH_RC4_128_SHA,
    },
  }
  results := make([]net.Conn, n)
  for i, _ := range results {
    results[i], _ = tls.Dial("tcp", "apiv2.twitcasting.tv:443", config)
  }
  return results
}

func getId(conn net.Conn) string {
  defer conn.Close()
  token := "??"
  conn.Write([]byte(
    "GET /internships/2018/games?level=10 HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if n == 0 || string(buf[2:4]) != "id" {
    return ""
  }
  // JSONをパースする時間も勿体無いので決め打ち
  id := string(buf[7 : n-2])
  return id
}

type AnswerJson struct {
  Hit     int    `json:"hit"`
  Message string `json:"message"`
  Round   int    `json:"round"`
}

func postAnswer(id, answer string, ch chan int, conn net.Conn) {
  defer conn.Close()
  token := "??"
  data := `{"answer":"` + answer + `"}`
  conn.Write([]byte(
    "POST /internships/2018/games/" + id + " HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n" +
      "Content-Length: " + strconv.Itoa(len(data)) + "\n" +
      "\n" +
      data + "\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if buf[7] == '1' && buf[8] == '0' {
    var answerJson AnswerJson
    json.Unmarshal(buf[:n], &answerJson)
    println(answerJson.Message)
    ch <- 10
  } else {
    // JSONをパースする時間も勿体無いので決め打ち
    ch <- int(buf[7] - '0')
  }
}

func reverse(a []int, startIndex int) {
  offset := len(a) - 1 + startIndex
  for i := startIndex; ; i++ {
    j := offset - i
    if i >= j {
      break
    }
    a[i], a[j] = a[j], a[i]
  }
}
func nextPermutation(a []int) bool {
  if len(a) < 2 {
    return false
  }
  i := len(a) - 1
  for i > 0 && a[i-1] >= a[i] {
    i--
  }
  if i == 0 {
    return false
  }
  j := len(a) - 1
  for j >= i && a[j] <= a[i-1] {
    j--
  }
  a[j], a[i-1] = a[i-1], a[j]
  reverse(a, i)
  return true
}
func encode(a []int) int64 {
  result := int64(0)
  k := 1
  for i := 0; i < len(a); i++ {
    result += int64(k * a[i])
    k *= 10
  }
  return result
}
func decode(a int64, n int) []int {
  result := make([]int, n)
  for i := 0; i < n; i++ {
    result[i] = int(a % 10)
    a /= 10
  }
  return result
}

func toString(q []int) string {
  result := ""
  for i := 0; i < len(q); i++ {
    result += strconv.Itoa(q[i])
  }
  return result
}
func getInitialQueries() [][]int {
  return [][]int{
    {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
    {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
    {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
    {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
    {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
    {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
    {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
    {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
    {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
    {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
  }
}
func getGameMemo() (map[int64][]int64, [][]int) {
  a := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  table := make(map[int64][]int64)
  queries := getInitialQueries()
  for {
    hits := make([]int, len(queries))
    for j, query := range queries {
      hit := 0
      for i := 0; i < 10; i++ {
        if query[i] == a[i] {
          hit++
        }
      }
      hits[j] = hit
    }
    key := encode(hits)
    val := encode(a)
    if _, exists := table[key]; exists {
      table[key] = append(table[key], val)
    } else {
      table[key] = []int64{val}
    }
    if !nextPermutation(a) {
      break
    }
  }
  return table, queries
}

func main() {
  initEnv()
  table, queries := getGameMemo()
  conns := getConns(1 + len(queries) + allow2ndNum)
  id := getId(conns[0])
  if id == "" {
    for _, conn := range conns {
      conn.Close()
    } 
  }
  hitCans := make([]chan int, len(queries))
  for i, query := range queries {
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(query), hitCans[i], conns[i+1])
  }
  hits := make([]int, len(queries))
  for i, hitcan := range hitCans {
    hits[i] = <-hitcan
  }
  answers := table[encode(hits)]
  hitCans = make([]chan int, len(answers))
  for i, answer := range answers {
    if i >= allow2ndNum {
      break
    }
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(decode(answer, 10)), hitCans[i], conns[i+1+len(queries)])
  }
  for i, hitcan := range hitCans {
    if i >= allow2ndNum {
      break
    }
    <-hitcan
  }
  for _, conn := range conns {
    conn.Close()
  }
}

さいごに

前回のFizzBuzzに比べてできることが多かったのでISUCONみたいな感じでなかなか楽しかったです.

特に,競い合える人がいたのが本当によくて,様々な知見が得られました…

前回のISUCONではお茶くみくらいしかできなかったので今回は僕もGoをチューニングして @nakario_jp を手伝えるようになりたい.

追記 (07/26)

ついでにそのままモイのインターン応募したけど落ちた笑