CodeFestival 2014 上海ツアー 参加記

0日目 (焼肉・前泊)

・ディスプレイとボードゲームがamazonから届くのを待っていた。（注文していたはずが、注文確定していなかったらしく、お急ぎ便で注文し直した）
・届いた。マルチディスプレイ快適すぎる
・TLはimosさんの結婚と、変数名の話しで盛り上がっていた
・へい
・ヒュルヒッる
・焼肉＠五反田にお邪魔させていただく
・チヂミが美味しかった
・８時に羽田とかTLEを避けられないので、空港直結ホテルに前泊

1日目 (出発・観光)

起きました。間に合うかな。 #上海ツアー

— 誰か氏＠23 (@snuke_) 2014, 12月 19

・８時前に堂々の起床✌︎✌︎✌︎✌︎✌︎
・K4PCの優勝賞品の「目が動くアイコン」の権利をトイレ５個さんに押し付けた

@snuke_ 本当に本当にありがとうございます！きゅうりさんのアイコンにするとゆう夢が叶いました！感涙

— トイレ5個さん (@chako0407) 2014, 12月 20

・飛行機(ANA)
・個人用画面があったので短いアニメを何本か見た
・上海にはすぐ着いた
・バスでホテルまで移動
・良いホテルだった
・観光
・謎のトンネルを通った
・謎の塔は待ち時間が長すぎて登れず
・まぁ高いところに行くのは飛行機で満喫したので良い
・晩御飯はクルーズで中華
・ターンテーブルにyosupoとkitayutaの顔を置いて回した
・人の顔をむやみに回転させてはいけない（腕をクロスさせる絵文字）
・焼きそばは山菜（ソース焼きそばをイメージしてはいけない）
・食べ始めるのが早すぎてクルーズが出港する前に食べ終わった
・asiさんに「中国にちなんだゲーム」としてGangnam StyleのDJゲームをオススメされたけど、残念ながらあれは韓国なんだよなぁ
・クルーズから出るところで、レーザーを照射してくる「レーザーレーザー安い安い」おばさんが居たけど「安い」じゃあ値段は分かんないんだよなぁ
・ホテルに帰る
・ホテルと同じ連結成分にローソンがあった
・とりあえず水を２本買った
・頑張ってtwitterに繋ぐ
・呟いた瞬間にkitayutaがクズみたいなリプライを飛ばしてきた、顔を回すことも辞さない
・1104でボードゲームを用意してお誘いtweetをする
・初訪問はtosさんでした
・５本のきゅうりなどをして遊んだ
・完全に名前買いだったけど、良いゲームだった
・歯磨きに水道水を使いたくなかったのでペットボトルの水でやった
・かなり少量の水で歯磨きをする一般的なテクを身につけた
・コップに水を少し入れて、歯ブラシをすすぎ、柄の部分に沿って水を流しながら捨てることにより効率良く全体を洗浄できる

２日目 (コンテスト)

・朝ごはん(バイキング)を食べすぎた
・ホテルの朝ごはん、とても美味しかった
・餃子が特に美味しかった
・すぐにお昼ご飯
・すでにお腹がいっぱいだったのでちょびちょび食べる
・小籠包の下半分を揚げた感じのものがとても美味しかった
・ただし、カロリーの味がした
・中国ではどこ行っても円卓が出てくる
・回転扉も至る所にあるし、中国はなんでも回転させたがる傾向にある？
・円卓にまつわる問題が作問されていた
・円卓でルーレットをしたりしてたら料理を持ってきたウェイターさんが困っていた
・あと、チャーハンもよく出てきた
・ご飯と卵とミックスベジタブルを炒めた感じ
・美味しい！ってことはないけど、少なくとも絶対まずくはないので安心感がある（自分は好き嫌いが多い方なので結構慎重）
・上海交通大学に向かう
・「交通」はネットワークとかそういう類の意味も表すらしい
・会場につく
・去年と相変わらず狭い
・komakiさんはいつも通り床
・しめじさんは寝そべって参加していた
・英語onlyこわい
・開始
・コンテストの参加記
・終了
・omeさんとかなり競り合っていたけど、現役力により優勝した
・準急は失敗しても優勝する(CodeFomula参照)ため、準急を止める手段は税金しかない
・表彰式で突然英語のコメントを求められ、つらみ
・懇親会
・あんまり時間がなかったけど中国勢とちょっと話せた
・ホテルに帰投
・omeさんとデパートに行く
・横断歩道を渡る一般的なテクを身につけた
・現地の横断歩道を渡るプロが複数人渡るのを待って、人と人の間の位置をキープしながら渡ると安全
・ココイチと寿司名人とたこ焼き屋があった
・背の低いファミマがあった
・部屋に帰ってボードゲーム会
・昨日より人が多くて、２卓立った
・きゅうり組とその他という感じだった
・モダンアートとムガルをやる
・順番決めでtopcoderじゃんけんをやったら勝ったぜいえい
・chokudaiさんがマラソン力を発揮していてかなり強かった
・良いゲームであった
・寝る

