ICPC Tsukuba 2016 参加記

競プロ ICPC

慶應義塾大学のチーム「Running」として参加し、３位の銅メダルでした。
メダルを取ることが出来たのは初めてで、とても嬉しいです。

時系列順で感想を羅列していきます。

コンテスト前日

つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯を食べた。

プラクティスでは、キーボードの癖の把握とスタックサイズの調査をすることにしていました。
キーボードは重めでびっくりしましたが、打ちやすくとても良かったです。
いつもはMacで⌘→で行末に移動しているので、Endキーを押さないと行末に移動できない環境には少し戸惑いましたがそんなに大きな影響はなかったです。
時間はあと15~30分ほど長いと嬉しいなと感じました。
会場の配線は、人が通る場所に線が、去年より心なしか少なかった気がする？

懇親会は帰りのバスを待つ時間が長くて、寒かったのもあってつらかったです。

ホテルについたら真っ先に大浴場に入った。
それから、peryaudoと近くのショッピングセンター的なところで買い物をした。
レジが半自動ですごかった。
ホテルに帰るときにライトアップされた変な建物を見つけた。
だいたいこういうのってラブホテルとかいうやつなんですが、それにしては大きいなぁと思って調べてみると、近くに保育園があって、教会系の結婚式場なのではという結論になった。納得した。

夜は結局寝れなかった・・・
結構眠気が強かったので寝れそうだと思っていたんですが、２時間ほど浅い睡眠をしたあとに廊下の声とかで起きてしまって、そこからは絶望の時間が始まりました。
なんか今年も１時くらいに暴走族がいたんですが、これIOIやったときにもいたら日本の印象的な意味でアレそう。
結局1~2時間くらいしか寝れなかった。

コンテスト当日

わりと眠かったですが、プリン食べてユンケル飲んで乗り切りました。（去年もそうした）
入場する前にタイピングソフトをやってみたところ、そこまで悪くない速度だったので少しだけ安心しました。
（これが遅かったら脳の回転速度が相当低下しているということで、やばかった）

コンテスト中の動向

うちの体制は、A,B をperyaudoに投げて、その間に先の問題を読んだり解法を考えたりしておくという感じです。
その後は２人に問題を読んでもらって、ライブラリ写してもらったりサンプル図示してもらったり手計算を投げたりとかする感じです。

A

開始直後peryaudoに投げたら一発で通してくれた。

D

Cが簡単だったのでperyaudoに投げてみて、Dからやった。
１回WAを出して直して投げたら、map<vector<int>,int>のせいでTLEしてしまった。

C

ジャッジ待ちの間にperyaudoに聞くと少し自信がなさそうだったので、自分でやることにした。
出力を改行区切りにしてしまって１WA食らった（だめやん）

D2

ハッシュに書き直して投げたけどWA。もうちょっとちゃんとハッシュを組まないといけなかったっぽい。

B

Cやってる間にperyaudoに読んでもらっていたので、やってもらった。１発ACいいぞー。
罠があったっぽいですが、少しのデバッグで乗り切ってたのはさすがっすね。
コーディングしてもらってる間に問題文を聞いたりした。

D3

vector<pair<vector<int>,int>>をsortすることにしたら通った。
TLEでハマるのはかなり泥沼なので、この程度のロスで済んだのはよかった。
ただ、ペナルティを結構食らったので、以降はペナルティをあまり意識しない方針にした。

G

E,Fがパッと見では分からず、順位表見たらGが解かれていたのでGに行く。
はじめsetを書こうとしたけど使わなかった。
細かいバグを何回か埋め込んで、3WA食らった。

E

Iが見た目簡単そうに見えたけど、WAしてるチームがあったしやめといた。
（そのとき考えてた方針は結局計算ミスしてて全然ダメだった）
次にやるものがないなーと思っていたけど、Eは同じ記号を違う文字に割り当てられないのに気づいて、それならただの実装問題やんとなり、これをやることにした。
再帰下降構文解析は頭を使わずに書くだけでいいので楽ですね。
末尾に'$'とかをつけておくと配列外参照とかを防げて楽でした。
（イテレータを正しくインクリメントするのだけは気をつけないといけないけど）
文法が正しいかまで含めて式を評価しないといけない問題だったので少し不安だったけど、１発で通ってびっくりした。

F

Jが解かれていたけど幾何だし、通してた中国チームはなにか類題を見たことがあったっぽい雰囲気を感じたのでやめた。
とりあえずFに取り組んだ。
問題設定がなかなか独特で、どうアプローチすればいいのかに悩んだ。
2-SATっぽい雰囲気のある設定だったけど、全然そんな形にはできなさそうだった。
mineとサンプルの具体例を構成してみた。
sample3がなぜYesなのかを考えていると、大体の条件はfalseにして置けばOKなことに気づいたので、その方向で考えていくと解法がわかった。
計算量は適当でも間に合いそうだなーと思っていましたが、BFSで次の辺を見つけるパートを合計O(N^3)でやらないといけないことに気づき、少し考えたけど、すぐ分かって良かった。


