青春18きっぷ 弾丸北陸日帰り旅行
今年の春，知り合いが青春18きっぷ期間に1枚余ったというので2000円程度で買い取って北陸へ日帰り旅行をしてきましたのでその話をしたいと思います．
この記事は以下のAdvent Calendarの記事です．
SPC同好会 Advent Calendar 2017 25日目 adventar.org
東京高専 Advent Calendar 2017 24日目 adventar.org
目的
計画
大糸線を乗り切り直江津から折り返し東京まで戻ってきて，次に上越線に乗車して土合駅を制覇するのは面白くないと誰もが思うと思います． そこで，糸魚川まで大糸線を利用したのち、越後ときめき鉄道で直江津，北越急行ほくほく線で十日市まで行き，そこから上越線で東京に戻るようなルートを取ることにしました． 北陸本線はすでに第三セクター化されており、その区間は素直にお金を払って乗車するしか手段がありませんが，よい機会なので乗ってみたい思います． 今回のスタートは登戸駅ですが、高尾駅を経由するので東京高専の寮生も同様の日帰り北陸旅行をすることができます．(無理やり東京高専ネタ)
出発進行!!!!
登戸→松本
世界レベルで利用者数が多い登戸駅ですが，早朝は誰もいません．
ちなみに，平日の登戸始発立川行き 455F は登り川崎方面のホームから発車します．
改札には大きく立川行き始発は2番線発車ですと掲示されていました．
このような立川行と川崎行の表示を同時に見ることができるのもこの時間だけです．
立川で乗り換え大月行 453T/1343M に乗り換えます．
夜明け前でコンデジでは車両の写真を撮るのが難しかったのでここら辺は省略します．
大月から甲府までは 327M で行きます．
甲府から松本までは 425M で行きます．
さてここまでの工程を軽く表にまとめたいと思います．
| 4:39発 | 登戸 | ||
|---|---|---|---|
| ↓ | 27分 | 18.2km | 南武線 |
| 5:06着 | 立川 | ||
| （18分） | |||
| 5:24発 | 立川 | ||
| ↓ | 18分 | 15.6km | 中央線快速 |
| 5:42着 | 高尾（東京） | ||
| ↓ | （直通） | ||
| 5:43発 | 高尾（東京） | ||
| ↓ | 36分 | 34.7km | 中央本線（高尾－甲府） |
| 6:19着 | 大月 | ||
| （4分） | |||
| 6:23発 | 大月 | ||
| ↓ | 49分 | 46.3km | 中央本線（高尾－甲府） |
| 7:12着 | 甲府 | ||
| （13分） | |||
| 7:25発 | 甲府 | ||
| ↓ | 1時間53分 | 101.3km | 中央本線（甲府－松本） |
| 9:18着 | 松本 |
このような感じでまず登戸から松本まで行きます．
松本-糸魚川
ここからが大糸線本番です．大糸線ですが，アルプスの山々の車窓を楽しむために架線柱の配置などが工夫されています．てことで，車内から見える景色を紹介していきます．
信濃大町で乗り換えです．
どんどん山へと突き進んでいきます．
南小谷です．ここまでがJR東日本の区間になります．ここから先はJR西日本の管轄になるのですが，糸魚川からの北陸線は第三セクター化されてしまったため，JR西日本取り残され区間になってます．そして南小谷から糸魚川までは非電化区間になります．
ここからはキハ120形にお世話になります．
ということで糸魚川駅です．
糸魚川駅から歩いて数分のところに日本海展望台という展望台が一応ありまして，そこに登ると日本海とアルプスの山々を望むことができるので，行ってみると良いかもしれませんが，乗り継ぎの時間には注意です．危うく乗り遅れるところでした．
もうひとつ糸魚川駅にはキハ52系が展示されてますので，そちらもひと目見ておくことをおすすめします．
| 9:22発 | 松本 | ||
|---|---|---|---|
| ↓ | 58分 | 35.1km | 大糸線（松本－南小谷） |
| 10:20着 | 信濃大町 | ||
| （9分） | |||
| 10:28発 | 信濃大町 | ||
| ↓ | 58分 | 35.0km | 大糸線（松本－南小谷） |
| 11:26着 | 南小谷 | ||
| (34分) | |||
| 12:00発 | 南小谷 | ||
| ↓ | 57分 | 35.3km | 大糸線（南小谷－糸魚川） |
| 12:57着 | 糸魚川 |
糸魚川-越後湯沢
まずえちごトキめき鉄道です．直江津まで行きます．それにしてもよくわらかない名前の付け方ですよね...
さて，ここからは北越急行ほくほく線です．車窓を見てると，また山に向かってるって感じがします．
最後に上越線です．越後湯沢駅まで行きます．
越後湯沢からはこんな山々を見ることができます．商業施設がかなり充実しているので，食料などを補給したり，美味しいものを食べたり，いろいろとできます．
ざっと越後湯沢までの工程です．
| 13:22発 | 糸魚川 | ||
|---|---|---|---|
| ↓ | 41分 | 38.8km | えちごトキめき鉄道日本海ひすいライン |
| 14:03着 | 直江津 | ||
| (24分) | |||
| 14:27発 | 直江津 | ||
| ↓ | 57分 | 66.6km | 北越急行ほくほく線 |
| 15:24着 | 六日町 | ||
| (9分) | |||
| 15:33発 | 六日町 | ||
| ↓ | 21分 | 17.6km | 上越線 |
| 15:54着 | 越後湯沢 |
越後湯沢-東京
ここから少々ルートを外れて，土合駅に寄ります．土合駅は平日で登山シーズンでないからか自分しかおりませんでした．
駅舎はこんな感じです．もぐら駅っぽい外観(?)をしてますね．ちなみに3月ごろに行ったのですが，雪が身長よりも高く2[m]くらい，まだ残っていました．
駅舎から地下ホームの方へ向かう道です．正直かなり良い雰囲気を出してました．地下を貨物列車などが通過すると地下からかなり強い風が吹いてきたりします．
かの有名な，終わりの見えない階段です．上り線のホームとの標高差は約70m,，約10分程度歩いてやっと下りのホームにたどり着けます．
地下ホームです．微妙に薄暗く，例えるならば少女週末旅行10話の地下鉄のホームといえばいいでしょうか．要塞感もあり，不気味な感じでした．帰りはもちろん，あの先の見えない階段を上ります．
こちらが地上部の駅舎の中です，薄暗く，待合室など閉鎖されてるため廃墟感もある，良い雰囲気でした．
駅名標です．古さがにじみ出てますね．
こちら，水上です．高崎行きの普通列車です．
そんなこんなで高崎駅につくと，いつもの安心できる都市の雰囲気を取り戻し始めます．
高崎からは上野東京ラインです．この列車小田原行きで，寝過ごせば見事に小田原...ではなく，これで東京駅まで一本でいくことができます．かなり便利ですよね．
ということで越後湯沢から1時間の土合駅の観光を経て東京まで行く工程表です．
| 16:52発 | 越後湯沢 | ||
|---|---|---|---|
| ↓ | 26分 | 24.9km | 上越線 |
| 17:18着 | 土合 | ||
| (58分) | |||
| 18:16発 | 土合 | ||
| ↓ | 12分 | 10.2km | 上越線 |
| 18:28着 | 水上 | ||
| (16分) | |||
| 18:44発 | 水上 | ||
| ↓ | 1時間04分 | 59.1km | 上越線 |
| 19:48着 | 高崎 | ||
| (19分) | |||
| 20:07発 | 高崎 | ||
| ↓ | 1時間53分 | 105.2km | 上野東京ライン（高崎・東海道線） |
| 22:00着 | 東京 |
まとめ
かなりぎりぎりの行程ですが，大体ネックになってるのは，大糸線なので大糸線を超えて北陸に出さえすれば，どうとでもなります．ただ，雪の多い時期などは大糸線が終日運休や，各北陸の路線が大幅に遅れ，新幹線ループを使わないと帰れないことや，家に帰る手段がないということになるので，気を付けた方がいいです，ではみなさんも 18きっぷの旅 をぜひ楽しんでください．
GCC's "-march=native" Option
どうも．先程 #GentooInstallBattle を始めました．
ところで，gccの-march=nativeオプションですが，CPUアーキテクチャに合わせた最適化をするという意味ですが，それがどんな感じに展開されてるのか気になり調べてみました．
Version of GCC
$ gcc --version gcc (GCC) 7.2.1 20171128 Copyright (C) 2017 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
man of GCC(L:18896)
-march=cpu-type
Generate instructions for the machine type cpu-type. In contrast to
-mtune=cpu-type, which merely tunes the generated code for the specified cpu-
type, -march=cpu-type allows GCC to generate code that may not run at all on
processors other than the one indicated. Specifying -march=cpu-type implies
-mtune=cpu-type.
The choices for cpu-type are:
native
This selects the CPU to generate code for at compilation time by
determining the processor type of the compiling machine. Using
-march=native enables all instruction subsets supported by the local
machine (hence the result might not run on different machines). Using
-mtune=native produces code optimized for the local machine under the
constraints of the selected instruction set.
gccは -march=native オプションを使用するとビルドするコンピューターのCPUでサポートされてるすべてのinstruction subsetsを使用するようにしてくれるようです．
-march=native の展開
-E -vオプションを使えば簡単に出来ました．
-E
-E Stop after the preprocessing stage; do not run the compiler proper. The output
is in the form of preprocessed source code, which is sent to the standard
output.
Input files that don't require preprocessing are ignored.
-v
-v Print (on standard error output) the commands executed to run the stages of
compilation. Also print the version number of the compiler driver program and
of the preprocessor and the compiler proper.
ということでどんな結果が出るのか見てみましょう．
$ echo | gcc -E -v -march=native - 2>&1 | grep cc1 /usr/lib/gcc/x86_64-pc-linux-gnu/7.2.1/cc1 -E -quiet -v - -march=haswell -mmmx -mno-3dnow -msse -msse2 -msse3 -mssse3 -mno-sse4a -mcx16 -msahf -mmovbe -maes -mno-sha -mpclmul -mpopcnt -mabm -mno-lwp -mfma -mno-fma4 -mno-xop -mbmi -mno-sgx -mbmi2 -mno-tbm -mavx -mavx2 -msse4.2 -msse4.1 -mlzcnt -mno-rtm -mno-hle -mrdrnd -mf16c -mfsgsbase -mno-rdseed -mno-prfchw -mno-adx -mfxsr -mxsave -mxsaveopt -mno-avx512f -mno-avx512er -mno-avx512cd -mno-avx512pf -mno-prefetchwt1 -mno-clflushopt -mno-xsavec -mno-xsaves -mno-avx512dq -mno-avx512bw -mno-avx512vl -mno-avx512ifma -mno-avx512vbmi -mno-avx5124fmaps -mno-avx5124vnniw -mno-clwb -mno-mwaitx -mno-clzero -mno-pku -mno-rdpid --param l1-cache-size=32 --param l1-cache-line-size=64 --param l2-cache-size=6144 -mtune=haswell
こちらが平常時になります．
$ echo | gcc -E -v - 2>&1 | grep cc1 /usr/lib/gcc/x86_64-pc-linux-gnu/7.2.1/cc1 -E -quiet -v - -mtune=generic -march=x86-64
上の2つを比較してあげると -march=native でどのオプションが追加されたかがわかります．
-march=haswell -mmmx -mno-3dnow -msse -msse2 -msse3 -mssse3 -mno-sse4a -mcx16 -msahf -mmovbe -maes -mno-sha -mpclmul -mpopcnt -mabm -mno-lwp -mfma -mno-fma4 -mno-xop -mbmi -mno-sgx -mbmi2 -mno-tbm -mavx -mavx2 -msse4.2 -msse4.1 -mlzcnt -mno-rtm -mno-hle -mrdrnd -mf16c -mfsgsbase -mno-rdseed -mno-prfchw -mno-adx -mfxsr -mxsave -mxsaveopt -mno-avx512f -mno-avx512er -mno-avx512cd -mno-avx512pf -mno-prefetchwt1 -mno-clflushopt -mno-xsavec -mno-xsaves -mno-avx512dq -mno-avx512bw -mno-avx512vl -mno-avx512ifma -mno-avx512vbmi -mno-avx5124fmaps -mno-avx5124vnniw -mno-clwb -mno-mwaitx -mno-clzero -mno-pku -mno-rdpid --param l1-cache-size=32 --param l1-cache-line-size=64 --param l2-cache-size=6144 -mtune=haswell
ちょうど自分の環境ではこのようになります．
これだけでは面白くないのでこのオプションを生成してる部分のソースを見に行きましょう．
これの381行目 const char *host_detect_local_cpu (int argc, const char **argv) で見れます．かなり気合のオプション生成をしてますので見てみると楽しいです． AArch64では，実は内部で f = fopen ("/proc/cpuinfo", "r"); をやって /cpu/procinfo を読みに行ってて，それをゴニョゴニョしてオプションを生成してました．
gcc/config/${arch}/driver-${arch}.c というような規則性があるようですので，他のアーキテクチャのオプション生成もどうやってるか見て楽しむことができそうなので，ぜひ皆さん見てみてください．
SECCON 2017 Online CTF WriteUp
SECCON 2017 Online CTFにTeam Caffein H@ck の一員として参加しました． 今回ですが、自動車教習など色々とやることがありあまり貢献できませんでしたが，とりあえず2問解くことが出来たので，WriteUpを書きます． セキュリティエンジニアではないので基本的に解くのは Programming ジャンルです．
Run me!
Run me!
----- RunMe.py
import sys
sys.setrecursionlimit(99999)
def f(n):
return n if n < 2 else f(n-2) + f(n-1)
print "SECCON{" + str(f(11011))[:32] + "}"
-----
さてこちらの問題ですが，上のソースを適当に動かして上げればいいということだとでしょう．しかし，誰が見ても再帰が深すぎて終わる気がしません．適当に最適化してあげれば大丈夫です．f(n)が死ぬほど呼ばれることは解ると思います．f(n)の時の値をメモしてそれを参照しながら，f(11011)を求めてあげればいいと言うことが想像できると思います．競プロer御用達メモ化ですね．で、書いたソルバが下のソースです．
あとはこれを実行して出てきた数字時の下32桁を取ってSECCON{}で包めばflagになります．今よくよく見てみたら完全にフィボナッチ数列ですね．
Qubic Rube
Qubic Rube Please continue to solve Rubic's Cube and read QR code.
さて、伝統的QRコード問題の時間です．問題記載のURLを開くとこんな感じのthree.js使ってくるくる回る立方体を見ることが出来ます．
まず，すべてのQRコードを適当にスマートフォンでスキャンしてみたところ黄色のQRコードから謎のURLを得ることが出来ました．そこを開くと全人類がすべてを察することができるますね．
考察・戦略
ということで，この問題は模様付きRubic Cubeを解いて各QRコードを復元し、またどんどん次のQubic Rubeを解読していくという問題ですね．これを察してから初め5秒位はどうくるくる回すかを考えてましたが，立体操作ができるほど頭は良くないので別の方法で解くことにしました．とりあえずピクセル単位で画像を分割して，以下のような分割された9の画像からどうやってQRコードを復元するかということを考えたいと思います．
この9つの画像の並べ方はすべてで 49 * 9! = 95126814720 通りあります．この通りをすべてを試してるとかなりの時間がかかり現実的ではありません．そこで画像を以下のようなパターンに分けます．
角
辺
真ん中
それぞれは角、辺、真ん中にしか来ないのである程度の位置は確定することが出来ます．これを利用すると， 4! * 4! * 4 = 2304通りになります．ま、これくらいなら調べても良さそうな気がしますね．
解法
まず立方体の各面の画像を取得，それぞれを9分割し，色別にする．その後，辺/角/真ん中のブロックか判定をして、2304通りの画像を生成，それぞれのQRコードを読み取って読めるかどうか見ていくというように実装しました．
実装
すべてを解説すると時間が無限に解けるので画像の取得などポイントだけ話します．あとは気合で最後にあるソースコードを読み解いてください．
画像の取得
QRコードのページの実際にQubic Rubeを回してるソースを抜粋してきました． L15-L20にかけて画像をロードしてるところが見えますね．これには， /images/hogefugapiyo_{R, L, U, D, F, B}.png こんな感じで規則性があるので、それを利用してちょちょっと画像を取得します．昨晩0時位から突然単純にwgetで取得するとconnection refusedされてしまったのでwgetに --user-agent="Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)" オプションをつけて偽装して取得しました．
辺/角/真ん中判定
それぞれの端のピクセルをすべて覗いて {R, G, B} = {0, 0, 0} のピクセルを見つけます．黒のピクセルを含んでいる端の列の本数を数えて，4本なら真ん中/3本で辺/2本で角というように判定しました．
QRコードの読み込み
下が，2304通りの一つのQRコードの例です．
QRコードの読み取りですが，Python使うとこんな感じで読めます．高専プロコンの時といいzbarさんマジ神です．
そ〜すこ〜ど
ソースコードを最後に載せておきます．死ぬほど読みにくいですが、疲れてたんです．ご容赦ください．
終わりに
みなさんお疲れ様でした． 今回終わって，次はどこかでチームの人で集まってやりたいと思う今日この頃です．大会中オンラインだと連絡がとりにくすぎる．
#procon28
第28回全国高専プログラミングコンテストに10/7~10/10まで山口県周南市に行ってきました
結果
競技部門 第5位 特別賞
戦略
多角形パズルにおいて頂点と頂点はかならず接するという条件のもとに、ある頂点と頂点がくっついたときの周りの辺と角のそれっぽさを評価して、ビームサーチで解こうとした。9月下旬頃にこれまでの傾向から90度角の多いピースがでるだろうと予想して、そのような問題を作るプログラムを後輩に書いてもらったら、案の定、局所解に陥ることが多かった。そのため 人力 を使ってどのピースが間違っておかれているかを人間の目で選択し、それを取り除いた上で再探索をするようにして、局所解を乗り切るようにした。
当日までの振り返り
4月課題が出たときは「またパズルですか...」とか思ってモチベが上がらず、まじめに開発をし始めたのは5月ごろ。
まず初めの関門である環境構築、今年は一昨年くらいからの伝統を引き継ぐべく LinuxでQtを使うことにして、それに加えてboost,spdlog,zbar,opencvを使った。今回新入生が多めに入部してくれたのでそれぞれに環境を用意しなければならなくてとりあえず、manjaro linuxをインストールしてもらってそこで開発をしてもらっていたわけなんだが、細かい環境の差異によるコンパイルエラーが結構起きて、それを治してあげたりとかしてかなり開発の効率が落ちてしまった。当たり前だけど、ArchLinuxの兄弟分のManjaroLinuxも遠慮なく最新のパッケージを降らしてくれるわけで、 pacman -Syu したらビルドが通らなくなったとか言われたりして笑えなかった。そんな中ArchLinuxArchiveを使えばいいやんとかいうことを思いついて、全員のPCにArchインストールバトルを敢行して、環境構築の闇は乗り切った。この手法ArchLinuxを使うところ以外には全く問題がないと思うので、ぜひ来年のプロコンの開発でも使ってほしい。
いつもの通り開発がつらいのは当たり前だが、今年は隣で"Bird Finder"(あの鳥の鳴き声の位置と種類を特定してHololensに表示するやつ)の開発をしており、絶えず鳥の声が大音量で部室に流されるとかいう非常に劣悪な環境で開発をしてたので余計につらかった。
そんなこんなで当日は魔材をきめてデスマしつつも、パズルを並べる力を維持するような睡眠をとって死ぬ気で開発をして、なんとか5位特別賞を取ってくることができた。多分5台だったか6台くらいを壇上に持ち込んですべてのPCを使って問題を解かせたってのがインパクトあったのかなとか思ってたり。
あ、2日目にあおみちゃんと名刺交換チャレンジに成功したんですよ。やったね。
食事部門
プロコンで食べた食事(外食のみ)を一通り紹介。
0日目 昼飯 徳山駅前の商店街の「ポパイ 喫茶店」
写真を撮り忘れてた()
0日目 夕食 徳山駅前の商店街のラーメン屋
1日目 夕食 ボンディ 下松店にて
2日目 夕食 国際交流会でどこかの中華料理屋さん
写真を撮り忘れる失態
3日目 昼飯 広島駅の駅ビルに入ってるお好み焼き屋さん
この写真もありませんでした
観光部門
高専プロコンといえば、観光。前回の伊勢大会では伊勢神宮に参拝したりできたわけだが、今年は徳山。徳山高専の知り合いに聞いても徳山は観光する場所なんてないらしく、今回は徳山から離れ広島の厳島神社へ行ってきた。
そこで凶を引くことができて、これはむしろ最高に運が良かった(?)のではとか思ってる。
まとめ
- ArchLinuxArchiveを使った開発環境の統一は再現性があってすごく良いので使おう
- おいしいものがたくさん食べれてよかった
これは SPC同好会 Advent Calendar 1日目の記事です。