３日目 (観光)

・朝は寝ていたので、本屋には行かなかった
・結構面白そうだったので行きたかった感がある
・朝食は洋食にしてみた
・ゴマ団子超ウメェ！
・爆速で売り切れていて１個しか食べられなかった；；
・観光
・カクカクした橋を渡った
・噴水から虹が見えたのでレインボーブリッジだった
・一般に橋と呼ばれているものは、切っても連結性が保たれることが多いため、橋ではなくただの辺であることに気づいた
・上海 老街(老害ではない)でお土産タイムだけどなにも買わず
・上 海老 街という区切り方をすると美味しそう
・北京ダックの店
・上海ビールはビールを水で薄めた味がした
・小籠包を作った
・スープが入っていなかったため、おいしさが0だった（参考URL）
・晩御飯を食べた
・上海蟹を食べるの難しかった
・みんなが上海蟹にてこずっていたせいで他の料理を食べるスピードが遅く、円卓の上が皿まみれになっていた
・小籠包によりテーブルがおいしくなった
・上海雑技団
・めっちゃ面白かった
・特に帽子のやつは笑った
・ぽよさんに「帽子のかぶせ合いのやつ、りんごさんとすぬけでやってそう」と言われた。やってそう
・トランプを無限に撒き散らすショー、片付けを箒を使わずN人が手で拾って回収していて大変そうだった
・「トランプおばさん他のメンバーから嫌われてそう」
・ホテル
・コンビニに日本のビールが売っていたけど結構安かったので買った
・日本のビールはうまい（海外のエールビールとかはもっとうまい）
・またボードゲーム
・まだあまりやっていなかったラブレターをやる
・一瞬でクソゲー認定される
・理不尽クソゲー楽しすぎたw
・ゲーム概要を言うと「カードを引いてyosupoが負ける」ゲームです
・深夜に最適なゲームでした
・しばらく雑談をして解散
・最後の方、yosupoが完全にマルコフ連鎖で会話をしていた
・添い寝に失敗した

４日目 (帰宅phase)

・朝食を解いてしまった
・空港で買い物
・お腹が減っていたのでおやつを買う
・80元くらい余っていたのをなんとか使い切って残り9角まで減らせた
・帰りの飛行機が爆速すぎて、見てたムービーが最後まで再生できなかった
・解散
・帰り方が難しそうだったのでとりあえず準急に付いていく
・京急爆速すぎて一瞬で帰宅できた
・晩御飯は鴨南蛮を食べた、激ウマ
・完

まとめ

超楽しかった！
リクルートさんほんと感謝です！お疲れ様でした！

みなさんへ：参加記を書くまでがツアーですよ＾＾

文字列の頭良い感じの線形アルゴリズムたち３

昨日の記事の続きです。

Z algorithm

文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
例えば、

aaabaaaab
921034210

こんな感じです。

Z algorithmのテクニックはManacherとよく似ています。ですので、以下の解説記事を読む前に少し考えてみると分かるかもしれません。

さて、結論から言うと、Z algorithmのコードは以下のようになります。

A[0] = S.size();
int i = 1, j = 0;
while (i < S.size()) {
  while (i+j < S.size() && S[j] == S[i+j]) ++j;
  A[i] = j;
  if (j == 0) { ++i; continue;}
  int k = 1;
  while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k;
  i += k; j -= k;
}

Manacherのコードとよく似ていますね。

ベースとなるアイデアについて見てみましょう。
キーワードは「既に計算したものを利用する」です。

