読者です 読者をやめる 読者になる 読者になる

ジョイジョイジョイ

ジョイジョイジョイジョイジョイ

最小全域有向木(m log n)

明日、KMC の組合せ最適化読書会でやる予定なのですが、少し調べた限りでは日本語の解説が見つからなかったので書いてみます。(注:組合せ最適化本体には O(nm) のアルゴリズムしか載っていません。)

 

こういうアルゴリズムに慣れていない人向けに書いたつもりなのでプロ各位にはまどろっこくて分かりづらい表現になったかもしれません。ゆるして。

最小全域有向木について

辺にコストのついた有向グラフが与えられて一つの頂点が指定されたとき、その頂点を根とする全域有向木でコスト最小のものを求める問題です。

 

根用の頂点を追加して、各点にコスト INF の辺を張れば頂点を指定しない最小全域有向木が解けます。コスト 0 で張ると最小有向森です。

 

有名な解法に Edmonds / Chu-Liu のアルゴリズムがあります。この計算量は O( nm ) で、組合せ最適化や Spaghetti Source - 最小全域有向木(Chu-Liu/Edmonds) に載っています。今から説明する O( m log n ) の解法は Tarjan [1977] によるもので、このアルゴリズムの亜種(というか高速化しただけ)です。

アルゴリズム

  1. 根以外の頂点を適当に選びます
  2. 今いる頂点 v に入ってくる(自己ループでない)辺のうちコストが一番小さい辺 ( u -> v ) を取ります。今いる頂点が圧縮された頂点なら、もとのサイクルで v に入ってくる辺を使う辺から除きます。u に移り、( u -> v ) を使う辺に追加します。
  3. 使う辺でサイクルができたら、サイクルを一点に圧縮します。このとき、サイクル外からサイクル上の頂点 w に入ってくる辺のコストを、w に入ってくるサイクル辺のコストだけ減らします。
  4. まだ根と繋がらなかったら 2 に戻ります。繋がったときは、他に頂点が無いなら終了。まだあるなら適当に頂点を選んで 2 に戻ります。

やることはすごく簡単です。少し下で解説をしているのでこれを読んで分からなければそっちを読んでみてください。(むしろこれだけで分かったらすごい)

解説

有向木では、根以外の入次数は 1 です。(もちろん根は 0 です。)なので、各頂点について入ってくる辺をちょうど一つ選ぶわけです。このアルゴリズムでは、手順 2 で貪欲に一番コストが小さい辺を選んでいっています。サイクルができなければこれが一番良いことはすぐに分かると思います。

 

厄介なのはサイクルができたときです。サイクルができた時は、そこで詰んでしまうので、サイクルを「開いて」やらなければいけませんf:id:joisino:20170111142108p:plain

サイクルに繋がる辺を選ぶ訳ですが、上の図のように開くと総コストが d - c だけ増えます。(コスト c の辺を使うのをやめてコスト d の辺を使うため。)このアルゴリズムではこのコストについて貪欲に小さいものを選びます。アルゴリズムの手順 3 で「このとき、サイクル外からサイクル上の頂点 w に入ってくる辺のコストを、w に入ってくるサイクル辺のコストだけ減らします。」と言っているのはそういうことです。(「サイクル外からサイクル上の頂点 w に入ってくる辺のコスト」は図の d に対応し、「w に入ってくるサイクル辺のコスト」は図の c に対応します。)

 

サイクルができるたびに上のように対応して、サイクル(だったもの)はそれ以降変更しないように一点に圧縮してしまいます。(これは、正当性の証明のところで示すようにサイクルの一辺以外を全て含むような最小全域有向木があるので OK です。)

 

入ってくる辺を貪欲に選んで、サイクルを貪欲に切って圧縮するというのは Edmonds のアルゴリズムも同じです。違うところは、Edmonds では全部の頂点について入ってくる辺を選んでから圧縮するのを繰り返しているのに対し、このアルゴリズムでは DFS の要領で一つずつ頂点を処理していくことです。

 

