とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

AGC 016 C (+/- Rectangle) と Farkas' lemma

AGC 016 Cを考えていると気づいたことがあるので、紹介します。

まず、AGCの問題文 : C: +/- Rectangle - AtCoder Grand Contest 016 | AtCoder
この問題は要するに、局所的には負にしつつ、全体は正にする、というような気分のような問題です。
私も結局よくわからず、最後は答えを見てなるほど～～、と言っていました。

では次にFarkas' lemmaを見てみます。
Farkas' lemma - Wikipedia
これはリンクにある問題2つのうち、必ずどちらか一方のみに解がある、というなかなか面白い補題です。

この式の2番の方に着目してみましょう。{y=-y'}として{y'}で式を立てれば不等号の向きが入れ替わります。

さてこの式、AGCの方の問題とほぼ同じではないですか？

{b}を要素がすべて1のベクトルすれば{b^T y' > 0} は正にする制約だし、
{A}側も、適切に設定すれば局所的に負にする制約にできます。

じゃぁこのとき、1式はどうなるのか。これは各小長方形1つに変数が1つ対応して、これが{x}になります。
{b}はマス1個に対応して、どの要素も1。{Ax}は小長方形の重み{x}をそれが含む各マスに足しこむ操作とみなせます。

ここまでわかれば、1式が解をもつかどうかはすぐにわかり、{H}が{h}の倍数かつ{W}が{w}の倍数であることが必要十分になります。
すると、2式が解を持たないための条件はこの条件だとわかるのです。

ということで、解が存在する・しないの判定は、このようなアプローチで見つかることがわかりました。（やったね！）

AGCの問題を解こうと思うと、ここからさらに構成する必要があるのですが、
このアプローチだけだと少し厳しそうに見えます。
というのも、Farkas' lemmaのアプローチで解{y'}を構成しようと思うと、
分離超平面を構成する必要があります。
これを今回の大きさの行列に適用するのはしんどいので、特別な性質があればよいのですが、
ぱっとはわかりませんでした。

誰かわかる人がいれば教えてください。

JOI春合宿2017 Day1 手持ち花火（Sparklers） の別解と上位問題の解法

こんにちは。今回はタイトル通りのことについて気づいたので紹介していこうと思います。
一応注意をしておくとネタバレを含むので、見たくない人は見ないでください。
また、この記事を書くにあたってsnukeさんに多大な助言をいただきました。この場で感謝します。

この問題の詳細はこちらをどうぞ。
JOI 2016/2017 春季トレーニング合宿 課題

読み進めるとわかりますが、一部想定解法は上記にある解説ページがベースになっています。
また、のちのちSegmentTreeが現れますが、かなりざっくりとした説明ですので、SegmentTreeを知らないと読めないと思います。

問題文

まずはこの問題の問題文を整理するところから始めます。

  • {N}人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
  • それぞれの花火に火はついていない。
  • {K}番目の人は時刻{0}に自分の花火に着火する。
  • 花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
  • それぞれの花火は着火後{T}秒で消えてしまう。
  • それぞれの人の花火は1度までしか着火できない。
  • 次のことができる各人の移動速度の上限{s}として最小のものを求めよ : 時刻{0}より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

整理

  • 入力は{N,K,T}と各人の時刻0での位置{x[i]}
  • 出力は最小の移動速度の上限{s}

重要な制約

  • {N \leq 10^5}

解法

基本的にはスライドを参照すればよいが、ここで簡単におさらいする。

記法 : 以下{x[i]}の最大値を{U}とする。

{O(N^2 \log U)}時間解法


まずは二分探索したいので、移動速度の上限{s}を決め打ち、ある上限速度{s}ですべての花火が点火されるかを判定する問題を解くことにする。この問題もそれなりに難しく、正当性を確かめるのに少し苦労はするが、次のような結果を得る。

まず、{L \leq K \leq R}となる{L,R}を用意する。
このとき、区間{[L,R]}に入るすべての人に花火をつけるためには{(x[R] - x[L]) / (R - L) \leq 2sT}である必要がある。

逆にこれを達成するためには、{L=R=K}からはじめて({L}をデクリメント) or ({R}をインクリメント)のどちらかの操作を繰り返し、上記式を常に達成できれば良い。

つまり、すべての{L,R}について{(x[R] - x[L]) / (R-L) \leq 2sT}をチェックし、その結果をoxを用いてグリッドに書き込めば、
そのグリッドの左下から右上まで oのみを使って到達できるかどうかを判定する問題になる（下図参照）。

f:id:tokoharu-sakura:20170410224334p:plain

これで{O(N^2 \log U)}時間で計算できることがわかる。

{O(N \log U)} 時間解法（解説スライドにおける想定解法）