緑の文字列が一致していて、青の文字列の最大共通接頭辞が緑の文字列に覆われているとき、赤の文字列の所の最大共通接頭辞って青の文字列と一致しますよね。
これを利用すれば結構計算量を省略出来そうですね。

青の文字列が緑の文字列からはみだしている場合はどうでしょう。

この場合は、そのまんま計算結果を再利用することは出来なさそうなので、新たに計算をする必要がありそうです。
ただ、紫の枠で囲った部分は一致しているはずなので、これは利用しましょう。

というアイデアをそのまま実装するとこうなります。

int c = 0;
for (int i = 1; i < S.size(); i++){
  if (i+A[i-c] < c+A[c]) {
    A[i] = A[i-c];
  } else {
    int j = max(0, c+A[c]-i);
    while (i+j < S.size() && S[j] == S[i+j]) ++j;
    A[i] = j;
  }
}
A[0] = S.size();

このコードは実装方針が違うだけで最初に載せたコードとほぼ同じことをしています。
とりあえず正しい答えは計算できそうなのではないでしょうか？

計算量解析はManacherのときと同じようにすれば O(|S|) であることが言えます。
せっかくなので２つ目のコードをベースに解析してみましょう。

int c = 0;
for (int i = 1; i < S.size(); i++){
  if (i+A[i-c] < c+A[c]) {
    A[i] = A[i-c];
  } else {
    int j = max(0, c+A[c]-i);
    while (i+j < S.size() && S[j] == S[i+j]) ++j;
    A[i] = j;
    c = i;
  }
}

今回はwhileの中の「++j」が実行される回数が |S| 程度であることを言えば良さそうです。
・f(i) を i+A[i] と定義しておきます。
「int j = max(0, c+A[c]-i);」等に注意すると、各 i での j は
・f(c) - i ≤ j ≤ |S| - i
の範囲に収まります。「A[i] = j;」を踏まえて移項をすると、
・f(c) ≤ f(i) ≤ |S|
新しい f(c) は f(i) になるため、f(c) は ++j された回数だけ毎回増えていきます。f(c) は常に |S| 以下なので、++j の回数も |S| 以下ですね。
図を書いて i+A[i] の位置に注目してみると O(|S|) になることが直感的に分かりやすいのではないかと思います。
なお、この解析はManacherの方でも同様に適用できます。Manacherの記事では少し複雑な解析をしましたが、原理を考えればシンプルな話だったんですね。

以上、Z algorithmでした。

最初の記事（KMP） | 前の記事（Manacher）

文字列の頭良い感じの線形アルゴリズムたち２

昨日の記事の続きです。

Manacher

文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。
例えば、

abaaababa
121412321

こんな感じです。

結論から言うと、Manacherのコードは以下のようになります。

int i = 0, j = 0;
while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}

このコードが何をしているのかを見ていきます。
とりあえず、i は現在の更新箇所で、j はそのときの半径です。
while内の１行目のwhileは、愚直に「文字 i を中心とする最長の回文の半径」を計算しているようです。
求めた答えを R[i] = j で代入して、
int k = 1、while(なんたら)かんたら、i+=k,j-=k・・・？？？？？？？？
この辺りがよく分かりませんねぇ。
恐らく、ベースとなるアイデアを見てみた方が良さそうです。

ベースとなるアイデアについて見てみましょう。
キーワードは「既に計算したものを利用する」です。

黄色の文字を中心とした回文（長いので以降は黄回文みたいに呼ぶことにします）があって、黄色の文字を挟んで対称な位置に青の文字と赤の文字があるときを考えます。
青回文が黄回文に完全に覆われている場合、対称性を考えると赤回文の最長半径は青回文と一致しますよね。

こういう風に黄色の文字をまたいでいる場合でも大丈夫です。
これを利用すれば結構計算量を省略出来そうですね。

青回文が黄回文からはみだしている場合はどうでしょう。

この場合は、そのまんま計算結果を再利用することは出来なさそうなので、新たに計算をする必要がありそうです。
ただ、紫の枠で囲った部分は回文になっているはずなので、これは利用しましょう。

というアイデアをそのまま実装するとこうなります。

