https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf を読んで実装した。 まだverifyしていないので正しいか知らない。 [追記4/28] http://uva.onlinejudge.org/index.php…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1142&lang=jp D言語らしいコードが書けた mutableじゃないとreverseできない（当たり前）とかimmutableだと~が使えない（なんでだろう？）で引っかかった 例えば，下の解答の一部で char[] v = st…

接尾辞配列というのを使うと文字列検索でいろいろできるらしいので書いてみた 何も見ずに書くと蟻本のコードと比較したとき自分のコードがいかにぐちゃぐちゃか思い知らされる． #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MA</vector></algorithm></cstring></cstdio>…

問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538解法 動的計画法を使う。 Oの数を数えることを意識して、 a[i] = if(s[i-1]=='I' && s[i]=='O' && s[i+1] == 'I') a[i-2] + 1 else 0 という漸化式を作り、aの中に何個N以上の数があるか…

PCK参加しました。 bitDP気づいたけど実装力なさすぎでバグりまくったのが悔しい 本選参加できるかどうか微妙(地域枠) 今はコード手元にないから今度のせる(追記) コードはどっかいったPOJ 1936部分文字列かどうか判定する問題 再帰書くだけでよい solve(p, …

PKUが死んでた http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0139解法 地道にチェックするコードを書く もっとスマートにできないかなぁ。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[250]; bool cA(){ int l = 0, i; for(i </algorithm></cstring></cstdio>…

問題 辞書データとクエリが与えられるので、翻訳した結果を表示せよ。 辞書に載っていない場合"eh"と表示せよ 解法 辞書データはmapで管理した。 入力の処理に少し工夫が必要。 #include <cstdio> #include <cstring> #include <string> #include <map> #include <algorithm> using namespace std; typ</algorithm></map></string></cstring></cstdio>…

問題 解法 駅は番号で管理するとやりやすい。駅名と駅番号を対応付けるためにmapをつかう。 あとはダイクストラかワーシャルフロイドすればいい。 #include <iostream> #include <cstdio> #include <vector> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; const int I</algorithm></queue></map></string></vector></cstdio></iostream>…

問題 解法 構文解析するだけ。 しなくてもできそう。 解析したあとは、再帰で一番上のパネルを求めることができる #include <cstdio> #include <string> #include <vector> #include <algorithm> using namespace std; //タグ class T{ public: string name; int x1, y1, x2, y2; vector<T> ko; //</t></algorithm></vector></string></cstdio>…

問題 getlineの使い方がわからないのでコードが変になった↓恐ろしく非効率なコード #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char text[3][5] = { "this", "the", "that", }; char S[100]; char A[100]; int len; void solve(){ char </algorithm></cstring></cstdio></iostream>…

問題 解法 対話型プログラムを書く変わった問題。おもしろい。AIの単語をsetを使って記録しておく。 自分の言う言葉の生成方法はいろいろあるが、bitで管理することにした。 具体的には以下変数iを用意して0で初期化する。 (1) i++; (2) 単語生成 1文字め…AI…

問題 解法 STLゲー。 map を使って単語と出現ページの情報を管理する。 #include <cstdio> #include <iostream> #include <map> #include <queue> #include <string> #include <vector> #include <algorithm> using namespace std; typedef priority_queue<int, vector<int>, greater<int> > PAGE; typedef map<string, PAGE> INDEX; int main(){ char b…</string,></int></int,></algorithm></vector></string></queue></map></iostream></cstdio>

問題 解法 STLゲー。mapをアイテムの値段用とレシピ用に2つ使う。 再帰で最小の金額を求めていく。 #include <cstdio> #include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; typedef map<string, int> ITEM; typedef map<string, vector<string> > RECIPE; ITEM item; RECIPE recipe; int solve</string,></string,></algorithm></vector></map></iostream></cstdio>…

あしたじゅけーーん 問題 解法 筆算するみたいにやっていけばいい。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_K = 80; char num1[MAX_K + 1]; char num2[MAX_K + 1]; char numS[MAX_K + 1]; int k1, k2; bool plus(){ int t = 0, </algorithm></cstring></cstdio>…

問題 解法 やるだけ。 #include <cstdio> using namespace std; const int MAX_LEN = 1024; char str[MAX_LEN]; const char a[8] = "Hoshino"; int main(){ char c; int p, n; scanf("%d\n", &n); p = 0; while(EOF != scanf("%c", &c)){ if(c == '\n'){ for(int i =</cstdio>…