ICPC2016 国内予選 参加記

競プロ ICPC

おそらく最後のICPCの国内予選です。
７完２位でした。
大きな戦略ミスと大きなハマりがなかったので良かった。
メンバーは去年と同じ（peryaudo,mine_studio）
今年はJOI本戦勢・JOI春合宿勢・CTF勢の１年生チーム（peryaudoを名乗っているチーム）がいて、来年以降にも期待が高まっています。

印刷を失敗したせいもあって序盤の立ち回りが崩れたのであまり参考にならないかもしれませんが、コンテスト中の流れです。印刷順序にはお気をつけください。

〜開始

・peryaudoがPCを買い換えてプロからエアーになってた。僕もmacbook趣味 の方なので使いやすかった

開始〜

・問題を自前プリンタで印刷しつつ、mineにエイリアスとかの環境を整えてもらう。
・後ろのページから印刷されてしまい、序盤の問題を読めなかったのは結構失敗だった。
・序盤のペナルティが増えるが、コンテスト全体の戦略を詰める時間が増えたので、デメリットだけでもなかったかもしれない。

A

・始まってすぐperyaudoに投げた。概要知らない。7分くらいで通してた。
・印刷を失敗して、仕方ないから後ろから順番に問題を読んでいた。
・H読んでシンプルなグラフ問題だし、そのうち解こうと思った。
・Gは幾何だったので、とりあえずmineに問題読解を投げた。
・F,Eあたりもざっと目を通した。

B

・Aが通った頃にはまだB問題の印刷が終わっていなかったため、とりあえずこれもperyaudoに投げた。
・その間にDを読むと区間DPだったので、自分で実装することにした。(DPは自分でやった方が数段速くなるという経験則)
・Cはperyaudoに投げようかなと思った。
・E,F,Hあたりの解法もこの辺で考えてわりとすぐ思いついてた気がする。
・peryaudoはサンプルが合わなくてちょっとハマったっぽい。
・問題文読んだりしたそうだったから交代した。

D

・書いた。
・区間DPをデバッグしてしまった。
・直った、通った

B

・D書いてる間に無事原因がわかったらしくすぐAC

C

・Eを読んで、立方体の交差によって減る表面積を計算する関数が要りそうだったので、その部分をperyaudoに詰めてもらうことにした
・結局Cは自分でやることにした。
・問題概要とかを伝えるほどでもないくらい実装軽かった。
・C問題：上限について思いを馳せるとエラトステネスっぽい操作だから素数っぽい感じになることがわかった。面白い。答えが最大になるケースがサンプルに入っていて優しさを感じた。

H

・バグる要素がないし、ライブラリさえ写せば残りのよりもすぐ書けそうだったのでやった
・ライブラリ写経は他の人に任せてもいいのだけど、EもFもすぐ書き始められる程度に解法スタックが溜まっていたので自分で写した。（独自のマクロとかもあるし、書いた本人である自分で写す方が多分早い）
・最小を最大化だと思ってて誤読で危なかったが、正しいバージョンもすぐわかったので良かった。
・H問題：S,頂点のノード(n個),辺のノード,Tからなるグラフにフローを流す。S→(頂)に流量x_i（後述）、(頂)→(辺)に流量1の辺(2m本)、(辺)→Tに流量1の辺を貼る。最小の値Lを0~nまで試す。x_iをLに設定して流してmaxflowがnLでなければNG。OKなら最大の値RをLから1ずつ増やしながら試す。このとき、グラフは初期化せずに対応する辺の残容量だけを増やす。容量を増やした後に流し直して、合計のmaxflowがmなら実行可能。流し直したときに最小流量条件を満たさなくなるかもしれないと思うかもしれないが、S→(頂)の辺を逆流させるような増加流は明らかに最短路ではないためここに逆流は起きない。
・デバッグも特になくAC

E

・立方体の交差によって減る表面積を求める関数と、それが1以上の組に辺を貼ったグラフまでperyaudoに実装してもらった。
・この間にGの概要を聞いて、解法を考えたけどすぐにはわからなかった。x,yを独立にするところまでは考察が進んだ。（解説では「重心」の一言で解決してる部分）
・残りのパートは悩ましい要素のある実装なので自分でやった。
・この辺りで２人の仕事はほぼなくなったので後ろで見てバグがないかチェックしてもらってたけど、結論から言うとバグった。
・正直redcoder（しかも変数名わりと適当）が何を書いてるのかを同時に追うのは相当難しいし、チェックすべきポイントみたいなのをまとめておくべきなんだろうな。（改善の余地あり）
・最初に訪れたフラグをtrueにし忘れるというアホバグ埋め込んだ（しかもこの辺の出力見て挙動チェックしたはずなのに・・・）
・1WA食らってしばらくデバッグ（ダメ）
・AC