現在の頂点から辺を逆に辿ってパスが伸びるか、サイクルができても圧縮してしまうので、現在の処理している辺たちは常にパスのように見えることになります。

 

こうすると、辺を辿るたびに、パスが 1 つ伸びるか、サイクルができて、サイクルの大きさくらいの頂点が消えるので、 2n ステップくらいで止まることが分かります。

正当性の証明

Edmonds のアルゴリズムの正当性の証明とほとんど同じです。そっちを知っている人はこれも証明できると思うので自力でやってみてもいいかもしれません。

 

証明は圧縮する回数についての帰納法で行います。

 

圧縮する回数が 0 回(圧縮しない)とき

これは、解説のところでも言及しましたが、ほとんど明らかだと思います。

このアルゴリズムで得られた有向木 T と、任意の有向木 S を比べたとき、各頂点に入ってくる辺同士についてコストを比べると、T の辺は入ってくる辺の中で一番コストが小さいものを選んでいるので、もちろん T の辺のコストが S の辺のコスト以下になります。ということは、総和をとっても T 全体のコストは S 全体のコスト以下です。

 

圧縮する回数が k + 1 回のとき

まず、最初に圧縮することになるサイクルを C とします。 C は L 本の辺からなるとします。

 

ここで、なんとサイクル C の辺のうち、L - 1 本の辺を使う最小全域有向木が存在することがいえます。(この証明は組合せ最適化にも載っています。慣れない人には少し難しいかもしれないので分からなかったら認めてしまって次に進んでも良いかもしれません。飛ばす場合は「補題の証明終わり」というところまで進んでください。)

 

背理法により補題を証明します。

最小全域有向木のうち、サイクル C の辺を使う本数が最も多いものを A とします。C の辺のうち K ( >= 2 ) 本使わないがあると仮定します。

C の辺のうち、A で使われていない辺を、一周回る順番に ( a_1, b_1 ), ..., ( a_K, b_K ) とします。ここで、i = 1, 2, ..., K について A には b_i から b_{i-1} にパスがあることを示します。( i = 1 のときには i-1 は K を表していると思ってください。)

( a_i, b_i ) が使われていないのだから、A には b_i  に入ってくる他の辺 e があるはずです。

e を使うのやめて ( a_i, b_i ) を使うことにしてみます。

( a_i, b_i ) のコストは b_i に入ってくる辺の中で一番小さいのでコストの総和は変更前以下になります。変更後もちゃんと有向木だったとすると、コストが真に小さくなっても A が最小であることに反するし、同じでも C のうち使う辺の本数が 1 本多いので、 A のとり方に違反します。

考えられるのは使う辺を変えたことでサイクルができてしまったということです。

これは、A において、b_i から a_i にパスがあったということです。a_i からそのパスを逆向きにたどって行くと以下の図から分かるように b_{i-1} にたどり着きます。(入次数が 1 なので一意にたどれます。また、(a_{i-1}, b_{i-1}) は使わない C の辺のうち一つ前の辺なので、間の辺は全て A でも使われています。)

f:id:joisino:20170111211948p:plain

つまり、A 上には b_i から b_{i-1} にパスがあるということです。(b_i から a_{i-1} へのパスの一部分。)

これでパスの存在は示せました。

しかし、これは b_K からb_{K-1} にパスがあり、b_{K-1} から b_{K-2} にパスがあり、...、b_1 から b_K にパスがあるということになり、A にサイクルがあるということになります。

これは A が有向木であるという仮定に反します。

よって、最小全域有向木のうち、サイクル C の辺を使う本数が最も多いものは L - 1 本の辺を使うということになります。

補題の証明終わり

 

もとの証明に戻ります。圧縮する回数が k+1 回のときにアルゴリズムで得られた有向木が最小全域有向木であることを示すのが目的でした。

 

このアルゴリズムで得られた有向木を T とし、サイクル C を圧縮したときにできるグラフ(以下圧縮グラフと呼びます)で T に相当する有向木を T' とします。帰納法の仮定より、 T' は圧縮グラフでの最小全域有向木です。