上記の解法に工夫を加えて{O(N)}程度に落とすために、まずは式変形をして、
{x[R] - 2sTR \leq x[L] - 2sTL} とする。
この式は非常に都合がよく、{X[i] := x[i] - 2sTi}とおけば
{X[R] \leq X[L]}で判定可能である。

これを眺めるとうまい性質がわかる（らしい）ので、それを用いると貪欲的に解けるという主張になる。
（あとはスライドを読んでください）

別解

ここからは考えた別解について説明していきます。
その際、書き込んだoxの性質についてみていきます。

oxの並び方の観察

まず、次の性質が簡単に示せます。

性質1 : 次の図のような配置はありえない。
f:id:tokoharu-sakura:20170410224338p:plain

証明はXを用いれば簡単にできる。
oxが書き込まれる条件を思い出せば
{X[j_2] \leq X[i_2]},
{X[j_1] \leq X[i_1]},
{X[i_1] < X[j_2],}
{X[i_2] < X[j_1]}が得られる。
これらをすべて足せば {0< 0}が現れるため矛盾する。

次に、ある種貪欲的に進めてうまくいくことを示す。
そのために次の性質2を示す。

性質2 : まず、到達可能性を定義しておく。{(L,R)=(l,r)}に到達可能であるとは、{(L,R)=(K,K)}より始めて{L}をデクリメントもしくは{R}をインクリメントを続けて、x印を通らずに{(L,R)=(l,r)}に到達できることと定義する。
仮に、{(L,R)=(i,j)}が到達可能かつ、{(L,R)=(i,j+1)}が到達不可能であるとし、さらに{i}より小さい{t}に対して{(L,R)=(t,j+1)}にo印であったとする。この{t}は最小(図で考えると一番上)のものをとることにする。
このとき{(L,R)=(t,j+1)}に到達可能であることが言える。
特に、下図の赤印のような関係になっていることが言える。

f:id:tokoharu-sakura:20170410230417p:plain

この証明は性質1を用いればできる。つまり、図の赤o印の箇所を{(i_2,j_1)}とおき、{j_2=j+1}とおく。{i_1}は{(i_1,j_1)}がo印になっているようにとる。
このとき、性質1より

ox
xo

のような位置関係は禁止されているが、
上記のように{i_1,i_2,j_1,j_2}を定めれば

ox
?o

のような位置関係になっていることがわかる。
性質1より'?'はo印にしかなりえない。
これを繰り返せば赤印のような箇所にo印をつけることができるため、
結局{(t,j+1)}も到達可能であることがわかる。

アルゴリズム

さて、以上の性質2を使えば、次のような遷移をして右上マスに到達すればOKであることがわかる。

  • 最初は{(L,R) = (K,K)}とする
  • o印である限り、{L}を減らす(上へ進む)
  • Rをひとつ増やす。
    • もしoであれば上記のように{L}をできるだけ減らす
    • そうでなければ{L}を増やして(つまり下に進んで)o印が書かれている箇所を見つける(性質2より、これをみつければ必ず{(K,K)}から到達可能。)
      • もしそのようなo印がなければ失敗。最初に定めた制限速度{s}では不可能であることがわかる。
  • 最後に{(L,R)=(1,N)}に到達すればOK

要するに、各{R=r}に対して到達可能な{(L,R)=(l,r)}である{l}のうち最小のもの（一番上にあるもの）を求めていることになる。

単純に進めるだけでは時間計算量の上界は{O(N^2)}であるが、{N^2}回程度の移動回数を必要とするような入力はこのアルゴリズムに気づかなければ構成が難しい。
ということで最悪で{O(N^2)}時間かかるコードを実装して提出してみたが、春合宿で用意されたデータセットすべてに正答することができた。

改良アルゴリズム

さて、改良できそうな箇所は最も近いx印の場所を求めたり最も近いo印の場所を求めることである。

これは次のようなアルゴリズムで実現可能である。
都合上片方のケースのみで考えるが、問題は次のように言い換えるとわかりやすい。

「配列{X}とインデックス{i} が与えられる。 ただし{X[R] \leq X[i]}であるとする。
{i}より小さい{j}のうち、{X[R] > X[j]}となるような最大の{j}を求めよ。」

これは次のようなデータ構造を持てばできる。
例えば最小値を持つRMQを用いて二分探索のようなことをする。
まず{O(\log N)}個くらいの調べたい範囲を持ってきて、それぞれの最小値を調べる。
これらの中ではじめて最小値が{X[R]}を下回る箇所を持ってくる。
この範囲で、segment tree上で二分探索をすればできる。
これは1クエリあたり{O(\log N)}時間で計算できる。

この解法から現れる上位問題

さて、ここまででtokoharuの考えた別解を紹介しましたが、想定解法のアルゴリズムをちゃんと理解している人であれば想定解法の方が好ましいと考えるかと思います。なぜなら想定解法の方が（たぶん）シンプルにほぼ線形時間アルゴリズムを構築できるからです。