int c = 0;
for (int i = 0; i < S.size(); ++i) {
  int l = c - (i-c);
  if (i+R[l] < c+R[c]) {
    R[i] = R[l];
  } else {
    int j = c+R[c] - i;
    while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
    R[i] = j;
    c = i;
  }
}

このコードは実装方針が違うだけで最初に載せたコードとほぼ同じことをしています。
とりあえず正しい答えは計算できそうなのではないでしょうか？

ここで、気になる計算量の方ですが、

while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}

一見２重ループなのでO(|S|^2)っぽく見えますね。
今回は少し複雑です。i,j,kに注目して解析しましょう。関係のありそうな部分を取り出してみます。
・W：while(i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) の中の「++j;」
・X：while(i-k >= 0 && k+R[i-k] < j) の中の「++k;」
・Y：i += k;
・Z：j -= k;
で、条件を書き出してみます。
・A：YとZをまとめて考えると、この部分では「i+j」は変化しません。
・B：「i+j」 は |S| 以下です。（位置＋半径なので）
・C：「i+j」 が変化するのは W の部分だけです。
・D：i は各ステップの k の和、つまり X を回した回数の合計と一致します。
・E：明らかに i は常に |S| 以下です。
A~C より、W のwhileを回す回数が合計で |S| 回程度であることが言えます。
D,E より、X のwhileを回す回数も合計で |S| 回程度であることが言えます。
というわけで、うまいこと計算量O(|S|)になってるんですよねー。すごい。

ちなみに、普通のManacherをやると奇数長の回文しか検出できませんが、「a$b$a$a$b」みたいにダミー文字を間に挟むと偶数長のものも検出できるようにできます。

以上、Manacherでした。

前の記事（KMP） | 次の記事（Z algorithm）

文字列の頭良い感じの線形アルゴリズムたち

この記事はAdvent Calendar 2014の12/1の記事として書かれました。

はじめに

KMP、Manachar、Z algorithm の３つについて書きたいと思います。
１アルゴリズム／１日で追記して行きます。

これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という点で共通しており、いずれも「なるほどなぁ」と言わされました。
この美しいアルゴリズムたちを是非紹介したいと思い、この記事を書くことにしました。

・記法について
|S|：文字列 S の長さを表す。
S[i,j]：文字列 S の i 文字目から j 文字目までを取り出した文字列を表す。

KMP

※これは正確にはKMPではなくMPです。KMPについてはこちら。
文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記録した配列を O(|S|)で構築するアルゴリズムです。ただし、|S[0,i-1]|未満のもののみを考慮します。
例えば、

aabaabaaa
_010123452

こんな感じです。(i=0の場所は適切な値が存在しないので_(-1の意味で使っています)とかを入れます。)
(等幅フォントじゃ無い場合は等幅フォントで見てね)

この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、その辺りの説明は他のサイトにお任せします。

結論から言うと、MPのコードは以下のようになります。

A[0] = -1;
int j = -1;
for (int i = 0; i < S.size(); i++) {
  while (j >= 0 && S[i] != S[j]) j = A[j];
  j++;
  A[i+1] = j;
}

このコードが何をしているのかを見ていきます。

j の動きに注目します。各for文のステップを実行した後のjの場所を追ってみます。

S : abbabba
1 : ji_____
2 : j_i____
3 : _j_i___
4 : __j_i__
5 : ___j_i_
6 : ____j_i

j は A[i+1] を示しています。S[0:j-1]とS[i-j+1:i]は一致していますね。

S[i]とS[j]が一致していれば j++だけで事足ります。（上の例は基本的にj++ばっかりしてます）
しかし一致していなければそういうわけにはいきません。
一致しなかった時は１から計算し直せば正しい答えは得られますが、それだと効率が悪すぎます。
それを既に計算したものを利用してなんとかするのが whileの部分なのですが、「j = A[j]」というトリッキーなことをしています。

さっきの例は単純な例だったので、もう少し複雑な例を見てみましょう。

S : aabaabaaa
A : _010123452
7 : _____j_i_
8 : __j_____i

i=7,8のときだけpickupしました。
i が 8 になった瞬間は j は 5 で、while文に入ります。
while文では以下のような操作が行われます。