補題により存在が示された、C の辺のうち L - 1 本を使う最小有向木を T* とし、圧縮グラフで T* に相当する有向木を T*' とします。

ここで、 T のコストは T' のコストにサイクル C に含まれる全ての辺のコストの和を足したものとなります。T* についても同様に T*' のコストに C のコストを足したものになります。

これは、 T' で C に相当する部分以外のコストは同じで、 C は、1 本以外全て使うことになりますが、使わない辺については C に入ってくる辺のコストの変更によって調整されているので、このようになります。

よって、( T のコスト ) = ( T' のコスト ) + ( C のコスト ) <= ( T*' のコスト ) + ( C のコスト ) = ( T* のコスト )

となり、 T が最小全域有向木であることが分かります。真ん中の不等号は T' が圧縮グラフ上での最小全域有向木であることからです。

f:id:joisino:20170111225913p:plain

 以上、帰納法によって正当性が示されました。

 

計算量

計算量を調べます。

解説のところで言及したように、1 ステップ ごとにパスが伸びるか、頂点がマージされて減るのでアルゴリズムの手順 2, 3 を実行する回数は O(n) 回です。

 

各頂点について入ってくる辺を隣接行列でもって愚直に管理するとします。手順 2 で最小値を求めるのは毎回 O(n) で、これは O(n) 回行われます。手順 3 で圧縮するのも、1 つの点につき O(n) でマージできて、合計高々 n 頂点しかマージされないので、結局全体の計算量は O(n^2) になります。

密グラフでこのアルゴリズムを走らせたいときはこれ以上速くなりようがないのでこれで終了です。

 

次に疎グラフで O( m log n ) を達成するやり方を考えます。

dijkstra 法などを学んだ人ならなんとなく分かると思いますが、辺をヒープ(prioirty queue)で管理します。

こうすると手順 2 で最小値を求めるのは毎回 O(1) になります。

 

問題は圧縮です。ヒープをうまくマージしたりコストを一様に減らしたりする方法なんてあるのかと思いますがあります。

一つには、マージテクを使うとできます。これで O( m log n + n log^2 n ) とかになります。

もう一つには、meldable heap というものを使います。これはマージが効率よくできるヒープのことで、leftist heap や skew heap などがあります。blog - Leftist Heap & Skew Heap に詳しいのでそちらを参照してみてください。これで O( log n ) でマージできます。また、コストを一様に減らす方法ですが、ヒープのノードに一様に足された数を持っておいてマージするときに遅延伝播すればうまくいきます。(segtree の遅延伝播と全く同じです。)これで全体で O( m log n ) になります。おめでとうございます。

 

具体的な実装例は使い道のところを参照してみてください。

 

ちなみに、fibonacci heap を使うとマージが O(1) でできます。コストを一様に減らす解析は読んでないので良く分かっていませんが Gabow et al. [1986] によると全体で O( m + n log n ) になるらしいです。誰か読んで分かりやすく教えて。

使い道

競技プログラミングでは今のところあまり実用性はないかもしれませんが、とりあえず首都(The Capital | Aizu Online Judge)をアルゴリズムパンチで殴り倒せます。

 

実装例です。多めにコメントを書きました。MSA という関数が、 r を根とする最小全域有向木のコストを求める関数です。「ここが本質です。」と書いてあるループ部分が最小全域有向木のメインの部分です。

The Capital ( AOJ 2647 )

 

終わりに

この記事を書くまでは最小全域有向木は無向の最小全域木よりも(少なくとも競技プログラミングで使うようなアルゴリズムでは)有意に計算量が大きいものだと思っていたんですが、割と簡単なアルゴリズムで似たような計算量が達成できるのにビックリしました。

最小全域有向木を使う問題はあんまり見ないですが、n = 10^5 とかで割と簡単に書けるので使いようがあるんじゃないかと思いました。(浸透しないとただの知識ゲーだけど)

 

 

ここが分からないとかここ間違ってるよとかあれば気軽に言ってください。

