a,b,cから構成される文字列に対応したグラフを考える
- 文字列のi番目の文字はi番目のノードに対応している
- 文字列のi番目の文字とj番目の文字が同じであればノードi, jは必ず隣接する
- i番目の文字とj番目の文字がアルファベット順で隣同士であれば隣接する
  - すなわち，aとb，bとcは隣接する
  - aとcは隣接しない
グラフが与えられるので以上の条件を満たす文字列があるかを考える
無い場合は“No”，ある場合は“Yes”と候補として考えられる文字列を一つ出力する

解法

全てのノードからbの候補となるもの見つける
- bは全てのノードと隣接している
- すなわちbから出る辺はn-1本
bの候補とそのエッジを取り除いたグラフから強連結成分を見つける
- 色々あるけど張ってあったのでUnionFindを使った
検出した強連結成分はaとcの候補
- 3つ以上強連結成分があればNoを出力
検出した強連結成分は完全グラフでなければならない
- bの候補に向かって張ってる辺を除いた辺の数が強連結成分のノード数-1となる
- なっていなければNoを出力
ここまででNoが出力されていなければYes
- b候補のノードをb，強連結成分に属するノードをaかc (異なる強連結成分同士で異なればどちらでもよい) として出力

2016-02-02

Suffix Array

アルゴリズム競技プログラミング

新しいアルゴリズムを学んだので自分用の備忘録．

Suffix Arrayとは

日本語では接尾辞配列
ある文字列の全ての接尾辞を辞書順に並べたもの
例えば “coder” という文字列について考える
接尾辞は “coder”, “oder”, “der” “er”, “r”, “”
接尾辞配列は以下の通り

開始位置	接尾辞
5
0	coder
2	der
3	er
1	oder
4	r

Suffix Arrayを使うと，長さnの文字列の中から長さmの文字列を[latex]\mathcal{O}(m\log{n})[/latex]で探索したりできる
競技プログラミングでもよく使うらしい (僕はまだ2問しか見たことない)

Suffix Arrayの構築

愚直に構築することを考える
- ソートのための比較の回数は[latex]\mathcal{O}(n\log{n})[/latex]かかる
- 比較は[latex]\mathcal{O}(n)[/latex]かかる
- よって構築のオーダーは[latex]\mathcal{O}(n^2 \log{n})[/latex]
- 競技プログラミング的には[latex]n=10000[/latex]くらいからアウトだと思われる
その他の方法
- SA-IS法 : [latex]\mathcal{O}(n)[/latex]
  - はやい，競技プログラミング的にオーバーキル気味
  - コード長い
  - 理解には論文を読む必要があるらしい…
- Manber&Myers : [latex]\mathcal{O}(n \log^2 n)[/latex]
  - 競技プログラミング的に丁度いいはやさ
  - コード短い
  - 蟻本を読めば理解可能
今回はManber&Myersについて学ぶことにする

Manber&Myers

接尾辞配列の最初の1文字でソート→2文字でソート→4文字でソート…
すでにソート済みの情報を使うので1回のソートは[latex]\mathcal{O}(n\log{n})[/latex]
よって[latex]\mathcal{O}(n \log^2 n)[/latex]
蟻本の説明とコードを見ても理解に時間かかったのでコードにコメントをつけた

2016-01-15

CodeforcesでACした問題を確認できるサイトを作った

競技プログラミング

CodeforcesでACした問題を確認できるサイトを作った．

Codeforces AC List

使い方

フォームにCodeforcesのIDを入れてEnterを押すだけ．
ACした問題は緑色になる．

作った経緯

競技プログラミングの能力を効率的にあげるには，自分に適したレベルの問題を解くことが重要だと考えている．
自分にとっては，Div. 2 C 〜 D辺りが (問題が読めれば) 解けるか解けないかのボーダーラインなので，それを簡単に確認したい．
また，新しい問題の方がネット上での解説が充実しているので，新しい問題から順番に解いていきたい．
そこでコンテスト名 (Div. 1かDiv. 2かそれ以外かを知りたいため) と，そのコンテストの自分の解答状況が，最新のものから順番に確認できる仕組みが必要となった．

実装

CodeforcesはAPIを提供している．
http://codeforces.com/api/contest.list?gym=falseにアクセスすれば，コンテストのリストがJSON形式で得られる．
http://codeforces.com/api/user.status?handle=user_idにアクセスすれば，user_idの提出状況がJSONで形式得られる．
これをPHPから叩いて適当に実装した．