とはいえ、この別解からは面白いことがわかります。
それはSparklersの上位問題が解けてしまうからです。

ここで上位問題の問題文を記述することにします。強調した部分以外は同じ文章になります。

  • {N}人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
  • それぞれの花火に火はついていない。
  • 誰か一人が時刻{0}に自分の花火に着火する。
  • 花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
  • それぞれの花火は着火後{T}秒で消えてしまう。
  • それぞれの人の花火は1度までしか着火できない。
  • 次のことができる各人の移動速度の上限{s}として最小のものを求めよ : 時刻{0}より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

太文字で強調した通り、{K}が消えてしまい、スタートが誰でも良くなってしまい、難易度が上がります。
しかし別解と同様の方針で考えればこの問題でも解くことが可能です。

これを確かめるために、もう一度「性質1」と「性質2」を確認してみます。
よく考えるとこの二つの性質は図を180度回転しても成立することがわかります。
つまり、性質2で出てきた到達可能性について{(L,R)=(1,N)}を始点としても同様の性質が成り立つことがわかります。

これがわかると、次の図のような到達可能性を調べればよいことがわかります。
f:id:tokoharu-sakura:20170411005130p:plain

この180度回転バージョンでは、各{R=r}について、到達可能な{(L,R)=(l,r)}の中で最大のl（一番下のo印）を求めることになります。
そして、これが{l=r}となるグリッドに到達すればOKということになります。

まとめ

Sparklersはより上位の問題に拡張できました。やったね！

競プロとLP双対まわりの話で最近知ったこと

こんにちは。tokoharuです。

これは
Competitive Programming （その2） Advent Calendar 2016 - Adventar
の12/7の記事です。

問題も稀にしか確認しなくなりましたが最近得た知見をここで報告・宣伝しておきます。少々マニアックな記事です。

概要

私のtwitter(鍵)を確認している人はご存知かもしれませんが、二年前に公開したドキュメントhttp://tokoharu.github.io/tokoharupage/docs/formularization.pdfを改訂しました。内容はフローとかLPとか双対とかそのあたりの話です。元々は自分だけ読めればよかったものを少しずつ他の人に読めるものに変えている途中なのでまだまだ読みにくいかもしれません。特にLPとかの話は情報系学科の人でも触りくらいしか知らないでしょうし...

それから最初のほうにLPを用いた細かな話をしているので挫折する方もいるかもしれませんが、Project Selectionあたりの話はちょっと毛色が異なるし、おそらくこのドキュメントで最も実用的な箇所なのでそこを読むのがよいと思います。

知見1（最小費用流問題の双対っぽい問題への対処）

LP双対をとって最小費用流問題に帰着させるような問題は双対という操作を覚えないといけないし、操作を間違えやすい意味で厳しい問題という印象でした。しかし、最近yosupoさんの力を借りることでいい感じに解釈して辺を張ることに成功したかと思います。
この考え方をマスターすれば、例えばHow to create a good game(AOJ-ICPC 1100点, 2016/12/6現在)の解法を紙を使わず頭の中だけで構築することも可能かと思います。

知見2（牛ゲーの罠）

書いた文章をもう一回読んだり検証したりして気づいたのですが、
AOJ0304はデータセットが甘いっぽいことに気づきました。
今後こういう問題を作るときはこういうケースを仕込んでおいてガンガン落としていきたいですね。
詳しくはこの記事をご覧ください :
tokoharuland.hateblo.jp


今後

最近はフローで解くと部分点でさらに深い洞察を踏まえることで高速なアルゴリズムを導く系統の問題が増えてきたような気がします。そういう問題は結局はフローの特殊ケースであるといえることもあり、こういうのもいずれ体系立てれたりしないかなぁと思ったりしますがそんなにちゃんと考えてないです。背後に何かいい感じのものがあったりしないかなぁ。

今年の JOI2016 春合宿「最悪の記者2」, KUPC2016 H「壁壁壁壁壁壁壁」なんかの問題はこの意味で非常に興味深いですし、作問者の方は素晴らしい問題をありがとうございます。この系統でいくとhttp://codeforces.com/contest/724/problem/Eもですね。この辺は深く理解したいですね。

次のアドベントカレンダー担当者

明日はskyさんとyosupoさんですね。

skyさんとは長い付き合いのはずなのにあまり話してない気がするのですが、
きっと彼の印象に残ってるイベントとぼくの印象に残っているイベントはかぶってる気がするので楽しみです。

yosupoさんは言わずもがなで、どんなネタを提供してくれるのか楽しみです。

AOJ0304がコーナーケースを入れ損ねてるっぽい話

競プロとLPまわりの記事 :
github.com
をupdateしたくなったので色々整理しているとこういう話になっているっぽいことを確認しました。

まず、次のふたつのACされたコードを用意します。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1197971#1と
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1270321#1

これらに