while (j >= 0 && S[i] != S[j]) j = A[j];
・i=8, j=5 ： S[8]=a,S[5]=b なので S[i] != [j]。jがA[j](=2)になる。
・i=8, j=2 ： S[8]=a,S[2]=b なので S[i] != [j]。jがA[j](=1)になる。
・i=8, j=1 ： S[8]=a,S[1]=1 なので S[i] == [j]。while文を抜けます。
（・while文を抜けた後 j++ されて j = 2 となります。）

ふーむ、なるほど？？

結局何をしているのでしょうか。

前のステップで緑の部分が一致していたとします。（二段目の緑の部分は S[0,A[i]-1]）
赤の文字と青の文字が同じなら j++ だけで良さそうですね。
赤の文字と青の文字が異なる場合、次にチェックすべきものは、

この図の緑(濃い方)の部分です。つまり、S[0,A[A[i]]-1]です。
ここまでの計算結果から、緑の部分は３つとも一致しているはずですね。
ここで赤の文字と青(濃い方)の文字が同じならば j = A[j], j++ とすればいいですね。
それで、赤の文字と青の文字が異なっていれば今度は S[0,A[A[A[i]]]-1] に注目して・・・とやっていけば良いというわけです。
イメージできましたでしょうか。

ここで、気になる計算量の方ですが、

for (int i = 0; i < S.size(); i++) {
  while (j >= 0 && S[i] != S[j]) j = A[j];
  j++;
  A[i+1] = j;
}

一見２重ループなのでO(|S|^2)っぽく見えますね。
j の値に注目して解析してみます。j が変化する場所は以下の２カ所です。
・while文を１回回す度に j は必ず減る。(ただし -1 より小さくはならない)
・for文を１回回す度に j++ により j は 1 ずつ増える。
すると while が回る回数って合計で高々 O(|S|) 回になっていませんか？なぜなら、j の値を減らすためには j の値を増やさないといけないですが、j の増加分が |S| しかないからです。
こういう計算量解析うまいですよねー。

以上、MPでした。

次の記事（Manachar） | 次の次の記事（Z algorithm） | おまけ（KMP）

SRM637

久しぶりにwriterやってました。登場人物もやってました。
「Cat Snuke と Wolf Sothe がゲームをする」というテーマで統一されています。
Cat Snukeといえば、いまのtopcoderの画像カンガルーだから早く猫の着ぐるみ買わないと。

Div2 Easy

猫のSnukeと狼のSotheで1~2Nが書かれた2N枚のカードでゲームをする。
まず、カードをN枚ずつ配る。
各ターンで２人のプレイヤーは同時に１枚ずつカードを出していき、大きい方のカードを出した方に１点が入る。
各ターンでプレイヤーが出したカードの情報が与えられるので、Snukeの点数を答えよ。

解法

やるだけ

Div2 Medium

2*Wのグリッドがあり、いくつかセルが黒く塗られている。
左端から右端まで白いセルだけを通っていくパスが存在するようにいくつかのセルを黒く塗る時、最大何カ所塗れるか。

解法

左から貪欲に埋めていく感じで考える。
両方空の列があったら基本ans++で、
#.~~~~..
..~~~~~.#
みたいに上下が切り替わってる場所の個数だけans--
オーバーキルっぽいけど、最短路問題を解いてもよい。
この問題だけ１人用ゲームです。

Div2 Hard

グリッドがいくつかのregionに分かれている。
まずSnukeがいくつかのregionを赤く塗る。
残りのregionをSotheが青く塗る。
青いセルのみを辿って上端から下端まで行けたらSotheの勝ち。
Snukeが勝つためには最小で何カ所の"セル"を塗らなければならないか。

縦,横 <= 50
regionの個数<=62

解法

各regionを頂点と見なして、８近傍で接しているregionに辺を張る。
そのグラフで左端から右端への最短路を求めれば良い。（重みはregionのサイズ）
平面グラフの最小カット＝最短路的なあれ。

ちなみにこのゲームの元ネタはHexとか。

Div1 Easy

猫のSnukeと狼のSotheで1~2Nが書かれた2N枚のカードでゲームをする。
まず、カードをN枚ずつ配る。
各ターンで２人のプレイヤーは同時に１枚ずつカードを出していき、大きい方のカードを出した方に１点が入る。
Snukeの手札と、Sotheがi番目に出すカードの情報（-1なら分からない、1~2Nならそのカードを出す）が与えられる。
Snukeの手札を順番を適切に決めて、得点の期待値を最大化し、その期待値を返せ。

