愛媛大会ＷＥＢ予選

http://ccserv.adm.ehime-u.ac.jp/ICPC/jp/
いつの間にか、予選が開催されていたんですね。コーチとして名前を貸していたチームは、残念ながら負けてしまったそうです。残念。Ｍ１が一人いたので、来年があるとは言えませんでした。
で、いまさっき問題を眺めていました。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/problems.html

問題Ａから問題Ｆまでの、日本語版のリストです。
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/A.jp/A.html
問題Ａ「花札シャッフル」は、カードシャッフルの問題ですね。これは、反転・反転・大反転（文字列のカット＆ペーストと同じアルゴリズムで、数珠のプログラミングという本に載ってる）を行えば、配列の要素を反転させる関数１つで実現できるでしょう。サービス問題ってやつですね。
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/B.jp/B.html
問題Ｂ「赤と黒」は、どれくらい広く領域を歩けるかの問題です。スタート地点を中心に、幅優先か深さ優先探索をしかけることで、あっという間に実現できるでしょう。（再帰のほうがかんたかな）
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/C.jp/C.html
問題Ｃ「単位分数の分割」は、ある分数が何通りの単位分数（分子が１の分数）の和で表現できるかという問題です。なんか、インド人が得意そう。正直、いまぱっと考えたけど、スマートなアルゴリズムが思いつきません。おそらく、単位分数の和を求める分割ルールが存在して、それを適用しながら単位分数の和の集合を現す木構造の探索をすれば良いのではないかと思われます。まあ、分割ルールは単純に分数を再帰的にどんどんと分けていくってやつでいいんでないかな。で、分母の積が与えられた数を超えたらハイ終了、みたいな。
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/D.jp/D.html
問題Ｄ「円と点」は、平面上に散らばってる点に、半径１のわっかを投げたときに一番多くの点を囲むには、どこにわっかを投げればよいかという問題です。精度は0.0001。適当な２点を通る円を作って（半径固定のため、円は２個に限定される）、それが囲むことができる点の数を求める。で、これを全部の可能な２点について調べつくせば、おのずとどの円が最強かを知ることができるのではないでしょうか。
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/E.jp/E.html
問題Ｅ「水槽」は、区切りで分割された水槽の中に、各区切りごとに蛇口から水を適当に流したときの水の流れをシミュレートしろという問題。問題が長すぎてあまり詳しく読んでないんで、題意を外してたらすまん。で、シミュレーションしろとのことなので、私だったらイベントドリブンみたいな感じで解きますか。各区切りの容量と、入り込む水量はわかってるから、そこから何分後に溢れるってのも計算できる。で、その時間をプライオリティキューに乗せて、ひたすら時間順にイベントをシミュレーションしていく。で、イベント発生時に各水槽の高さを計算できるようにしておき、終了時刻を最初っからキューに載せておけば自動的に求まる。そんなところでどうでしょう。でも、解析的に解けるべ、これ。
http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/F.jp/F.html
問題Ｆ「交差点の名前」は、制約問題を解く問題。詳しくは自分で問題を読んで。データセットから、道をノードとするような半順序関係を生成して、問題として与えられた二つのノード間に順序が存在するかを調べればいいかと。あとは、道の方角を東西で塗り分けるだけっしょ。面倒ならば、線形計画問題に持ち込んで、解が存在するかしないかに問題を落としこんで、アルゴリズム辞典のサンプルソースを写すだけで解ける。（普通の再帰で十分対応できるから、オーバースペック気味で微妙。）
とりあえず、後で実際にプログラムを書いてみるか。目標は、ＡＢＣＤが一問２０分、ＥＦが一問５０分の計３時間。無理そう。