F

・解いてる間にGのサンプルを図示してもらう。
・特に何も起きなかったので解法だけ書く。
・周りに白マスをつけて１周り拡張する。
・包含関係は根付き木になるため、それをまずは構成する。
・各マスの「そのマスが属するグループ番号」と「親グループの番号」を求めていくことにする。
・左上のマスから順に、まだグループ割り当てがされていなければDFSを開始する。
・同じ色の連結成分全てに現在のグループ番号を割り当て、隣接している異なる色のマスについて、そのマスがまだグループ割り当てされていなければ親グループを現在のグループに設定する。
・求めた情報から根付き木を復元するのは難しくない。
・根付き木はカッコ列に変換する。子のカッコ列は辞書順にソートして並べる。これで正規化が出来て比較が容易になる。（ちなみにこの部分は、前にperyaudoのコーディング面接練習に付き合ったときに出題したらちゃんと解かれた）
・２個ずつ処理するのが面倒だったので、2*テストケース数分だけ文字列が入ったvectorを作って、最後に全部出力した。

G

・２乗和なのを失念していて、候補の座標はいずれかの頂点と同じx座標,y座標のn^2通りでいいと思って書いてしまい、サンプルが合わなかった。
・候補が2^40通りより減らせなくて結構悩んだ。
・N=20が2^20を連想して少し惑わされたが、それを利用できそうな道は思いつかなかった。
・問題を整理して円を書いてみたら、集合の候補がだいぶ減りそうな方針を思いついた。（具体的にどれくらいかはわかってなかったけど言われてみると確かにM^2程度だ）
・円の交点となるような座標について、そこを含む円の集合を計算して、それらのコストを最小化する座標を求めてそれを候補とすれば良い。
・（＋もとの頂点の座標も候補に入れる）
・正しい解法を思いついた時点で残り18分で、peryaudoに幾何ライブラリを写してもらって、mineに方程式を解いてもらって、僕はその他の実装を詰めた。
・なんとか実装は終わって嬉しかったけど、デバッグは間に合わなかった。

以上

うーん、よく考えるとまだまだチーム戦略見直すべき点がいくつかあったけど、年々チームの立ち回りがよくなってきていて楽しい。
peryaudoにどれくらいのことを任せられるのかが分かってきたというのも大きそう。
googleのコーディング面接対策をしてからperyaudoの実装力が上がったような感触を受ける。

最近競プロで大スランプを感じていたので不安だったけれど、悪いコンディションとかがたまたま重なってただけかなぁ・・・
今回の目標は遠征費獲得（例年通りなら大学別２位）だったので大満足な結果です。

Xmas Contest 2015

競プロ

Xmas Contest 2015 お疲れ様でした！

ご参加いただいた方、ありがとうございました。

楽しんでいただけていたら幸いです。

とりあえず、各問題の解法の概要を書いていきたいと思います。

A「Accumulation」

乱数生成が一番難しい、という問題。
f(x) = Ax + B
のときに f^T(x) を求めたい。
f(f(x)) = (A*A)x + (AB+B)
みたいな感じで関数合成をバイナリ法で計算していくと f^T(x) が求められる。

B「Broken Christmas Tree」

解法１：「まだ繋がっていない頂点集合」をsetか何かで持ちながらDFSしていく。繋ごうとした時に繋ぐのに失敗する回数がM回で抑えられるので上手くいく。
解法２：悪い辺の次数が最小の頂点に直接繋げられる頂点をぐいぐい繋いで連結成分を縮約すると、頂点数が√M以下になるので、MSTとかをする。実装大変。

C「Colored Tiles」

解法１：ある2行を取りだして（1≦i≦j≦5 の15組）manacherで最長回文を求めておくと、あとは適当に計算できる。
解法２：中心と高さを固定して取れる限り幅を増やしていく、というような愚直なアルゴリズムで求めていく。ただし、Yesと言われた時はunion findでくっつけておき、次からはその情報をもとにYesだと確定する時はクエリを投げないようにする。すると、Yesと言われる回数が高々HW-1回に抑えられる（uniteの回数は高々頂点数-1）。また、Noと言われる回数も中心と高さの組の個数で抑えられる。

D「Destroy the Duplicated Poem」

解法１：KMPをやるんですが、そのままやるとTLEなので、「ここでこの文字がきたときのfailure link」みたいなのを計算していく。「ひとつ下に潜る」という操作に注意。
解法２：KMPをうまく実装すると一回の遷移がlogで抑えられるらしい。というかこれが本来のKMP。詳細はclimpetさんの提出とこれを読んでください。→記事書きました