解法

見えてる所は出来るだけ多く勝った方が良い。なぜなら、見えている所でわざわざ負けてそのカードを見えていない所に回して一勝するよりは、見えている所をちゃんと勝つ方が良い(または同じ)。勝つときはぎりぎりで勝つのが最善。絶対に負けるカードに対しては持っている中で最小のカードを割り当てる。
残った完全なる運ゲー部分は、カードごとに独立して期待値を計算し、足し合わせれば良い。期待値線形性ってやつだっけ。

Div1 Medium

2*Wのグリッドがあり、いくつかセルが黒く塗られている。
交互にセルを１つずつ塗っていく。左端から右端まで白いセルだけを通っていくパスが無くなるように塗った人の負け。

解法

まず、右端の４セルのうちのどこかと左端の４セルのうちのどこかが埋まったらあとは何の戦略も無く、終局までの手数の偶奇が一定となり、それによって勝敗が決まることに気付く。
両端２列ずつを抜き出してみる。

となっていた場合はもう勝敗は決している。

となっていた場合は右の４セルのうち上に置くか下におくかで終局までの手数の偶奇を好きに選べるため、先手の勝ち。

となっていた場合は見合いとなっており、この８セルのうちどこかを塗ってしまうと１つ上のパターンとなり、負けてしまう。
つまり、中略の区間での勝敗がこのゲームの勝敗となるため、再帰的に判定して行けば良い。

ちなみに、空の区間で分割してグランディー数とかで解けてしまうのが少し残念。グランディー数強過ぎるんじゃいー。
追記：制約でかくすればgrundyやるだけ問題じゃなくなって良かったなぁとすごく後悔しています・・・

Div1 Hard

グリッドがいくつかのregionに分かれている。
何らかの手順でゲームが行われ、ゲームの最終状態では、いくつかのregionを赤く塗られ、残りのregionをSotheが青く塗られている状態になる。
赤いセルのみを辿って左端から右端まで行けたらSnukeの勝ち。
青いセルのみを辿って上端から下端まで行けたらSotheの勝ち。
両方勝てないことはあり得るかどうかを判定せよ。

縦,横 <= 30

解法

結論から言うと、
格子点を頂点、異なるregion同士の境界を辺としてグラフを作る。
このグラフから１つ頂点を選んでsourceとし、四隅の頂点をsinkとしてフローを流した時、4流れればinvalidとなる。
フローに使われた辺をまたぐregionに異なる色を塗れば復元できる。

まず、上端と下端・左端と右端をcutしたい。
平面グラフのcut→最短路的なあれを考えると左端→右端のフローと上端→下端のフローを同時にながせれば良さそうですが、それだとあんまりうまくいかない。
混ぜちゃうと多分、
AAB
CAA
を誤ってinvalidと言ってしまったりする。
そこで少し考える。
左端→右端のフローと上端→下端のフローは少なくとも１点で交わるはずなのでその点をsourceにして、
中央→右端・中央→左端・中央→上端・中央→下端の４つのフローにすると良さそう。
少し悩みそうなのはsinkをどうするかですが、盤外の上下は青で、左右は赤で塗られていると考えれば、フローの脱出口が四隅だけになってhappy。
ざっくりですが以上です。

解法２
８近傍のregion間に辺を張り、辺の交差点からフローが４流れるかを判定。
解法１とわりと違う気がするのに正しく解けるの面白い。
強いケース：
ABC
DED
DDD
フローを流した時に次数が４になる頂点が２つ。
解法２を８近傍でなくて４近傍にするとこれが落ちるらしい。

夏季セミナー2014 長編参加記

さすがに１単語は少な過ぎたのでもっと書きます。
下の方に真面目そうなことを書いてみました。

---

１日目