最後まで読んでいただきありがとうございました。

 

(1/11 23:33 マージテクでも少しいい感じにできるよということなど少し追記しました)

参考文献

[1] B.コルテ, J.フィーゲン [2012]: 組合せ最適化 第二版. 丸善, 2012, 第 6 章.

[2] Gabow, H.N., Galil, Z., Spencer, T., and Tarjan, R.E. [1986]: Efficient algorithm for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6 (1986), 109-122

[3] Tarjan, R.E. [1977]: Fining optimum branchings, Networks (1977), 25-35

2015ふりかえりと2016めも


昨日振り返りするの忘れていたので元日に振り返りと目標どっちも書こう

 

2015年の振り返り
こんなことを買いていたのでその振り返り

 

大学に入る
はい

 

赤くなる
TC 1584 -> 1827 (+243)
CF 1876 -> 2150 (+274)
うーんダメ
一瞬だけCF赤くなったけど色基準変更されてレートも落ちてしまった
来年はちゃんと精進して赤くなるぞ

 

ゆゆ式二期が決まる
ダメですね......

 

良い一年だったけど目標は全然達成できてないですね
2015年は全然競プロできなかったので今年は精進するぞ

 

2016年めも
TC,CF赤くなる
ゆゆ式二期が決まる 

櫟井唯ちゃんの画像を無限に生成する話

いくら待てどゆゆ式二期の発表がないのでそろそろ僕の櫟井唯ちゃん資源が枯渇してしまいそうです

そこで今話題のニューラルネットワークに唯ちゃんの画像を無限に生成してもらうことにしました

 

とりあえずこちらがデモです(設定の読み込みにかなり時間がかかります)

Mugen Yuichan

 

ランダムに生成したサンプルです

一応はっきりと唯ちゃんだと分かる

f:id:joisino:20150909230636p:plainf:id:joisino:20150909230646p:plainf:id:joisino:20150909230652p:plainf:id:joisino:20150909230656p:plainf:id:joisino:20150909230700p:plain

 

使ったのはDenoising Autoencoder(DAE)

ふつうのAutoencoderの入力にノイズを加えて学習させるだけです(今回はガウス分布のノイズを加えました)

ノイズ除去に使えたり生成モデルを作れたりします

DAEについては深層学習 (機械学習プロフェッショナルシリーズ)を参考にしました

 

作り方

まずはゆゆ式の本編から唯ちゃんの顔部分だけ切り抜きます

この作業はこのページを参考にさせていただきました

ご注文はDeep Learningですか? - kivantium活動日記

ゆゆ式1話と2話でだいたい1000枚の唯ちゃんの画像が手に入りました

 

次にニューラルネットワークの構成ですが、夏季セミのときに作ったのを流用しました

JOI夏季セミナー2015チューター記 - ジョイジョイジョイ

 

ネットワークは3層で、入力画像が96*96*3、中間層が128、出力画像が96*96*3です。

本当はもう少し中間層を増やしたかったのですが公開のときのサイズの都合上128にしました(これでも重い)

 

あとは普通に学習させるだけ

学習方法はSGD+Momentum(0.9)

学習係数は0.01

デモのネットワークはだいたい100epochくらいのもので、学習は1時間くらいで終わりました

 

やりたいこと

多層にすると精度上がるかなぁ

変分自己符号化器(VAE)を使ってみたい

自前のライブラリだと速度や実装コスト面でつらいのでそろそろライブラリの使い方を覚えたい

 

 

最後にリポジトリです

github.com

JOI夏季セミナー2015チューター記

 

JOIの夏季セミナーにチューターとして参加してきました。

本が6冊なのになぜかチューターは5人だったので僕は『プログラミング言語の基礎概念』と『深層学習』の2冊を担当することになりました。

 

1日目

catupperと共にヌエックに到着

自己紹介する(チューター→生徒の順)

ぼく「最近興味があるのは深層学習です」(伏線)

本決めとかする

セミナーはじまる(プログラミング言語の基礎概念』を担当)