E「Esolang?」

部分点は線形リストとかで取れます。
満点のベースアイデアは、vectorみたいに「確保していたメモリが足りなくなったら、新たに倍のメモリを確保する」という感じです。
ただし、vectorみたいに新たに確保するたびにデータをコピーしていると、メモリが4Mぐらい必要なので、配列の線形リストみたいな形で実装します。
データ構造は、[サイズ1の配列]→[サイズ2の配列]→[サイズ4の配列]→[サイズ8の配列]...みたいな線形リストになります。
メモリは2M+N*αみたいな感じで、expr回数はO((M+Q) logM)とかです。
exprの回数制限だけで変なコード（例えばa[a[a[a[a[a[...]]]]]]]]とか）が縛れるのが作問側の知見として面白かったです。

F「FILO Sort」

[B+1,A,B]（A<B）という部分列がないことがソートできる条件。こういう組の個数を数えるのは、前計算：BITやる、クエリ：隣接swapしかないのでO(1)でできる。
考察を進めるほど実装が簡単になる問題だった。

G「Good Sequence」

よく考えると、隣接の差の絶対値の和を求めるだけ。

H「Hybrid Testcase」

この枠は他の問題が出来てから作ろうと思っていて、他の問題の準備がある程度終わってから適当にそれっぽい問題を作ってみたら問題になっていた。
まずA=0 かつ X>T としてみると、X+4B=Z, X+C=Z という式になる。B=Z/4, X=Z%4, C=4B, T=1 とすると9以上は全て構成できる。
あとは8以下だが、A問題の性質上 X は8以下しかありえなくて、G問題の性質上 他の値は X+8 以下しかありえない。となると、考えられるケースを全て試すことができる。

AOJ 2633 「Cellular Automaton」

りんごさんセットのCellular Au🍅n解きました。

面白いです。ヒントなしでは解けませんでした。

ヒント

ヒント
グラフ
グラフの頂点は2^(2w+1)個、辺は各頂点から２本ずつでる有向辺
閉路の重み
ポテンシャル
牛

解法

ネタバレ防止のため閉じてあります
w=1で考えます
sの長さは3です
000~111に対して0,1を割り振ったとき、それが条件を満たすかどうかを判定する方法を考えます
判定方法
まず、000は0でなくてはならない（わりと自明）
セルの初期状態として考えられるものは、
・00..0001011000..00
のように、000で囲われたものになる
この例だと、
・p[000]+p[001]+p[010]+p[101]+p[011]+p[110]+p[100]+p[000]=3
を満たしている必要がある。
ここで、000~111を頂点とし、「１つシフトして右に0か1をつけたもの」に重み付きの辺を張る
たとえば、011-0->110、011-1->111、010-0->100、010-1->101、のような感じ
このグラフの000を含むサイクルであって、辺の重みの和≠頂点の重み(p[v])の和となるものがあってはならない
グラフを少し拡張して、頂点の重みを辺の重みとして扱えるように変形します
頂点を２倍にして、片方をin、片方をoutにして、他の頂点からの辺u->vはu_out->v_inとつなぎ直します
それから、v_in->v_outに重みが-p[v]の辺を張ります
このグラフに重みが0でない閉路があってはいけません
判定だけならこれでできるようになりました
ただし、解の候補は2^128通りあったりするのでまだ工夫が必要です
p[v]を0,1だけでなく?にできるようにします。（?=0か1のどちらかが未定）
?を許可した時の判定方法
各頂点にポテンシャルh[v]を定めた時、全ての辺u->vでh[u]+重み=h[v]となっていれば良いです
h[u]+重み=h[v]を
・h[v]≦h[u]+重み
・h[u]≦h[v]-重み
に書き直すと牛になります。
重みが?の辺に関しては、
・h[v_out]≦h[v_in]+(-1)
・h[v_in]≦h[v_out]
です。
辞書順でs以上の最小を求める方法は、ソースコードを読むのが早いと思います
イメージとしては、0から1にすべき最下位のビットを求めて、そこからはいつもの辞書順

ちなみに、閉じるやつはindenterで生成しました。

ソースコード

// 前略
int w, n;

bool f(string s) {
  rep(i,n) {
    int l = (s[i] == '1');
    int r = (s[i] != '0');
    g.setCost(i, r);
    g.setCost(n+i, -l);
  }
  return !g.hasNegativeCycle();
}