• 田舎を自転車で走っていたら迷子になり、疲れた。
• 昼を食べずに参宮橋へ
• 参宮橋でhogloidを発見
• 一緒に松屋に入る
• プレミアムじゃない牛めしがなくて不思議だった。七味割と美味しかった。
• 藤原が松屋の前を通り過ぎるのを見た。
• チューターの自己紹介および本の軽い説明
• 生徒の自己紹介
• 本決め
• じゃんけん。CISPと集合知が若干人気で1人ずつ別の本にうつってしまった。
• 部屋を分けてセミナー開始
• １日目は時間も短いし、とりあえずざっと本の全体像を眺めてもらうことにする。
• 割と章ごとに独立していたので、章を分担して読んで軽く章の概要を紹介してもらった。
• インターネットが飛ばせなくてつらかった
• 取り組む章をなんとなく決めてもらったかなーってところで終了。
• ご飯が足りないことに薄々気付く
• siquareさんとkagamizさんが遊びに来た。

２日目

• 章を決めて取り組み始めてもらう。
• インターネットだめみたいだったのでmanuke(emobile)を飛ばした。
• pythonに戸惑っている人もいた。
• まぁそんなに敷居の高い言語ではないのでなんとかなった。
• pythonは使えると色々便利
• ご飯が足りないことに確信する。
• 講義：タイリングが綺麗だった
• まぁそんな感じで２日目も無事終了
• りんごさんが遊びに来た。
• 参加記を書くのに疲れてきた。
• ご飯が足りないことを嘆く。
• Codeforces
• りんごさんと競プロ談義をする。やはり楽しい。

３日目

• Ω＼ζ°)ﾁｰﾝ
• 進捗状況を見て適当な感じにサポートした。
• 行き詰まったらどんどんチューターに質問しましょう。
• 自分が生徒だった時にもらったvisualizerを渡したり、
• pythonとかの環境を整えたり、
• 相談に乗ったり、
• チューター業をした。
• ニューロネットワークのパラメータをGAするというのにちょっと感動した。
• 決定木組んでみたけど面白かった。
• エントロピーとかも、理解してみると面白いと思います。
• 夜は交流タイムがあった。サッカーを布教したり、カタンを提供したりした。
• ご飯が足りないことに絶望する。
• 満を持して万豚記
• 白胡麻担々麺。うまかった。
• 部屋でSkull and Roseをトランプでやった。結構楽しかった。

４日目

• 発表準備日
• 進捗のサポートをしたりした。
• ソフトをダウンロードしたり、ツイートデータを取得したりするにつけ、インターネットの重要性を痛感。
• 割とチューター業をした。
• ほえー
• 晩はカタンをやった。都市化しまくって勝った。

５日目

• 発表
• 面白かった。
• 特に面白いと思ったのは、Trianguler・死にたくない・バランスゲームあたりだったかな。
• 生徒さんみんな優秀でした。
• 蚊怖すぎ・・・
• 帰る
• 万豚記
• とりあえず新宿に行ったものの、やはり全員にとって行きたい場所というのが特に決まらず、結局サイゼリアという安上がりプランが採用された。
• 帰宅。

来年以降の生徒へ

• チューターは基本暇そうにしているっぽいのでどんどん頼ったり質問したりして仕事を与えてあげましょう。
• というか、行き詰まって時間の無駄をするのは本当にもったいないので、がんがんチューターを頼りましょう。
• テザリング等のインターネットへ繋ぐ手段を持っておくと何かと便利だと思います。
• セミナー期間は長いようで案外短かったりします。セミナー時間中に油断してると充実し損ねるかもしれません。
• 来年はきっと談話室があると思うので、行きましょう。
• twitterをやっておくと交流しやすいでしょう。

来年以降のチューターへ

２年間チューターをやらせていただいて思ったことを書きます。

• 本の予習は軽くでもしておくと、生徒へのアドバイスがしやすいと思います。
• 本を渡すだけでは、よほどプロな生徒以外は少し何から手を付ければ良いのか戸惑ってしまうと思います。どんな風に本を読み進めてもらうかとかは考えておくと良いと思います。
• 定期的に進捗を確認しましょう。行き詰まっていそうな生徒や、まずそうな方向に進んでいそうな生徒がいれば、早めにサポートしてあげましょう。
• 自分ならどんなことをして発表ネタにするか、とかを考えておくと発表ネタが思いつかずに詰まっている生徒の助けになれるかもしれません。

本や班のメンバーによってどうするのが良いかが変わってくるかとは思います。

まとめ

万豚記

夏季セミナー2014 参加記

さらにボキャブラリーが減ったので、１単語のみで参加記を書きます。

---

万豚記