5 4
1<=2-2
4>=3-2
5>=4-1
5>=3+4

の入力を与えるとき、前者はinf,後者は-1が出力されます。

入力に対する解説をすると、
始点1から到達不可能な点であっても負閉路が検出されるときは
validな配置が存在しないため-1になるべきということです。

それぞれのBellman-Ford法を眺めてみると、
前者の実装では始点以外INFで初期化をしてINFがあれば更新をしないのに対し、
後者の実装では始点以外INFで初期化をしたもののINFがあっても更新をしています。
この差が反映されて出力の差異が発生しています。

これらのコードが両方ACされているため、
ジャッジケースにはこういうコーナーケースは入っていないのだと思われます。
今後、類題が出題される、もしくは類題を出題するときには気をつけたいところです。

2015 JAG Regional J : Longest Shortest Path

原案出しました。
この問題は考察が非人道的ですが、壁を突破した後にたどり着く解法は美しいものです。


今回は感想や小話を書いたり、中の人の議論ページにあるのをちょっと編集して貼り付けます。

感想や小話

解法を知りたい人はもう少し下を眺めてください

提案直前

  • モチベーションとして、LP双対をとる問題を作りたかった
  • 手本ポジションにHow to create a good gameという問題があるので、この問題と似たような状況で双対とって遊んでいれば面白そうなので遊ぼうとなる
  • できた
  • 下記解法(1)が見えたのでとりあえずMi_Sawaさんに相談
  • 確かに双対をとった結果は同じということを確認し、解法(2)とかで解けますねーみたいな話をされる
    • これはちゃんと理解できていなかったのでとりあえずそっちはMi_Sawaさんに任せることにする
  • 簡単な例題を解いて照合するうちに変数yが1/nばかりをとることに気づく。
  • これに沿って変形することで費用流一回で解けそうな何か(3)が錬成された
  • Mi_Sawaさんに投げるとしばらくしたら証明してくれた。さすが。

8月

  • とある日、だらだら5時とかまで起きてた
  • 寝ようとしたらGCJ World Finalの現地にいるMi_SawaさんからD問題を読めとの連絡が来る
  • 眠いけど読むとどうも今回のJ問題と非常に類似するとわかり目が覚めてくる
  • アイデアが同じだとほぼ類題になるので棄却の危機を感じる
  • と思って解説フェーズの動画を見るとよくわからん操作をしていて安心した

作問準備

  • C++では下記(1),(2),(3)の解法はAtCoder上で通った。それぞれ(5sec, 5sec, 0.1sec)
  • 妙に辺数が多いのはSimplex法( algorithm/SimplexMethodLP.cc at master · spaghetti-source/algorithm · GitHub)が思いのほか高速だったため。
    • M=1000程度でも下手すると通るのではぐらい速度。Simplex法恐ろしい
    • という事情でM=2000.
    • ここまでやるとようやく30秒では終わらなくなったので呪縛から逃れる。
  • その代償として、c,dの最大値を極限まで減らした。
    • これはパス反復法の理論計算量を考えた時に、制約最大値を代入をしてもそこそこ信用できる程度の量にするため。
  • ちなみに代入すると4億でした。実際には0.1secで終了します。
    • このギャップを埋める入力は良く知らないので詳しいことをご存知の方は教えてください。

終わった後の感想など

  • やーさんめっちゃ説明うまい。
    • 「グッと睨むと」みたいなフレーズの選び方がうまいなぁと思った
  • なかなか解けないよね…とは思った。
    • とはいえ解く可能性のあるチームは考えていて、
    • 先述のGCJ-WF進出者のsemiexpはワンチャン行けるんじゃないの
    • 直前にsigmaさんのHow to create a good gameを解いた記事を読んでいたので行けないかな
    • とか思っていました
  • やっぱりこの解法(3)の直感的理解がわからん。なんやねんこれ
  • 台湾はまさかの(3)で解いたので頭良すぎと思った
    • 彼らにはそこまで理解できているのか
    • もしかして何か論文かなんかあるとか？

議論ページの解法などまとめ

貪欲っぽいのを落とす入力

4 5 L 1 4
1 2 2 2
1 3 4 4
2 3 1 1
2 4 4 4
3 4 2 2

L=1の場合、最適値は6. 2->3の辺の長さを1増やす
L=2の場合、最適値は6+1/3. 1->2と3->4の辺の長さに1/3足して2->3に2/3足す
L=5の場合、最適値は7+1/4. 1->2と3->4の辺の長さに5/4足す

このように、ある辺を一旦増加させても、Lを増やせば減少させる方がよいケースがある。
なので、そのような仮定に基づくアルゴリズムは落とされる。

これをある程度突破できる嘘解法はある？



解法

この問題で求めたいのは max_x min (辺にxの距離を足したs-tパス長)。
とりあえずmin...に対して双対をとるといわゆる牛ゲーになり、全体としてmaxだけでかける