int main() {
  string s;
  cin >> w >> s;
  w = w*2+1;
  n = 1<<w;
  g = bell(n*2);
  rep(i,n) g.add(i,n+i,0);
  rep(i,n) g.add(n+i,i,0);
  rep(i,n) {
    int u = (i<<1)&(n-1);
    g.add(n+i,u,0);
    g.add(u,n+i,0);
    g.add(n+i,u|1,-1);
    g.add(u|1,n+i,1);
  }

  // ここから辞書順最小を計算
  if (f(s)) {
    cout<<s<<endl;
    return 0;
  }
  for (int i = n-1; i >= 0; --i) {
    if (s[i] == '0') {
      s[i] = '1';
      if (f(s)) break;
    }
    s[i] = '?';
  }
  if (s == string(n,'?')) {
    puts("no");
    return 0;
  }
  rep(i,n) {
    if (s[i] != '?') continue;
    s[i] = '0';
    if (!f(s)) s[i] = '1';
  }
  cout<<s<<endl;
  return 0;
}

AOJ 2635 「Snuke」

AOJ ICPC 競プロ

この記事はAOJ-ICPC Advent Calendar 2015の記事として書かれました。

りんごさんセットのSnake解きました。

解法を知っていれば簡単。

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/JAGSummer2014/sunake.png

通れるでしょうか？

解法

ネタバレのため、反転してます

各辺について注目した時、(凸包)ー(凸包)という鉄アレイみたいな形状になっていれば良い。
先頭から見ていき、0~i番目までの頂点の凸包＝0~i+1番目までの頂点の凸包となっている部分があってはダメ。
さらに、前後を逆にして同様の判定を行う。

コード

// 前略
bool f(Poly p) {
  int n = sz(p);
  double pre = -1;
  rep(i,n) if (i >= 2) {
    Poly a;
    rep(j,i+1) a.pb(p[j]);
    a = convex(a);
    double now = area(a);
    if (abs(now-pre) < eps) return false;
    pre = now;
  }
  return true;
}

int main() {
  int n;
  cin >> n;
  Poly p(n);
  rep(i,n) cin >> p[i].x >> p[i].y;
  string ans = "Possible", im = "Impossible";
  if (!f(p)) ans = im;
  reverse(rng(p));
  if (!f(p)) ans = im;
  cout<<ans<<endl;
  return 0;
}

競技プログラマのためのC++

programming 競プロ

この記事はCompetitive Programming Advent Calendar 2015の６日目の記事として書かれました。

この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。
筆者自身がC++に詳しいわけではないため、仕組み等の解説は避け、「こう書けばいい感じに動くよ」みたいな部分だけを書いていきます。
「競プロでの応用例」という点に注目して読んでいただければと思います。

目次

・range-based for（前菜）
・lambda式（メイン）
・コメントアウトの小技（おまけ）

まずは、C++11の新機能を使ったテクニックから紹介します。

range-based for

これはよく知られていると思います。以下のように書くとvectorとかmapとかを舐められるやつです。

for (型 変数名 : 舐める対象)

使用例です。

void printVector(vector<int>& d) {
  for (int a : d) printf("%d\n", a);
}
void printSet(set<int>& d) {
  for (int a : d) printf("%d\n", a);
}
void printMap(map<int,int>& d) {
  for (pair<int,int> a : d) printf("%d %d\n", a.first, a.second);
}

特にmapを舐める操作が簡潔に書けて良いですね。

autoという型を自動で判断してくれる便利なやつを使うとさらに楽になります。

void printMap(map<int,int>& d) {
  for (auto a : d) printf("%d %d\n", a.first, a.second);
}

書き換えがしたくなった場合は、参照で舐めることもできます。

void twiceVector(vector<int>& d) {
  for (int& a : d) a *= 2;
}
void twiceMap(map<int,int>& d) {
  for (auto& a : d) a.second *= 2;
}

range-based forをグラフの問題で使うときは注意が必要です。

vector<int> to[MAX_V];

// 木を舐める
void dfs(int v, int dist, int p=-1) {
  printf("%d : %d\n", v, dist);
  for (int u : to[v]) if (u != p) dfs(u, dist+1, v);
}

このようなケースでは便利で問題ないのですが、辺にコストがつくと普通のforで書かざるを得なくなります。
（いい方法知ってたら教えてください）

vector<int> to[MAX_V];
vector<int> cost[MAX_V];

void dfs(int v, int dist, int p=-1) {
  printf("%d : %d\n", v, dist);
  for (int i = 0; i < to[v].size(); ++i) {
    int u = to[v][i];
    if (u != p) dfs(u, dist+co[v][i], v);
  }
}