あとで聞いた話だと、64bit高速化とかで乗り切ったチームとかもいたっぽいですね。
解法の証明は甘々にしかしてなかったので怖かったですが、１発で通ってびっくりした。

この問題不思議な問題で、なんかプロコン慣れしてる人ほど苦しんでたんじゃないかと思います。
解法自体のユニーク性、O(N^3)に落とすパート、面白い問題だと思いました。
少し感動して気持ちが上がった。

この時点では２位だっけ。

H

とりあえずIの両辺が10^9の正方形のケースでの解答の構成をチームメイトに依頼して、Hを考えた。

なかなか一筋縄ではいかないなぁと思った。
とりあえず、無限判定について考えてみると、無向辺で繋がってる頂点を縮約してやるといい感じになることに気づいた。
無向辺だけ見たときにサイクルがあればダメで木になるので、木を頂点としたDAGで最長経路を求められれば良さそうとなる。
木の最長経路パートは、

「木に分解」「DAGを作る」「DFSする」「DFS内でダブルスイープ」とやることを分かりやすいパートに分割出来て、あまり頭を使わずに実装できるので量は多めだけど楽な実装だった。
それでも量は多い実装なので、１発で通ってびっくりした。

「木を頂点としたDAGにすればいい！」って気づいたときは感動しました。

また、グラフを変換する方針があるらしいです。


面白い方針だと思ったのですが、少し実装の見通しが悪くバグのリスクが高いこともあり、僕なら木に分解する方針を選びます。
一般に「自分の書き慣れた形」を組み合わせてコードを書いていくとバグを出しにくくなる気がしています。

I

Hやってる間にmineが一辺10^9の正方形の構成を思いついてくれて、それを長方形に拡張したときに何が問題になるかとかの部分まで考えてくれていて、それを聞いたら解法を思いついた。
制約からルートで分割しそうなオーラは感じていたんですが、どういう分割をするのかは思いついてませんでしたが、チームメイトと議論してるうちに正しい解法へとたどり着けました。チーム感を感じたり、そもそも解法が面白くて感動したりで、気持ちが上がった。
extgcdあんまり使い慣れてなかったので不安でしたが、１発で通ってびっくりした。

この時点では４位と２完差の３位だったし、９完が出てもペナルティで勝てそうだったので３位を確信して少し肩の荷が降りました。

K

上にも下にも差があったので解いてもあまり変わらなさそうでしたが、１時間弱あったしやりました。
気が抜けたこともあり、睡眠不足が効いてきて意識朦朧としてました。
peryaudoと話してたら和んだ。

結局解けず終了。

      • -

とりあえず解けなかった問題に関しても感想を書きます。

J

三角形と円の共通部分面積のライブラリは持っていたのですが、探索方法が思いつきませんでした。
解説でいろいろアルゴリズムが紹介されていてすごかった。
きゅうりに教えてもらった解法を上げておきます。

x軸方向とy軸方向で独立に３分探索をします。
というのも、多角形が凸多角形なため、x軸方向だけで中心を動かすと凸関数になっています。y軸方向もしかりです。
なので、x軸で３分探索をして、その評価関数内でy軸方向の３分探索をすれば良いです。

補足：まず、例えば長方形のときとか凸関数ではない。（ただ値が変化しない区間は必ず最大値を取るということは証明できるかもしれない）
あと、面積が０になる区間はうまく避けないと三分探索が機能しないので注意しないといけない。

K

唯一不満を持った問題です。理由は思いつきようがないようなマイナーな知識を要求するだけの問題だからです。（申し訳程度の半分全列挙はありますが。）
いや「こんな知識を知ってるなんて、よく勉強してるなぁ」という風に、一応一理はあると思うんですが、デメリットの方が多いと思います。
あまりマイナーな知識を要求されると大会に対する対策のしようがなくなり、モチベーションが下がります。
また、ICPCはネット検索などもできず論文を検索したり出来るような大会ではないので、「出典：〇〇」のような問題は少し場違いに感じます。
参加者のフィードバックとして参考にしていただけると幸いに思います。

ただ、この知識自体はとても興味深いものです。
もしブログなどで出会ったとすれば素直に感動したりしそうです。
出典の本に関しても関心が高く、ぜひ読んでみたいと思います。

コンテスト後

体調最悪で、解説まではだいたい寝てました。
PFN勢がたくさん来ててすごかった。
解説は結構じっくりやってました。
順位表解凍はネイティブな感じでいい感じでした。
終了時の予想通り、前述の通り３位でした。
ただ、１位が全完していたのは予想外でした。SJTUさすがだなぁ。
３位はつくば賞とPFN賞をもらえました。

