UVa 11475 Extend to Palindrome
長さ100000以下の文字列sが与えられる。sの後ろにできるだけ少ない文字列を連結して回文にし、出力せよ。
少し考えると、sをreverseした文字列をs_revとして
s.substr(s.size() - N) == s_rev.substr(0, N)
となるような最大のNを求めれば良い事が分かる（できるだけオーバーラップさせたいので）。
したがって、s_revをneedle、sをheystackとしてKMPを走らせて、終了時にPMAのどの状態にいるか調べれば良い。
#include <iostream> using namespace std; class KMP { public: KMP(const string& pattern) : failure_(new int[pattern.size() + 1]), pattern_(pattern) { // build failure function failure_[0] = failure_[1] = 0; for (int i = 2; i <= pattern_.size(); ++i) { for (int j = failure_[i - 1]; ; j = failure_[j]) { if (pattern_[j] == pattern_[i - 1]) { failure_[i] = j + 1; break; } if (j == 0) { failure_[i] = 0; break; } } } } ~KMP() { delete[] failure_; } int Match(const string& text) { for (int i = 0, j = 0; ;) { if (j == text.size()) return i; if (text[j] == pattern_[i]) { ++i, ++j; } else if (i > 0) { i = failure_[i]; } else { ++j; } } } private: int *failure_; string pattern_; }; int main() { string s; while (cin >> s) { string s_rev(s.rbegin(), s.rend()); KMP kmp(s_rev); int max_match = kmp.Match(s); cout << (s + s_rev.substr(max_match)) << endl; } }
明治ミルクチョコレートパズル（ブラック）：回答編
いきなり回答編ですが。
最近研究室の後ろに座ってる人がこれ（http://www.amazon.co.jp/%E3%83%8F%E3%83%8A%E3%83%A4%E3%83%9E-%E6%98%8E%E6%B2%BB%E3%83%9F%E3%83%AB%E3%82%AF%E3%83%81%E3%83%A7%E3%82%B3%E3%83%91%E3%82%BA%E3%83%AB/dp/B000BVN0AA）を持っていて、遊んでいたら元に戻せなくなったのでプログラムを書きました。最初std::vector
#include <iostream> #include <set> using namespace std; typedef unsigned long long ull; char color[10][6]; ull choco[12][8 * 10 * 6]; int choco_size[12]; ull pieces[12] = { 271,527,8642,12676,8327,16833,199,327,28737,31,899,16834 }; inline ull Pos(int i, int j) { return 1LL << (i * 6 + j); } inline ull At(ull n, int i, int j) { return n & Pos(i, j); } ull Rotate90(ull n, int maxr, int maxc) { ull ret = 0; for (int i = 0; i <= maxr; ++i) { for (int j = 0; j <= maxc; ++j) { if (At(n, i, j)) { ret |= Pos(j, maxr - i); } } } return ret; } ull Reverse(ull n, int maxr, int maxc) { ull ret = 0; for (int i = 0; i <= maxr; ++i) { for (int j = 0; j <= maxc; ++j) { if (At(n, i, j)) { ret |= Pos(i, maxc - j); } } } return ret; } int dr[] = {1, 0, -1, 0}; int dc[] = {0, 1, 0, -1}; int Count(ull &b, int r, int c) { b |= Pos(r, c); int ret = 1; for (int i = 0; i < 4; ++i) { int nr = r + dr[i], nc = c + dc[i]; if (0 <= nr && nr < 10 && 0 <= nc && nc < 6 && !At(b, nr, nc)) { ret += Count(b, nr, nc); } } return ret; } void Dfs(int depth, ull board) { static int num = 0; if (depth == 12) { printf("Answer %d:\n", ++num); for (int j = 0; j < 6; ++j) { for (int i = 0; i < 10; ++i) { cout << color[i][j]; } cout << endl; } cout << endl; } else { for (int i = 0; i < choco_size[depth]; ++i) { ull shifted = choco[depth][i]; if (!(board & shifted)) { ull board_shifted = board | shifted; for (int ii = 0; ii < 10; ++ii) { for (int jj = 0; jj < 6; ++jj) { if (At(shifted, ii, jj)) { for (int k = 0; k < 4; ++k) { int iii = ii + dr[k]; int jjj = jj + dc[k]; if (0 <= iii && iii < 10 && 0 <= jjj && jjj < 6 && !At(board_shifted, iii, jjj) && Count(board_shifted, iii, jjj) % 5) { goto NEXT; } } color[ii][jj] = 'A' + depth; } } } Dfs(depth + 1, board | shifted); } NEXT:; } } } int main() { for (int k = 0; k < 12; ++k) { ull piece = pieces[k]; int maxr; int maxc; set<ull> chocok; for (int r = 0; r < 2; ++r) { for (int d = 0; d < 4; ++d) { maxr = 0; maxc = 0; for (int i = 0; i < 10; ++i) { for (int j = 0; j < 6; ++j) { if (At(piece, i, j)) { maxr = max(maxr, i); maxc = max(maxc, j); } } } for (int i = 0; i + maxr < 10; ++i) { for (int j = 0; j + maxc < 6; ++j) { chocok.insert(piece << (i * 6 + j)); } } piece = Rotate90(piece, maxr, maxc); swap(maxr, maxc); } piece = Reverse(piece, maxr, maxc); } for (set<ull>::iterator it = chocok.begin(); it != chocok.end(); ++it) { choco[k][choco_size[k]++] = *it; } } Dfs(0, 0); }
一つの解はこのように表示されます。
Answer 1: ABBHHCIIIJ AABHCCCDIJ AKBHHCDDIJ AKBFFDDLEJ KKGGFLLLEJ KGGGFFLEEE
std::cin::get() にはまる
とても簡単に書くと、次のプログラムを実行してCtrl-Dを入力した際に
-1
とだけ出力されて欲しかったのです。
#include <iostream> int main() { while (1) { int c = std::cin.get(); std::cout << c << std::endl; } }
ところが実際にはこうなります。
-1 -1 -1 ...(以下続く)...
どうやらEOFだけは特別扱いされて、一度到達するとstd::cin.get()はEOFを返し続けるようです。というのはまぁ、EOFが入力されたら以降の入力は無いと考えるのが普通なので許せます。
ただEOFも単なる1byteの値なわけで、読み飛ばせそうな気がします。実際読み飛ばしてるっぽいプログラムもあるし。
なのでreferenceを見てそれらしいメソッドを探してみます。
http://www.cppreference.com/wiki/io/start
どうやらstd::cin.clear()というものがあるようです。EOFフラグをリセットできると書いてあります。使ってみます。
#include <iostream> int main() { while (1) { int c = std::cin.get(); std::cout << c << std::endl; if (std::cin.eof()) { std::cin.clear(); } } }
実行してみます。
-1 -1 -1 ...(以下続く)...
ダメです。適当に「eof clear」等でググると、stdinを生で触る場合は次のようにして解決できる事が分かりました。
#include <cstdio> int main() { while (1) { int c = getc(stdin); printf("%d\n", c); if (c == EOF) { clearerr(stdin); } } }
これで、Ctrl-Dを入力するごとに「-1」と出力されるようになりました。
やりたいことが出来る事は分かったので、「cin clearerr clear」等で適当にググります。
するとこんなページを見つけました。1999の記事です。
http://www.delorie.com/djgpp/bugs/show.cgi?000277
僕と同じ悩みを抱えているようです。素晴らしい事に解決法も書かれていて、std::cin.clear();の後にstd::cin.seekg(0, std::ios::end);と書けば良いようです。
試してみます。
#include <iostream> int main() { while (1) { int c = std::cin.get(); std::cout << c << std::endl; if (std::cin.eof()) { std::cin.clear(); std::cin.seekg(0, std::ios::end); } } }
今度は期待通りの動作をするようになりました。
ところでlink先の記事ではc++ libraryのバグじゃない？と言われているのですが、10年後の今になって再現性があるので、きっと仕様でしょう。が、なぜstd::cin.get()は素直にEOFを読み飛ばしてくれないのか分かりません。getc(stdin)なら読み飛ばしてくれるのに。
srm437
久しぶりのsrm、のはずだけど、今年からペースが落ちたので問題セット的には間は空いてない。
しかしまぁ緊張した。
div1:250 TheSwap
1 <= n <= 1000000, 1 <= k <= 10と妙に数字が小さいので一見して全探索の予感。
スワップを全通り試すと6C2 ^ 10になって当然終わらないけど、6桁の数字の並び替えはせいぜい6! = 720通りしかないので、(現在の数字の並び, 残りのswap回数)でメモってやれば6! * 10で楽勝じゃん。おおぅ。というわけで普通のメモ化再帰を書く。整数値のままswapするのが面倒で文字列で処理したので速度が不安だったけれど(n = 123456, k = 10)が一瞬で終わったのでそのまま提出。
ところがswapの処理でバグを発見したので久しぶりに再提出。ふー。。。
。。。と、落ち着きたい所だったのだけれど、再提出後にテストしてみるとなぜか修正前の結果が出てしまう。直ってない。実は今回新しい環境で参加していて、プラグインの設定を変更できておらずファイルが上書きされてしまっていたっぽい。うぇぇぇ。
というわけで、二度目の再提出でとんでもなく低い点数になってしまった。
ともあれ通って良かったです。
map<pair<int, int>, int> memo; int rec(int n, int k) { pair<int, int> p(n, k); if (memo.count(p)) return memo[p]; if (k == 0) return n; stringstream ss; ss << n; string s = ss.str(); int ret = -1; for (int i = 0; i < s.size(); ++i) { for (int j = i + 1; j < s.size(); ++j) { if (i > 0 || s[j] != '0') { swap(s[i], s[j]); ret = max(ret, rec(atoi(s.c_str()), k - 1)); swap(s[i], s[j]); } } } return memo[p] = ret; } class TheSwap { public: int findMax(int n, int k) { memo.clear(); return rec(n, k); }
passed system test 87.47
div1:1000 問題名すら覚えていない
編集距離っぽい文面だけ読んだ。
opened
というわけで、間を空けるとやっぱり良くないなというありがちな感想です。ただ今回の問題セットはなかなかgoodだったらしく、全failな赤・黄コーダーが頻発してたので（どうしてかは知らない、greedyに引っかかったんでしょうか）レーティングは予想より上昇。なぜか黄色が見えてきた！
1383 -> 1443
srm433 復習
参加記の方書くの忘れてた。
本番は250で8! * 160 * 160を書いてしまって撃墜され、500でad-hocをやって撃墜されてしまって0点。うぐぐ。難し目のセットだったようであまり下がらなかった。
div1:250 MagicWords
T(i) = T(0)となるiがK個存在する<=>T(0)はK個の等しい部分文字列に分割できる、という事を利用すると8! * 160になって通る。
class MagicWords { public: int count(vector <string> S, int K) { int ret = 0; vector<int> P(S.size()); for (int i = 0; i < S.size(); ++i) P[i] = i; do { string con; for (int i = 0; i < P.size(); ++i) con += S[P[i]]; int cnt = 0; for (int i = 1; i <= con.size(); ++i) { if (con.size() % i != 0) continue; bool ok = true; for (int j = 1; j < (con.size() / i); ++j) { for (int k = 0; k < i; ++k) { if (con[k] != con[j * i + k]) ok = false; } } if (ok) { cnt = con.size() / i; break; } } if (cnt == K) ++ret; } while (next_permutation(P.begin(), P.end())); return ret; }
div1:500 SettingTents
最初に菱形の辺としてありうる直線を列挙して、長さ（だと整数にならないのでその二乗）で分類する。
等しい長さの直線を二つ選ぶと菱形が出来るので、bounding boxを計算して上下左右に動かす。
typedef complex<int> P; class SettingTents { public: int countSites(int N, int M) { map<int, vector<P> > m; for (int i = 0; i <= N; ++i) { for (int j = -M; j <= M; ++j) { if (i == 0 && j <= 0) continue; m[i * i + j * j].push_back(P(i, j)); } } int ret = 0; for (int d = 1; d <= N * N + M * M; ++d) { vector<P> &v = m[d]; for (int i = 0; i < v.size(); ++i) { for (int j = i + 1; j < v.size(); ++j) { P p[3] = {v[i], v[j], v[i] + v[j]}; int minx = 0, maxx = 0, miny = 0, maxy = 0; for (int k = 0; k < 3; ++k) { minx <?= real(p[k]); maxx >?= real(p[k]); miny <?= imag(p[k]); maxy >?= imag(p[k]); } int x = maxx - minx, y = maxy - miny; if (x <= N && y <= M) ret += (N - x + 1) * (M - y + 1); } } } return ret; }
div1:1000 BarbarianInvasion
マップの外側と首都を分断するようなコスト最小のラインを求めれば良くて（正確にはラインじゃなくて-で途切れてる事もあるけども）、結局それはグラフの最小カット（＝最大流）になっているので、適切なグラフを作ってからフローを流すだけで求まってしまう、という。
単純にコスト最小なラインではなく出来るだけ潰すマス目の小さいラインを求めよ、という一見やっかいな条件があるが、適当にでかい数を足して最後に割ると上手く行く。
typedef long long ll; const ll MOD = 10000000000LL; template<typename T> class Graph { private: struct Edge { int to, back; T flow, cap; Edge(int to, T cap, int back) : to(to), back(back), flow(0), cap(cap) {} T residue() { return cap - flow; } }; int n; vector<vector<Edge> > g; public: Graph(int n) : n(n), g(n) {} void insert(int i, int j, T c) { g[i].push_back(Edge(j, c, g[j].size())); g[j].push_back(Edge(i, 0, g[i].size() - 1)); } T dinic(int s, int t) { T flow = 0; int P[n], Q[n]; for (;;) { memset(P, -1, sizeof(P)); int QF = 0, QB = 0; P[Q[QB++] = s] = -2; while (QB > QF && P[t] == -1) for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i) if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0) P[Q[QB++] = v] = g[u][i].back; if (P[t] == -1) return flow; for (int i = 0, z; i < g[t].size(); ++i) if (g[z = g[t][i].to][g[t][i].back].residue() > 0 && P[z] != -1) { T inc = g[z][g[t][i].back].residue(); for (int e = z; P[e] >= 0; e = g[e][P[e]].to) inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue()); if (!inc) continue; g[t][i].flow -= inc, g[z][g[t][i].back].flow += inc; for (int e = z; P[e] >= 0; e = g[e][P[e]].to) g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc; flow += inc; } } } }; int dr[4] = {0, 1, 0, -1}; int dc[4] = {1, 0, -1, 0}; class BarbarianInvasion { public: int minimalDetachment(vector <string> countryMap, vector <int> detachmentSize) { int N = countryMap.size(), M = countryMap[0].size(); #define HI(i, j) ((i) * M + (j)) #define LO(i, j) (HI(N, 0) + (i) * M + (j)) #define D (LO(N, 0)) int S; Graph<ll> g(D + 1); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { for (int k = 0; k < 4; ++k) { int ni = i + dr[k], nj = j + dc[k]; if (0 <= ni && ni < N && 0 <= nj && nj < M) { g.insert(HI(i, j), LO(ni, nj), MOD * 2); } } if (i == 0 || i == N - 1 || j == 0 || j == M - 1) { g.insert(HI(i, j), D, MOD * 2); } if (countryMap[i][j] == '*') { S = HI(i, j); } else if (countryMap[i][j] != '-') { g.insert(LO(i, j), HI(i, j), detachmentSize[countryMap[i][j] - 'A'] + MOD); } } } return g.dinic(S, D) % MOD; }
srm431
srm430からそれほど間を空けずにsrm431。前回は登録出来なかったので助かった。
ただ来年は月二回ペースとの噂があるのでなんとも残念。
div1:250
直行座標系の第一象限と第四象限に、y軸と並行な長さ1以上の線分がいくつか与えられる。偏角-PI/2 〜 PI/2の範囲のランダムな方向に向けて光線を発射する時に、貫通可能な線分の数の期待値を求めよ。
ある直線を貫通する確率は貫通可能な偏角の範囲をPIで割れば求まる。従って
で期待値は求まる。のだけど、もっと賢い方法があって、それぞれの線分について貫通可能な偏角の範囲を足し合わせてやって最後にPIで割れば同値な計算になってとても簡単。
半分位の人はそっちでやってたような。自分は前者でやったので遅くなってしまった。
failed system testな人はなんと5人しか居なかった。なんつーrobustな問題ｗ
passed system test: 193.52
div1:500
数字列を長さ(N)、分割数(A)、最も右にある数(RIGHTMOST)、最も右の部分列の公差(DIFF)の四つ組S(N, A, RIGHTMOST, DIFF)で表して四次元DPで行けそうだな〜（1000 * 1000 * 10 * 10 = 一億の空間が必要になって不安だけど）と思ったので書いてみたけど基底条件を正しく列挙できなかったので正答まで持っていけなかった。難しかったらしくて皆提出していない。
opened
div1:1000
challengeの為に必要な情報しか読まず。ところが時間内にcompileしなかったためtest caseを入力する事が出来ずchallenge phaseで先を越されてしまった。次回からは最低compileだけはするようにしよう。
opened
ratingは1397 -> 1415と微増。微すぎる！
OS Xでアセンブリからシステムコール呼び出し
とりあえずのhello world。
.file "hello.S" .data msg: .ascii "hello world\n" len = . - msg .text .globl start start: # call write(1, $msg, $len) pushl $len pushl $msg pushl $1 lea -4(%esp), %ecx # stack pointer - 4 movl $call_exit, %edx # return address movl $4,%eax # system call number of 'write' sysenter call_exit: # call exit(0) pushl $0 lea -4(%esp), %ecx movl $0, %edx # meaningless movl $1, %eax # system call number of 'exit' sysenter
実行可能バイナリを作るには
as -o hello.o hello.S && ld -o hello hello.o
でOK。
だったのが、xnuでは
となっていて、また一つ違いの分かる人になれて良かったです。