range-based forで途中まで書いてコストがあることに気づいて書き直す、なんてことがないように気をつけたいものです。

lambda式

やばそう、というくらいにしか思ってない人もいるんじゃないかと思いますが、意外と競プロでも便利だったりします。

基本形

lambda式とは、超簡単に説明すると、関数みたいなやつです。
基本的な構文は以下の通りです。

[](引数) { 処理 };

例えば以下のように使えます。

void solve() {
  auto mod2 = [](int x) { return x % 2;};
  printf("%d\n", mod2(2015));
}

この例だと、関数内で関数が作れるという嬉しさ（嬉しいかどうかは知らない）しかありません。

補助関数

ここからが本領発揮です。

まず、「[]」を「[&]」にすることで、スコープ内の変数に自由にアクセスできるようになります。
スコープって何？っていう人はスルーして下の例を見てください。多分スコップとスープを足して２で割ったようなやつです。

例題：

0に以下の操作を何回か行ってNにしたいです。最小何回でできるでしょう？
・+1する
・-2する
・2倍する
・2乗する

要するに、遷移の種類がたくさんあるBFSです。
lambda式を使うと結構綺麗に書けます。

int solve(int n) {
  vector<int> dist(n+1, INF);
  queue<int> q;
  auto add = [&](int x, int d) {
    if (x < 0 || x > n) return;
    if (dist[x] != INF) return;
    dist[x] = d;
    q.push(x);
  };
  add(0, 0);
  while (q.size()) {
    int x = q.front(); q.pop();
    add(x+1, dist[x]+1);
    add(x-2, dist[x]+1);
    add(x*2, dist[x]+1);
    add(x*x, dist[x]+1);
  }
  return dist[n];
}

[&]にすると、distやqにアクセスできるようになるという点がポイントです。
（この例だと頂点と距離のペアをqueueに突っ込んで行って、popしたときにいろいろ判定するという方法もあります）
（↑ダイクストラだと、queueに入れる前にチェックしないと定数倍がわりと重くなります）

比較関数

さて、lambda式の利用法として「比較関数」は外せないでしょう。sortの比較関数とかでlambda式を使うと良い感じです。

void sortRect(vector<pair<int,int>>& rect) {
  sort(rect.begin(), rect.end(), [](P a, P b) {
    return a.first*a.second > b.first*b.second;
  });
  // [](const P& a, const P& b) とすると少し速くなります
}
void sortByValue(const vector<int>& value) {
  vector<int> id;
  for (int i = 0; i < value.size(); ++i) id.push_back(i);
  sort(id.begin(), id.end(), [&](int a, int b) {
    return value[a] < value[b];
  });
  for (int a : id) printf("%d : %d\n", a, value[a]);
}

１つ目は、長方形（ペアで２つの辺の長さを持っている）を面積の降順にソートしています。
２つ目は、添字の方をvalueの昇順にソートしています。「[&]」が活きていますね。

lambda式が一番輝くシチュエーションは、個人的にはSuffix Arrayではないかと思っています。

struct SA {
  string s;
  int n;
  vector<int> id, rank;
  
  void construct() {
    s += '$';
    n = s.size();
    id = rank = vector<int>(n);
    vector<int> tmp(n);
    rep(i,n) id[i] = i, rank[i] = s[i];
    int k;
    auto comp = [&](int i, int j) {
      if(rank[i] != rank[j]) return rank[i] < rank[j];
      int ri = i + k < rank.size() ? rank[i + k] : -1;
      int rj = j + k < rank.size() ? rank[j + k] : -1;
      return ri < rj;
    };
    for (k = 1; k < n; k<<=1) {
      sort(id.begin(), id.end(), comp);
      tmp[id[0]] = 0;
      for (int i = 1; i < n; ++i) tmp[id[i]] = tmp[id[i-1]] + comp(id[i-1],id[i]);
      rank = tmp;
    }
  }
};

ちなみに、classの代わりにstructを使うとpublicを書かなくてもいいので楽です。（お行儀は悪いですが）

多重ループbreak

さて、最後にちょっと変わった使い方も紹介したいと思います。

ずばり、多重ループを抜けるときに使えます。

多重ループを抜ける方法には、

・if (~) breakをたくさん書く
・i,j,kとかを書き換えてループの終了条件を全部満たすようにする
・gotoを使う

などがありますが、個人的にはどれもなんだかモヤッとします。
そこでラムダ式を利用します。
比較も兼ねて全部の例を書きます。

// if (~) breakをたくさん書く
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < n; ++k) {
      ++cnt;
      if (cnt >= m) break;
    }
    if (cnt >= m) break;
  }
  if (cnt >= m) break;
}