生徒優秀すぎるでしょ...(何もできずただ座っている)

ヌエックのご飯おいしい

1日目は談話室なかったのでちょっと集まってすぐ寝る

 

2日目

セミナーと講義

師匠に私は熟女好きですされる

わたあめ大人気

今日からは談話室が使える

がっこうぐらしをつけながら枯山水をやる

枯山水たのしい

hogloidの徳の高さには勝てなかったよ...

ここでめぐねえが死ぬ

寝る

 

3日目

catupperの班(関数プログラミング)と相部屋になる

絵しりとりなどする

catupperにHaskellを教わる

ABCの問題をHaskellで解く

Haskell楽しい('ω' )三('ω')三( 'ω')

夕食時、わたあめ機が壊れていた(けっきょく食べられなかった)

シンデレラ見たかったけど談話室は24時に閉まるので見られず死

この日は談話室では特になにもしなかった

 

4日目

深層学習と相部屋になる

potetisenseiがkaggleの犬と猫を見分けるのをやるらしい

面白そうなので勝負を申し込む

画像読み込む段階で挫折しそうになる

potetiにライブラリを教えてもらってなんとか読み込む(これをつかった)

とりあえず昔書いた単純なパーセプトロンに学習させてみる

49.1%

ランダムにラベルつけた期待値の方が高いじゃん...

MNIST(手書き数字認識)を学習させたら9割超えるんだけどなぁ...

Deeplearningの必要性を感じたので畳み込みニューラルネットワーク(CNN)をpotetiから一通り教わる

協力プレイしない?という話になる

基礎はpotetiが既に作っていたのでぼくは畳み込み層の逆伝播とプーリング層を実装することに

セミナーが終わったので談話室で実装することに

hogloidとdegwerがウェイについて話している

hogloidはウェイ

catupperはウェイ

人類皆ウェイ

全然終わらないのでぼくの部屋で実装することに

開発の都合上gitを入れることに

パソコン弱いのでgitインストールできない(結局potetiとcatupperにめっちゃ手伝ってもらった)

アイマス曲を流して歌いながらぐだぐだ実装する

いつのまにか部屋にめっちゃ人が集まっていた

そしてだんだん外が明るくなりはじめる

potetiがスライド一通り作り終えたようなので一緒に考えながら実装する

一応完成した

20分くらい学習させてみる

50.0%

 

5日目

結局寝ないまま5日目の朝を迎える

potetisensei「深層学習で死にそう」

そのあとの紆余曲折はだいたいここに書いてあります

www.slideshare.net

(ここでの正解率は全てMNISTの正解率で結局犬と猫のにはチャレンジできなかった)

 

ア、皆の発表ちゃんと聞いてたからね?

ここでdegwerに私は熟女好きですされる

 

まぁ一からCNN書いて理解も深まったし、なにより動いてくれたのでめでたしめでたし

 

 

...?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

K理事長「分からなかったことに納得するまでが夏季セミナーです。」

 

6日目

基本的にレイヤーの実装が良くないというはなしになる

また設計やり直すか?とか話す

 

7日目

 

ConvNetJSと比べてパフォーマンスが悪いなぁという話になる

ConvNetJSでは活性化関数にReLUを使ってるけどこちらでReLUを使うと重みが発散して死ぬ

ConvNetJSのコードを見て学ぶ

重み制限を実装する

このおかげでReLU使って重み発散しなくなる(ただしパフォーマンスは悪い)

6層のCNNでReLU使って79.66%が出る

逆伝播のデルタを初期化していないという深刻なバグを見つける(これのせいで変な方向に重みが動いていた)

直したけどパフォーマンス全然変わらない

これもう分かんねぇな

potetiがレイヤーの設計改めて実装する(プロ)

 

8日目

新しい設計でテストする

4層だと学習するんだけど6層だと学習しない

ConvNetJSの設定みて初期値とか学習率を変えるとめっちゃパフォーマンスよくなる(ただし依然6層では学習しない)