まとめ

日本のICPCは本当に上質なコンテストで、今年も本当に良い大会でした。
去年の参加記にも書いたことと少し被りますが、他のアジア地区よりも、クオリティが高いと思っています。
会場設営、スケージュール、コンテンツ、問題セット、運営・進行、スポンサー、放送、などなど、全てにおいてコンテストに関わる人の熱意がすごく感じられ、参加している私自身とても幸せな気持ちになりました。本当にありがとうございました。

他にも書きたいことはありますが、とりあえずまずは11/6あたりのジャカルタ大会頑張ります。

最小流量制限付き最大流

Algorithm topcoder

SRMで最小流量制限付き最大流が出ました。（SRM694Div1 Hard）
とりあえず自分がやった方法をメモしておきます。

まず、下図のようなグラフのs→tの最大流が求めたいとする。
f:id:snuke:20160710041224j:plain
以下のように変換する。（蟻本に載ってる図と同様）
f:id:snuke:20160710041307j:plain
超頂点S,Tを作り、u→vにL以上R以下の辺があるとき「u→vにR-L（黒）」「u→TにL（青）」「S→vにL（青）」の辺を張る。
「S→sに∞（緑）」「t→Tに∞（赤）」の辺も張る。
この変換により、最小流量制限を外す準備は整った。
しかし、このまま流すと青の辺に十分な量が流れない可能性がある。
そこで、以下の手順でフローを流す。
1. 緑と赤の容量を0にして流す
2. 緑の容量を∞、赤の容量を0にして流す
3. 緑の容量を0、赤の容量を∞にして流す
4. 緑と赤の容量を∞にして流す
このように流すことによって、青の辺を優先的に使うフローが求まる。
こう流したあとの残余グラフで青の辺に容量が残っていたら条件を満たすフローが存在しない。
（追記：コメントで教えてもらったのですが、緑と赤を張らずに、S→T・s→T・S→t・s→tの順に流せばもっと楽ですね。）

また、上記と同じようなことが最小費用流でも実現できる。
緑と赤の辺だけのコストを1にして残りを0にすればいい。
実行速度は遅くなるが、実装は楽そうだ。


フローまだまだ知らないことがあるなぁ・・・とりあえず、最小費用循環流の解き方が知りたい。

Mo's algorithm とその上位互換の話

競プロ Algorithm

最近 Mo's Algorithm - Codeforces をよく目にする気がします。
興味深いアルゴリズムではありますが、より良いアルゴリズムがあります。
追記：「上位互換」と煽っていますが、実装量・定数倍の面から、Moが使えるときはMoを使ったほうが良いでしょう

Mo

まずはMo's algorithmの概要を説明しておきます。

Mo's algorithmは以下のような問題に適したアルゴリズムです。

長さNの数列に対し、Q回の区間クエリを処理する。
ただし、[l, middle) と [middle, r) の結果をマージすることはできない。（できるならsegtreeでいい）
・値の追加操作ができる。（[l, r) から [l-1, r) や [l, r+1) が求まる）
・値の削除操作ができる。（[l, r) から [l+1, r) や [l, r-1) が求まる）

つまり、区間の結果をマージする操作がlogとかでできず、区間を１つ伸ばしたり縮めたりするのがlogとかでできる場合。
クエリをリンク先の記事のソースコードのようにソートして、区間を伸縮しながら処理するというのがこのアルゴリズム。

クエリの l と r を２次元座標にプロットすると一目瞭然です。
f:id:snuke:20160701022948j:plain
（本当は l >= r の領域には点がありませんが、本質的な差はありません）

  • 赤点はクエリを、黒線は区間の伸縮の様子を表しています。
  • 緑線で区切られた領域は√N個あり、それぞれの高さは√Nです。

このとき、横移動（rを増減させる操作）に注目すると、左端から右端までの逆戻りなしの往復が√N回となるため、全体の長さは O(N√N) となります。
そして、縦移動（lを増減させる操作）に注目すると、ひとつの点に対して高々√Nなので、全体の長さは O(Q√N) となります。
つまり、計算量は O( (N+Q) √N * [伸縮１回の計算量] ) となります。（厳密には + Q log Q だけど本質ではない）

追記：区切る領域の個数を√Q個（高さはN/√Q）にすると計算量はO(N√Q)になるらしい、なるほど。（横移動はそのままで、縦移動はQN/√QでこれもN√Q）
こっちの計算量の方が上記よりも良いこと（ O(N√Q) ≦ O((N+Q)√N) ）を示しておく。
両辺を√Nで割って O(√N√Q) ≦ O(N+Q)、両辺二乗して O(NQ) ≦ O(N^2+Q^2+NQ)。