// i,j,kとかを書き換えてループの終了条件を全部満たすようにする
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < n; ++k) {
      ++cnt;
      if (cnt >= m) i = j = k = n;
    }
  }
}

// gotoを使う
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < n; ++k) {
      ++cnt;
      if (cnt >= m) goto LABEL;
    }
  }
}
LABEL:

// lambda式を使う
[&] {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) {
        ++cnt;
        if (cnt >= m) return;
      }
    }
  }
}();

多重ループを「[&] { ~ }();」で囲って、breakの代わりにreturnを使うだけです。
若干トリッキーな記法なので、少し解説します。

[&]() { ~ }
↓ 引数を省略（引数がない場合は省略できる）
[&] { ~ }
↓ このlambda式を関数呼び出しみたいに呼び出す
[&] { ~ }()

という感じです。

再帰

lambda式で再帰を書こうとすると型推論ができないらしく若干面倒です。

#include <functional>

// autoだとエラーが出る
function<void(int)> f = [&](int x) {
  if (x == 0) return;
  cout << x << endl;
  f(x-1);
};

追記：これ遅いらしいので注意が必要ぽい

コメントアウトの小技

おまけです。
範囲コメントアウトをするとき、いちいち4文字付けたり消したりするのは面倒ですよね。
これを編集距離１でtoggleする方法を紹介します。

/*
コメントアウトされている
//*/
↑
↓
//*
コメントアウトされていない
//*/

楽ですね！
応用編もあります。

/*
操作１
//*/ 操作２
↑
↓
//*
操作１
//*/ 操作２

こう書くと、操作１と操作２をtoggleできるようになります。

最近はエディタのショートカットを使うようになったので使わなくなりましたが。。

まとめ

以上、どうだったでしょうか？
参考になった点が少しでもあれば幸いです。
C++11には他にもinitializer listなどの便利機能があるので興味があればチェックしてみてください。

なんか、僕が書く感じのジャンルじゃなさそうに見えますが、是非紹介したかったので書いてみました。
僕はあまり処理能力が高くないので、見通しの悪いコードを書くとすぐにバグを入れてしまいます。
なので、いかにコードの見通しを良くするかということをたまに考えていたりします。
その結果、この記事が生まれたという感じでしょうか。


明日は、sigma425さんの「何も決まってないです。」です。楽しみですね！

ICPC Tsukuba 2015 参加記

ICPC 競プロ

11/28昼

・チームメイトと秋葉原で合流。
・つくばエクスプレス、椅子が硬いとの噂で、コンクリート並みの硬さをイメージしていたけど、そんなことはなかった。普通の在来線という感じ。
・駅で静岡チームに出会い、着いていく。
・つくばカピオに着く。カピオはラテン語で「財産」
・会場の前でJOIOBの東大３チームがチームメイトを待っていた。
・プラクティス、キーボードの右シフトを押すと「↑」が入力されるバグに悩まされる。多分'_'キーが長すぎるせい。
・Backspaceを押すとEndが入力されるバグもあるらしい。
・という感じで、日本語キーボードの配列がやばかった。（twitterでもめっちゃ見かけた）
・環境はキーボード以外は素晴らしかった。競技者として嬉しい点は、
　・会場が適温
　・チームに与えられるスペースが広い
　・配線等がしっかりしてて、足元に電源スイッチがあってPCが突然落ちるといったことがない
　・windowsじゃなくてlinuxが使える
・JavaChallenge、さすがに２時間かつ提出して無限に待たないとフィードバックが得られないのではなにも作れず。
・紹介文に書いた迷路解いて写真アップしてもらえててうれしい。他にも解いてくれてた人がいてうれしい。


11/28夜

・懇親会、飯がうまい。皆が寿司にかまけてる間に串カツを１通り食べる。
・チームスライドはperyaudoが韓国の空港で作ってくれました。かっこいい。
・宿に向かう。宿の前に焼肉屋があった。
・風呂が混むのは容易に想像がついたので、爆速で風呂に向かう。
・しかし、準急がすでにいてさすがだと思った。
・ロビーとか研修室で雑談をした。
・歯ブラシを忘れたのでコンビニに買いに行く。コンビニ近くてうれしい。
・寝る。

11/28闇

以下闇情報です。反転すると一応読めます。
・全く寝付けず。
・今回に限らず、ICPC前日はいつも寝付きにくいが、今回は特にひどかった。
・事前に「大会どうせ勝てないしどうでもいいどうでもいい、みたいに考えることによって緊張をなくして安眠する」という作戦を考えていたが、見事に失敗した。
・結局３時間くらいしか寝られなかった。一睡もできないのとは大差があるので、まぁ良かった。
・睡眠薬試してみようかなぁ・・・
・もう完全に絶望的な気持ちでツラかった。