でもまだConvNetJSの方がパフォーマンス良い

向こうはAdadelta使ってるからだろうなという結論になる

とりあえずmomentum実装する

まぁいい感じ

momentumの符号逆であることに気付く

直したけど精度変わらず

これもう分かんねぇな

momentum有りだと6層で学習するようになる

 

9日目

momentum有りの6層で94.20パーセントが出る(大勝利)

そろそろ犬と猫に挑戦してもいいんじゃない?

犬猫は80パーセントを目標にして、達成したらやめると宣言する(この時点で全く手を付けていなかったので80パーセントという数字は適当)

この見切り発車を後で後悔することになる

 

biasの更新に学習率をかけていないというバグをみつける

バグを直すを学習が遅くなる

これもう分かんねぇな

 

10日目

Adagradを実装する

Adagrad最強(めっちゃ学習が速くなった)(しかもReLUでもいい感じに学習する)

Pythonインストールしてpotetiのスクリプトいじって犬と猫の画像をリサイズする

画像のサイズ128*128にすると計算遅すぎてまともに学習しないので32*32に

とりあえず4層(input->conv->pool->fully->output)で学習させてみる

53.89パーセント(死)

一応統計的に有意に学習してます(白目)

8層(input->conv->pool->conv->pool->conv->pool->fully->output)で学習させる

59.9パーセント

厳しすぎる

8層に3時間くらい学習させて64.057パーセント

とりあえず学習させながら寝る

 

11日目

朝起きて確認

68.960パーセント

うーん

フィルタ増やしたいけど増やすと計算が遅くなる

計算資源の重要性を思い知る

amazonEC2と自宅のパソコンを使っていろいろパラメータをチューニングする

9層のCNN(input->conv->pool->conv->pool->conv->pool->fully->fuully->output)で71.794パーセントが出る

このあたりで80パーセントにしたことを後悔しはじめる

72パーセントとか言っとけばよかった(くっ)

 

12日目

画像の大きさを36*36にして、そのうちランダムで32*32を切り取るようにする

チューニングしながら学習させまくる

 

13日目

なかなか記録伸びず

9層CNNに40時間くらい学習させて75.874パーセントがこの時点で最高

dropout実装するか~という話になる

dropout実装する(二人で分担した)

とりあえず明日まで昔のCNNに学習させて、無理そうだったらdropout付きのに切り替えることにする

 

14日目

8epoch(50時間くらい)終わって77.794パーセント

つらい

というか8epochに50時間かかるの遅すぎませんかねぇ(1epochで2万画像)

ちょっと(3割くらい)プログラム高速化してdropout付きのに切り替える

一応昔のも走らせ続ける

 

 

15日目~18日目

ひたすら学習させる(放置)

6epoch 74.686パーセント

8epoch 77.394パーセント

9epoch 77.909パーセント

10epoch 79.268パーセント

12epoch 78.869パーセント

13epoch 79.806パーセント

 f:id:joisino:20150829201021p:plain

 

 \パンッ/ヨッシャアアアアアアアアアアアアwwwwwwwwwwwwww(高い声で)キタァwwwwwwwwwwウワァヤッタアアアwwwwwwwwwwwwwwwww

 

くぅ~疲れましたw これにて完結です!
実は、potetiに競争申し込んだら協力を持ちかけられたのが始まりでした

云々

 

最後にまとめ

 

まとめ

Deeplearningの闇

  • バグってなくてもパラメータ次第では学習してくれないのでバグのせいかパラメータのせいかの見分けがつかない
  • 下のようなCNNの構成とパラメータを探してもあまりない(実験系の論文や強いライブラリを使ったものはあるけど計算資源の都合上真似できない)
  • バグってても学習するのでバグってることに気付かない
  • 計算資源を無限に欲してしまう
  • 深層学習のアルゴリズムの解説に「理屈はないけど経験上うまくいく」というのが多くて結果の予測がむずかしい

 