(P1)
max p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0
さらに双対をとる
(P2)
min (sum d_e f_e) + y L
s.t. fはs->tに1流れるような流量保存則を満たす
c_e y - f_e >=0
f_e, y>=0
これでほぼ最小費用流の形が出る。

ここからいくつかの方針が考えられる。

(1) (P2)のyを固定したときの最適値をg(y)とおけば、
元の問題がLPであることを考慮すればg(y)は凸関数。
また、g(y)は最小費用流で求められる。 ~
最適解は0 < y <= 1に入ることを確認してから(これは証明の意味で。実際y=1であればもとの最短長に+Lする状況になるので、それは長すぎる。)三分探索をする。

(2)
ここの欄はMi_Sawaさんが書いてくれる予定です -> 詰めきったら (3) と同じになりました... (途中で考察を止めるといちおう少し違う形になるので書いておきます)
(P1)
max. p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0

であった.

答えの値を T 以上にできるかで二分探索することにすると,

(P1')
max. 0
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
p_s - p_t <= T
x_e >= 0

を得る. sum c_e x_e <= L を満たせるかで判定問題にすることにして,

(P1'')
max. -sum c_e x_e
s.t. p_u - p_v <= d_e + x_e ... 双対変数 f_e
p_s - p_t <= T ... 双対変数 α
x_e >= 0

と -L との大小を比較し, -L 以上な最大の T をとればよい.

双対をとると,

min. -αT + sum f_e d_e
s.t. f : s-t に α 流れるフロー
0 <= f <= c
0 <= α

だから, 容量 c, コスト d のグラフで, 単位流量あたりにコストが T 以下である間フローを流し,
(フローのコスト) - (フロー量)*T と -L との大小を比較すればよい.
この時の (flow, cost) は, CostPerformanceFlow の時の折れ線の折れている部分になる.

(flow, cost) な点で cost - flow * T を -L 以上にできるのは, T <= (cost + L) / flow のとき.
よって, 各点で min((cost+L)/flow, s-t shortest path) を取り, その max が答え.
さらに詰めると, 結局とこはるさんのと同じになる.


(3)
(P2)が出たところからさらに考察を進める。
yを 1/mで置き換え、f_eをf_e/mで置き換える。
これを整理すると
(P3)
min (sum d_e f_e + L) / m
s.t. fはs->tにm流れるように流量保存則を満たす
c_e >= f_e
f_e >= 0 , m > 0
f(m) := ((P3)の条件でのmin (sum d_e f_e + L) の値)とおけば
これはm流す最小費用流の最適値にLを足したものなので、区間で線形に増える。
したがって、f(m)が線形で増える区間[l,r]でf(m)=am+bであったとすると
f(m)/m = a + b/mより、最小値をとるとすれば端点(m=l,r)である(m=0はムシ)

なので、折れ線の端点のみの結果を見て比較すればよいので次をすればよい。

  • 容量c, コストdの最小費用流に対する最短路反復法(Primal Dual)を走らせる
  • 1反復ごとに(P3)の目的関数値をチェック
  • それらの最小値が答え

その他

  • この問題のおもしろいところは、

(3)の解法で出てくるグラフの容量は元のグラフのコストとなり、コストは元のグラフの距離となり、
逆のように感じるような設定になっているところ。

  • 春コンのCost Performance Flowと似てる部分がそこそこある?
  • ぱっと見て最短路反復法と思える人はいるか？いるとすればどのくらい思いつきやすいか？

とこはるの問題

今までに作った(or原案に携わったレベルの)問題と簡単なコメント

2012年

簡単な問題を作りたかった

タイトルだけ。内容は関与せず。

基礎的なフローの問題を作りたかった

当時は列になってる数をうにょうにょするDPを作りたかったはず。

高評価をいただいて大変ありがたい問題です。
本番中はwatashi(=rejudge)さんとrngさんだけが解きました。

2014年

やっぱり簡単な問題を作りたかった

よすぽさんと話し合ってたらできた。
よすぽさんが筋のいい問題を投げてくれたのでいい感じの解法のある問題が出来た。

地味にgeneratorが面倒で、適当にやるとビームサーチが通ってしまっていた。つまるところ局所解が少なかった。そこでgeneratorではi個外食したときの最適解f(i)のようなものを考えてそれの差分を導出してこれがランダムウォークっぽい挙動をするように調整したりした。

題名だけで放り投げておいたらshimomireさんが筋のいい問題を提案してくれていたので、いい感じの解法を付けて出題された。お気に入り問題のひとつ

知識ゲーを出したかった

JAGで出そうとした問題の没問。ごく一部に知ってる人はいたけど高校生用だからいいでしょってことで出してもらいました。

2015年

超簡単な問題を出したかった

大昔uwiさんと似たような問題を議論した覚えがあるけど時効だし出してuwiさんが正解しても不公平にはならないと思ったので出した。
証明の仕方が競プロ的テク+ホールの補題なのがお気に入り。

投げやり題名。組合せ最適化に書いてある問題だけど出してみた。手で解いたときは最小平均長閉路だと思ったけど、みんな牛ゲーで解いていたのでしくじったと思った。

原題はKaraoke Schedulingだった。（人より音が取れない下手くそではあるけど）カラオケにたまに行くのは楽しいなぁみたいな気分のときに問題を作った。
それから、簡単バージョンとしてコストが二乗でなくて絶対値になっている問題も同時に提案していた。

提案時はAOJ-ICPC換算で600-700くらいで、（アイデアは）蟻本にも書いてる内容だしで、ちょうどいいぐらいの典型問題だと思って出しだけど、人々を虐殺してしまった。
writer解を作るときに割とバグらせて時間がかかったのでそのときに気づくべきだったかもしれない？
XVII Open Team Programming Collegiate Cup. ロシアだといいぐらいに上位層を選別する難度の問題として機能していたかなあという感じ。

VectorFieldを1次元にすればええやん、というそれだけ。
ただ、まじめに考えるときれいにできるのでよい

なんか行列累乗みたいな感じの問題を作りたかった。
サンプルにすべてのクエリーを網羅してなかったので申し訳ない

ここに書いた : 2015 JAG Regional J : Longest Shortest Path - とこはるのまとめ

（ノックアウトな）トーナメント表みたいなのは好きな構造なのでそれを使って何かをしたかったという話。
こういう問題はなかなか説明しづらいので、問題文のwriterには感謝。
最初は区間DPで行けるだけかと思ったけど実験的にやるとMongeが成り立っていそうだったので、Mi_Sawaさんに投げたら証明が返ってきました。

2016年

豪邸と宅配便 , jfen : あまり仕事ができず。

2017年

IOIで出た図書館系の問題が割と好きだったのでそういうのを作りたくなったので作りました。

昔の本家ICPCの問題 BrokenDoor http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp をそのまま一般化したもの。
AOJ-ICPCにある難問を通勤中の電車で考えることを一時期やっていて、
BrokenDoorを考えているときになんとなく行けそうな気がしてきて、頑張って詰めた覚えがあります。

これを本番で通せるチームが複数いるあたり、やはり当時とはレベルが段違いであることを伺わせます。
昔のICPC勢と飲むときに酒のつまみにできる問題です。

問題の美しさは最高レベルだと思っています。
wataさんの資料からも参照されていてとても嬉しいです。

模擬地区に向けて問題が足りないということで必死こいて作りました。結構短期間で作った覚えがあります。

2019年

  • All your base are belongs to us

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2972

JAG内部の問題Wikiに雑すぎる解法を書いたため埋もれていた問題です。
notさんがエレガントな証明を思いつくことで日の目を見ました。

2013アジア地区大会振り返り

おさけーさんによる別視点
http://www.osak.jp/diary/diary_201312.html#20131205

まとめ(1/8 追記)

binding.pryの一員としてICPCアジア地区大会の会津大会(日本大会)およびDanang大会(ベトナム大会)に参加してきた。

会津大会で国内大学としては、東大に次ぐ形となり、これが決め手となって世界大会(エカテリンブルク・ロシア)に行けることになった（まだ非公式だが）。Danang大会でもいい感じの順位まで来たがここでは次点止まりだった。

今回はFCCPC_alphaがかなり強いので半分は負けると考えていたが、その中で勝てたのは正直かなり幸運だったように思う。

チーム戦略としては、二人が実装主体で、一人（ぼく）が後ろでアルゴリズムなどを考えるというもの。
要するにこれの劣化版

劣化版というのは University of Agitsune より遥かに能力が低いということだが、今回はそれなりにうまく行ったように思う。あと、実際には二並列ではなくて、何回かやってみて我々のチームでは「メインコーダー」と「サブコーダー / デバッガー / 読解」みたいな分け方が妥当だなあと思った。書いてみたけど改めて後者が「何でも屋」って感じがする。すごい。

メリットは

  • 後ろの人は両メンバーと話し合いながらすすめることが多いので、時間的にどの問題からやるかとか、コーダー交代のタイミングを（それなりに）正しく制御できる。
  • 実装苦手な人が実装しなくてよい / 逆も。
    • ただし、実装量の見積もりはそれなりに正しく出来る必要があるので、本当の素人に任せるわけにはいかない感じがする

デメリットは

  • 後ろの人は実装する人に正しいアルゴリズムを正確な言葉で伝えなければならない
    • これは出来る人が全部一からやるよりも時間的ロスが大きい
    • また、間違った言葉で伝えてしまって大惨事になるリスクもある(Danang,C問題)

というところだと思う。

===================================================================
以下、大会中の流れ

注：以下は全くまとまってない
・もうだいぶ時間経ったので時系列が嘘っぱちかも。
・読み返していないので文章がおかしいかもしれない

会津大会


・すごいドキドキする
0完
・ドキドキしつつも事前の打ち合わせ通り自分はCを読む。
・ドキドキしているがまあこれは普通に座標圧縮でゴニョゴニョすれば大丈夫だと思う
・あとEを読んでおく
1完(A)
・領域の間に辺があるかどうかの判定がどうにもめんどくさそうだが、特に解決策も思いつかなかったのでそのままosa_kさんに投げる。
・その後、osa_kさんが領域の間を別の色で塗るというナイスな案を考える。すごいいけそう
・Eの概要も伝える。何も考えていなかったが、Dijkstraだと言われる。たしかに。
・Dを考える。何を考えればいいんだ…
・Gについてosa_kさんから3次元のマトリョシカだと言われたが、そういう系見たこと無いし、すぐに取っ掛かりが見つからないので絶対にヤバイ問題だと思う。
・思い違いかもしれないが、少なくとも3段階で最も簡単な難易度というのは大嘘だと感じてAを☓印で消す
2完(B)
・Dの詳細を詰めようとする。心臓バクバクする。なんだこれ。やばい。JOIですらこんなに緊張したか怪しい。
・C、 おさけーさんが失敗してるけど、みけきゃっとさんが行けそうと言っているので行けるかも。とりあえず任せてみる。
・D、 よく考えたら秒針を変数として(0<=x<60)としたら普通に式が立つじゃん。大体式立ちそう。
・Cがヤバイらしい。見てみると、たしかにみけきゃっとさんの方針はやばい。見落としだった。しくった。とりあえずおさけーさんに再び交代。
3完(C)
・D,Eどっちが早いか問われる。Eは20分でできるらしい。すごい。Dは式が完全ではないので、Eを任せる。
・Eをやってもらっている時間でちゃんと確認。これなら大丈夫そう
・みけきゃっとさんも分数を定義して行けそう、と言ってくれる
4完(E)
・みけきゃっとさんにDを任せる。
・そろそろドキドキが収まってくる。
・Hをosa_kさんがいい感じの幾何だと見破ってくれる。
・本質部分の話は昔きゅうりの問題で見たことがあると言ったが、僕自身完全に忘れていた。
・その問題は分割統治法で解いた覚えがあったが、今回はそれよりも制約がきついし、詳細忘れていたし、osa_kさんにメリットを説明することが出来なかったのでそれは実現せず(分割統治を使えば幾何のめんどい式を一切使わずに答えを求めることが出来る)
・osa_kさんが頑張ってHを詰めているうちにIを考える。わからん。
・Gもちょっと考えてみる。やっぱりやばい問題じゃないのという感想を持つ。
・Hの詰めの際に詳細の確認をされる。それっぽい証明を言って完全に方針が定まる。
・Dが少し詰まっているようにも見えたのでチラチラ見る。少し想定と違ったので少し指示を出しつつ、バグを直したら通る。
5完(D)
・Hの実装を開始。
・Iを考える。区間DPっぽいものを考えるがやっぱりわからん。
・みけきゃっとさんと新規問題の開拓をしようとするが、成果はない。
・そろそろ時間も押してくる時間だったので、osa_kさんのコードを見るようになる。
・なんかうまく行ってないっぽいのでみけきゃっとさんに印刷したコード投げると、すぐにヤバイ箇所を見つける。さすがデバッガだ。
・そこから何かあったか忘れたが、もう少し直したら通る。
6完(H)
・次に何を解くか。選択肢はF,G,I.どれもいうほど開拓できてない。実力不足感。
・おさけーさんの魔法の言葉「落ち着いて考えよう」
・ぼくはJを解くことを推奨しようとしていた（が、多分おさけーさんが完全に無理と判断しているので、どっちにしろ退けられていた）
・Gはやばいと主張し続けた。（これが正しかったかはわからん
・Iもきっとやばいと主張した
・その結果Fを考えてみた。
・Fでその前までわかっていたことといえば、「球面をうまいこと分割することだけど、球面とかうまいこと分割できるわけ無いじゃん」ぐらい。
・その辺を説明している辺りで、球面上での距離の大小関係は3次元の直線距離でも同様の大小関係を保つことに気づく。
・勢いのまま話して、それは蟻本にあることを言われ（もちろん僕も気づきつつ）開き、3次元をどうするかを考えて、それ以外の部分をまずはかき上げることにする。
・実装パートはおさけーさん、詳細の詰めはとこはる＆みけきゃっと。
・まずは蟻本のアルゴリズムを思い出す。見たことはあったので、その辺は比較的楽。
・次に次元を上げた時にどうするか。いろいろ出たが、実装量的には、単純に2次元のときに枝刈？のようなことをそのまま流用するのが最善と判断。もしTLEならそのときに考える。
・ちょうどおさけーさんも書き終わったっぽいので、蟻本を見せつつ説明。理由も示しつつ説明したつもりだった（が、言われるがまま、という感じだったらしい。その辺難しい
・実装が終わる。なんかうまく行かない。
・以後はおさけーさんの日記通り。添字ミスが原因。
・最後の最後のSubmit。通った。安堵した。
7完(F)
・F問題のACに至るまでの過程が全員の力を使い切った感じがして非常にドラマチックだったのでかなり印象に残った

Danang 大会

会津とは対照的にわりと落ち着いた気分で大会に臨む。
世界大会ほぼ確実の状態だったからだろう。
0完
・問題文が1部しか配られないので、最初にホッチキスを外して、問題ごとに付箋を貼って最初に読む問題をそれぞれ渡す。
・Jを読む。どうみても行列累乗。でもSumのある形。一応メモに行列とその積を書いて確認。よさそう
1完(A)
・おさけーさんにJを渡す。これこれこうこう、という説明をする。やってもらっているうちに、Dを読む。
・Jがなんかおかしいらしい。色々見て、答えとしている行列の箇所が違うことを確認。サンプルがあったのを確認して提出するがWA.なんでや…
・印刷してもらって確認したりIやってもらったり、Cをちょっと考えたり。
・MOD 10^12じゃねえか！掛け算すると死ぬじゃねえか！！あほか！！
・なのでJを訂正。
・通る。
2完(J)
・Iもすぐ直すだけだったらしい
3完(I)
・Cの解法を伝える。
・O(NlogN)だったら通ると思い、1~Nで篩っぽい操作をする旨を伝えた（が、普通の篩の操作をしてしまっていた。篩なんて表現で伝えるべきではなかった。
・その間にFを考えるなどする。
・Fは0011100みたいなビット列で管理すると頭がおかしくなるので、0がa個あって、1がb個あって、みたいな記法で表現して考えることにする。0,1が逆でも問題変わらないので、(a,b,...)の列だけ考えればよいので、こっちのほうが楽である。
・Cがなんか合わないらしい。解釈を議論する。やはりよくわからん。色々試すけどダメっぽい。
・ので、Fを渡す。結局、縮約処理をシミュレートする感じにした。証明はできてない
・Fを実装してもらっている間にGの問題概要を聞いたりする。
・みけ「いくつかグラフが与えられて、それが同じグラフか判定する問題」とこ「へー、それって木だったりするん？」みけ「木だね」とこ「まじでｗｗｗｗｗｗ」
・つまるところ聞いたことある問題だったので、これは解けると確信するが、それは時間がある話であって、果たしてこれはうまく行くのか…
・Fのサンプルがそれっぽいので投げる。AC
4完(F)
・引き続き闇のCを考えてもらう。なんかみけきゃっとさんが気づいたらしいのでそれを元に検証が行われている。
・Bの問題も聞いておく。全域木の数え上げらしい。
・知ってた。正確に言えば、解けることを知ってた。詳細はあんま覚えてなかった。やばい。これは正念場だ…。
・思い出す。覚えている情報は次の通り。
+ 行列式が答え。
+ 隣接行列を使う。
+ Traceはなんか別に割り振る。
+ なんかマイナスを掛けるとか出てきたような気がする。
・いつか忘れたけど、いい感じにCもなんとか解けたらしい。
5完(C)
・それで、さっきの箇条書きを組み合わせてそれっぽい行列を作る。
具体的には、普通の隣接行列に対角部分に次数に-1かけたものを入れたもの。まあテストして正しいっぽい値でたし大丈夫でしょということでGOサインを出す。（計算ミスで正しい値が出ていた。これでGOサインを出したのは色々やばかった。
・投げている間にDを考える。なんか二部グラフっぽい。最小費用流で答えは出そうな感じはする。正当性はみけきゃっとさんに丸投げする。
・Bの行列式が0になるらしい。ほんとだ。たしかに計算しても0になる。
・もう一回さっきの行列式を思い出す。
・そういえば、さっきの行列の行列式を出しても常に0だったような気がしてきた。
・それだったら、確か一行一列抜かすんじゃないかなあ
・ということで、最後の行を抜かして行列式を求めてもらう。
・サンプルでそれっぽい値が出るが、+になったり-になったりするらしい。
・みけきゃっとさんから修正案も出るが、僕が「これは偶奇で場合分けだろう」と言う。
・結局偶奇がそれっぽい値が出るように見える。出してみる。AC
(結局、思い出した行列式はTrace部分は正で、それ以外の隣接行列の部分は-1を記入する、ということだったし、二重に間違って思い出していた)
6完(B)
・あと解ける問題は時間的にDのみ。
・最小費用流を実装してもらい、そして費用について逐一説明する。
・なんとか書き終わったが、時間がない。サンプルにも食わせず提出。WA。終戦。