11/29朝

・鮭は皮まで食べる人です。（おいしいよ）
・プリンとユンケルを投入する。
・移動してコンテスト
・時間通りに開始されなさそうな気配を感じていたら、時間通りに開始されてびっくりした。

11/29コンテスト

チームメイト

・peryaudo：３年間チームを組んでいる。JOIで知り合ったスーパープログラマ。googleのインターンとか行ってて完全にプロ。きゅうりとは小学生からの付き合いらしく、いじられキャラの素養がある。
・mine：今年からチームを組んだ。高校が同じで、superconでチームを組んだこともある。ごちうさ。

チーム体制

・snuke：メインコーダー。ひたすら解く。
・peryaudo：持ち前の英語力を生かし、主に問題文を読んでもらう。ライブラリを写してもらったり、サンプルを試してもらったりもする。ちょっかいをかけると楽しい反応をしてくれるので、和む。
・mine：精度の高い仕事をしてくれる頼れる仲間。主に環境設定、幾何・グラフ系のサンプルの図示、数式の計算などをしてもらう。複雑な状態を持つDPの問題の遷移の係数を表す14*8くらいの表を埋めてもらったとき、全部合っててびっくりした。
・問題文について：問題文を簡潔に伝えてもらうというのはもちろん重要だけど、制約・入力がdistinctかどうか・問題の細かい設定などを聞いたら答えてもらえるというのも実に助かる。

記録・感想

・開始後はとても穏やかな気持ちだった。
・ユンケルのおかげか、結構眠さとかはなかった気がする。
・いつもは慌てて問題を解いてハマって余計に時間がかかるというパターンが多かったので、今回は冷静にゆったりと問題を解くことにしていた。
・mineに設定をしてもらってる間にAを読む
・これsubsequenceじゃなくない？と思いつつやるだけなのでやる。
・サンプルをダウンロードできるページ情報を得るためにclarを投げる。
・Bから悩ましい問題だなぁと少し驚きつつも、他のチームもどうせ驚いてるだろうと思いつつ解く。なぜかDAGの最長経路問題に落として解いた。
・Cで今回のセットは前半の重さが増していると確信しつつ、冷静にやる。
・D、時間がかかりそうなので飛ばすべきかと思いつつもABCの次にD以外をやっているチームがなかったのでやる。
・E、桁DPを考えるがprod無理じゃね？となるが、2,3,5,7で何回割れるかを状態として持てば良さそうとなり実装する。添え字がやたら多くて笑いながらコーディングする。
・DPテーブルを再利用してもメモリが足りなかった。
・prodをmapで持った方が状態数減るしなんとかなるやろと思いmapに切り替える。
・TLが1秒なのに実行してみると2秒近くかかってあーと思うが、O2をつけたらなんとか1秒に納まりそうだったので投げたら通った。
・あらかじめ積を列挙しといて状態をlower_boundとかでintに変換すれば高速化できそう。
・ここまでずっと５〜９位くらいだったのでこの調子で行けば良さそうと思う。
・会津が強くてびびる
・他のマークしてたチーム（台湾勢、阪大、FCCPC、筑波、九大、京大...etc）に勝っていたのでほっとする。
・Fを聞くが、複雑で少し時間がかかるが理解する。
・少し余裕がありそうだし、少し疲れたのでリフレッシュ目的でトイレに行く。
・トイレ待ち行列に行ったらいつの間にかperyaudoがいて話しかけたら係りの人に怒られた。チームメイトだけどダメか。
・小走りで席に戻ってたら「don't run」と怒られる
・「トイレに行くだけで２回怒られる男」とperyaudoに煽られ続ける
・F、問題さえ読めばC~Eより簡単。
・問題文に乗ってないサンプルのデータが合って、それだけ答えが違った。
・デバッグしてAC
・G、むずそうなのにA~Fを埋めるより先に解いてるチームがいくつかあってビビる。
・H~Kを聞いてみて、Gをやることを決める。
・結構悩んだ末AC。よくできた問題だった。
・「長さがhogeの回文」ではなく「長さが最短な回文」であることが重要であることに気づくのに時間がかかった。
・解かなければならない問題は全部解き切ったので少し休憩をしつつI,Jあたりを考える。
・残り45分くらい、そろそろどれに取り組むかを決める必要があった。
・H、Jは時間的に無理そう。
・Iでなんらかの嘘解法を生やして枝狩りとかを入れつつ提出しまくるというのも魅力的な選択肢。
・Kは簡単な場合はCFで最近見たなぁと思った。
・残り時間的にはIかKだと思ったけど、台湾がKを解いていたのを見てKにする。
・嘘解法を生やすも、撃沈。
・終了...しなかったので暇を持て余す。
・周りを見渡して凍結後に増えた８完がいないことを確認する。
・阪大チームが延長戦でAC出してたのが楽しそうだった。