最終的なCNNの構成

  • input 32*32 channel 3
  • conv size:5*5 channel 16
  • pool size 2*2 stride 2
  • dropout 0.25
  • conv size 5*5 channel 32
  • pool size 2*2 stride 2
  • dropout 0.25
  • conv size 5*5 channel 64
  • pool size 2*2 stride 2
  • droput 0.25
  • fully channel 64
  • dropout 0.5
  • fully channel 2

活性化関数は全てReLUで最後だけsoftmax

学習係数は0.01

学習方法はAdagrad

画像を全て36*36にリサイズして、うち32*32をランダムで選んで学習させた(推測時は16通り全て試して多数決)

 

ちなみにdropoutなしの同じ構成は20epoch学習させても77.886パーセントでした

 

構成はnagadomi/kaggle-cifar10-torch7 · GitHubを多く参考にしました。

 

僕たちのリポジトリ

github.com

 

 

誘ってくれたアンド最後まで付き合ってくれたpotetisenseiへの感謝の言葉で終わりにします

サンキューポテチ!

PCK2014本選参加記

1日目

  • 起床成功
  • 伊丹空港到着
  • 飛行機でウキウキ
  • 会津
  • @DEGwer3456と@namonakiaccountに会う
  • 優勝おめでとうございますと伝える
  • 実際優勝した(完全にプロ)
  • バスで大学へ
  • 受付
  • 開会式
  • 競技
  • 7完3WAだった(5位)
  • バスでホテルへ
  • @potetisenseiと初めて会う
  • 神秘的だった
  • 交流会ではJOIerとばかり交流する
  • 部屋へ
  • @HIR180と@yokozuna_57の部屋に風船が集まっているらしい
  • 持っていく
  • そのままIs部屋に居つく
  • @satashunから高槻駅やよい軒閉店の知らせを聞いて驚愕する(後で調べたらリニューアルらしい)
  • 雑談していたら皆倒れていったので部屋に戻って寝ることにする

 

2日目

  • 起床成功
  • 朝食
  • 朝食解いた人は意外と少なかった
  • バスで大学へ
  • 自由時間
  • 鶴ヶ城
  • ラーメン食べる
  • おいしい
  • 大学に戻る
  • @potetisensei「Is、三上和馬、DEDwerの7名が写真撮影に間に合わない」
  • 写真撮影開始
  • 予選の成績順で並んだので前の方スッカスカ
  • JOIerは闇
  • 並び調整してる間に7名到着
  • 撮影
  • 大学見学
  • 表彰式
  • 5位(再掲)
  • 三上和馬のミドルネームの一部と化す
  • 会津若松駅
  • 高槻
  • 帰宅

 

感想

  • たいしたミスも無かったのに5位なのはつらい
  • 求められる速解き力、実装力
  • 受験終わったら競プロ精進します

PCK2014予選参加記

はじめに

  • 炒めスズランとして参加した
  • チーム名は相方が考えた
  • 由来を聞いたところ「鈴蘭って綺麗やん?」ということだそう
  • 何で炒めたのかまでは聞き出せなかった
  • 結局六完(1,2,3,4,6,7)だった

 

1~3匁

  • 読む
  • 書く
  • 提出する
  • AC

4匁

  • 読む
  • 書く
  • 提出する
  • 出 力 形 式 エ ラ ー
  • 絶望
  • よく分かんない
  • 改行を消して提出
  • 出 力 形 式 エ ラ ー
  • 大絶望
  • 予選落ち不可避
  • もうダメ
  • 問題文を1000回読みなおす
  • 最後の空白いらないっぽい?
  • 消す
  • 提出
  • AC

5匁

  • 読む
  • 書く
  • 誤読に気づく
  • どうしよう?
  • 飛ばそう
  • かなり動揺している

6匁

  • 読む
  • 書く
  • 提出する
  • AC

7匁

8匁

  • 7匁でかなり時間を使ってしまった
  • 時間ないよう...
  • ふぇぇ...
  • 読む
  • 7匁より簡単じゃん
  • 爆速で書き始める
  • 時間切れ
  • あと5分欲しい人生だった