実装

実装自体はイメージよりもだいぶ軽いです。

int n; // 数列の長さ
int q; // クエリ数
vector<int> l(q), r(q); // クエリの[l,r)
/* 入力 */

// ソート
int sq = max(1, int(n/sqrt(q)));
vector<int> qi(q);
for (int i = 0; i < q; ++i) qi[i] = i;
sort(qi.begin(), qi.end(), [&](int i, int j) { // クエリの順番をpair(l/sq,r)でソート
  if (l[i]/sq != l[j]/sq) return l[i] < l[j];
  return r[i] < r[j];
});

// クエリの処理
// add(i)は追加操作、del(i)は削除操作
int nl = 0, nr = 0; // [nl,nr)
for (int i : qi) {
  while (nl > l[i]) --nl, add(nl);
  while (nr < r[i]) add(nr), ++nr;
  while (nl < l[i]) del(nl), ++nl;
  while (nr > r[i]) --nr, del(nr);
  /* クエリの結果計算 */
}

上位互換

Moの上位互換のアルゴリズムは上記のようなクエリを処理できます。しかも、削除操作ができる必要がありません。
その代わり、データ構造にはrollback(+snapshot)メソッドを実装する必要があります。
rollbackはその名の通り、snapshotを撮った位置までデータ構造の状態を巻き戻すメソッドです。
rollbackは、 <配列のindex, 元の値> のペアを記録しておいて時系列の逆順に戻すようにやります。データ構造が複雑な場合はindexの代わりにポインタで持つと良さそう。
これは追加操作と同じ計算量になります。なぜなら、追加操作の計算量がO(log N) だとすると、追加操作で行われる代入の回数は高々O(log N)にしかならないためです。

アルゴリズム

まず、長さが√N以下のクエリを愚直に全て処理します。（クエリあたり O(√N * [追加操作の計算量] )）
残りの長さが√Nより大きいクエリを l/√N の商で仕分けます。
それぞれのグループのクエリたちの処理は以下のように行います。
f:id:snuke:20160701031448j:plain
1. グループ内のクエリ区間を右端の昇順にソートしておく。
2. グループ内のクエリ区間の左端をギリギリ超えるような √N の倍数を X とする。（緑の縦線の位置）
3. [X,X) から始めて、右端を１つずつ伸ばしていく。
4. 現在の右端がクエリ区間の右端と一致したらsnapshotを撮る。
5. 左端をクエリ区間の左端まで伸ばす。
6. rollbackして 3. に戻る。
右端を伸ばす回数は１グループあたり O(N) なので、全体で O(N √N) 回です。
左端を伸ばす回数は１クエリあたり高々 O(√N) なので、全体で O(Q √N) 回です。
これらをまとめると、計算量はこれまた O( (N+Q) √N * [追加操作の計算量] ) となります。

追記：Moと同様に、√Q個に分割するとO(N √Q * [追加操作の計算量])になって計算量が真に良くなります。

以下はrollback（とsnapshot）がついたUnionFindの実装例です。

struct UF {
  vector<int> d; // 根の場合は高さ*-1、子の場合は親の番号が入る
  vector<pair<int,int>> history;
  UF(){}
  UF(int mx):d(mx,-1){}
  int root(int x){
    if(d[x] < 0) return x;
    return root(d[x]);
  }
  void unite(int x, int y){
    x = root(x); y = root(y);
    if(x == y) return;
    if(d[x] > d[y]) swap(x,y);
    if(d[x] == d[y]) {
      history.pb(make_pair(x,d[x]));
      d[x]--;
    }
    history.pb(make_pair(y,d[y]));
    d[y] = x;
  }
  void snapshot() {
    history.clear();
  }
  void rollback() {
    while (history.size()) {
      d[history.back().first] = history.back().second;
      history.pop_back();
    }
  }
};

このアルゴリズムでこれ（UF+区間クエリ）とかが解けます。
ちなみにこれ自分で考えて喜んでたら、Moの記事のコメント欄にも載ってました。
名前があった方がウケがいいらしいので、Rollback平方分割とでも呼ぶことにしようかな。
ちなみに、追加クエリが均し計算量の場合は注意が必要です。

まとめ

汎用性の高い Rollback平方分割 の方を覚えておいて損はないと思います。
Mo's algorithmも、上の方にある図を覚えておけばすぐに思いつける程度のものだし、忘れる必要はないです。
ただ、実用上では必ずしも上位互換というわけではなく、削除操作が出来てかつ「削除操作の実装 < 分割+rollbackの実装」の場合は実装量の面でMo's algorithmの方がいいかもしれません。追記：あと、定数倍もMoの方が良いっぽい。

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;
}