コンテストまとめ

・過去の参加経験を生かして「冷静」を実践できたのはよかった。
・持てる力の80%は出し尽くせた（bestを尽くせなかったという意味ではない）かなと思う。これ以上出そうとするとハマる確率が上がって安定しないので後がない状況では最善の戦略だったと思う。
・結果は8位、大学別6位でした。
・メダル枠と別地区を除くと、NTU→Aizu→Keioなので、WFの希望は残っているのではないかなぁと思う。Aizuのシンガポールでのご活躍とCJ先生に祈るしかない。
・＋１完がなかなか難しいんだよなー。今回は残り時間が少なかったから仕方ない気はするけど。
・まぁそれでも嘘を並べれば想定解でなくてもうっかり通ってしまう可能性があるかもしれないタイプのI問題を選択した方が期待値は高かったかなという反省は少しある。
・今年は結果を出したかったので、それなりの結果を出せて良かったです。
・ペナルティ0なの、すっごくないですか？

11/29昼

・解説、スケジュールの伝達ミスで巻きでやってしまったっぽくて、かなり雑だった。でもなんとなくどんな感じかは分かった。
・Java Challengeについて（負なので反転）：Java Challenge作られた方、去年４回も問題を使い回していた方なので非常に印象が悪い。今年は使いまわしではなかったので良かった。しかし、ローカルでテストできない上サーバのレスポンスが激遅だった点、IDとかが0-indexedなのに与えられる座標がどうやら1-indexed（問題文に書いてない）だった点は残念だった。
・Java Challengeがグダグダになるのはいつものことだし、それが面白いってところもあるので楽しかった。メインコンテンツでもないしまぁ多少はね。お疲れ様でした。
・謎の空白時間。
・秋葉さんのカメラから逃げる遊びをしていると、よすぽが素材としてのプロ意識を発揮する。
・表彰式。プレゼントの中身が気になる。（クリスマスはちょっと早くない？w）
・Dreadnoughtまじで圧倒的だったなぁ。あと、風船22個を阻止してしっかり9完したIIIlIIIllIIlIlIIllIlIllllllIIIもさすがだった。
・IIIlIIIllIIlIlIIllIlIllllllIIIがJOMANDAしてた。参考：


dic.nicovideo.jp

11/29夜

・閉会パーティー
・皆んな大好きK理事長の乾杯音頭
・料理は今日もわりとうまい。焼きそばが二種類あるのが謎だった。
・googleブースの謎解きがハイクオリティだった。
・ヨーヨー楽しい。
・社会人のいろんな方と話した。
・例の数式の会社の社長さん、SFCの先輩らしい。（ちなみにここでperyaudoがバイトしてたらしい）
・２つくらい企業賞をもらう。やったぜ！！
・yahooからもらったアダプタkit（しかもmac高速充電）が嬉しかった。

・東大勢と一緒のつくばエクスプレスで帰る。

11/29家

・いつのまにかタイムシフトを見はじめていた。
・眠すぎたので最後まで見れなかった。
・tozangezanのためにまとめを作った。www.youtube.com

まとめ

・日本の運営、すごいしっかりしてて最高。
・つくば以外と近いし、それでいて旅をした気分になれるので良い。（会津も好き）
・コンテストはそれなりの結果が出せて良かった。
・運営お疲れさまでした。ありがとうございました！

Sorting game

パズル 雑談 programming

謎のゲームを作った。
Sorting game
swapしてソートするだけのゲーム。

マージソート風にやるよりもクイックソート風にやった方が強いっぽい。
適当に似た色を選んでいく方法も割と強い。

マージソートのやり方

2個組、4個組、8個組までは気合。
このとき、各組はソート済みにしなくてよくて、大事なのは各組内での順序が一意に定まるようにすること。
マージ操作は色に頼りつつ頭の中で頑張る。
8個組と8個組のマージは頭の中だときつい。
小さいやつから順番に正しい位置に置いていく。
「残りのものから最小の数を見つける」という操作が必要になるが、そのような数の候補は２つしかないので極小のもの２つを見つけて比較すればいい。
操作数はだいたい60くらいかな。