ぶっちゃけAしか合ってないので、解き方についてはなんも言えない。
結果は15点/penalty 36:23で162位。なんとか目標のTシャツには届いてた。
参戦しながら考えてたことを参戦記としてだらだら書いてみる。
B. バクテリアの増殖
- 開始。5問もあることにびびる。点数配分をみて、なんとなくBかCを早めにとけばTシャツいけんじゃないかと根拠の薄い仮説を立てる。
- Bを読む。ふむふむ。バクテリア増えすぎやろ。宇宙がやばい
- 多分、周期がありそう。でも周期発見するまでに溢れまくりそうだ。(ab+c)^(ab+c)を展開してmod bに関係ないとこ外さないといかんかな？
- ああ、数式の展開とか全然できない自分の頭がうらめしい。後回し。ていうか多分できない。
- 次はCにトライ！するつもりだったけど、なんとなくしょんぼり状態になったので勢い付けたい。Aいこう。(終わってみれば、ここでC行ってたらTシャツもらえないところだった。)
A. アンテナ修復
- ああ、これは直感的には、長い棒から順に、右に置いて、左において、って感じで長い棒を片方に寄せれば面積最大になりそう。
- 証明…はいっか。他のやりかた思いつかないし、Aだし引っ掛けもなさそう。それで解いちゃえ
[cpp]
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const double PI = acos(-1.0);
double solve(vector<int>& E) {
sort(E.begin(), E.end());
// 短い方からE0, E1, E2…とすると、円周上で… E4 E2 E0 E1 E3 ..
// みたいに並ぶよう並び替える
vector<int> ordered;
for (int i = 0; i < E.size(); i++)
if (i % 2 == 0) ordered.push_back(E[i]);
for (int i = E.size()-1; i >= 0; i–)
if (i % 2 != 0) ordered.push_back(E[i]);
double answer = 0;
for (int i = 0; i < ordered.size(); i++) {
double e1 = ordered[i];
double e2 = i != ordered.size()-1 ? ordered[i+1] : ordered[0];
answer += e1 * e2 * sin(2 * PI / ordered.size()) / 2;
}
return answer;
}
int main() {
int T; cin >> T;
for (int i = 1; i <= T; i++) {
int K; cin >> K;
vector<int> E(K);
for (int j = 0; j < K; j++) cin >> E[j];
double answer = solve(E);
cout.precision(10);
cout << "Case #" << i << ": " << answer << endl;
}
}
[/cpp]
C. ワイルドカード
(※ 以下は最初から問題取り違えたまま右往左往した記録でありなんの参考にもなりません)
- 気を取り直してCをオープン。なんか昨日チャレンジブックで読んだしゃくとり法が使えそうな気がする！
- しゃくとり法で、Bには存在しなくてかつできるだけ短いAの部分文字列を見つける。なんとか実装。sample通ったのでsmall提出。不正解。
- A:dz, B:ddzzのパターンうまくいってない。解が見つかってない様子。dzはBの部分文字列だけど、*がないdzはBから識別可能なのか。最初と最後の文字は区別する必要あるのね。
- AとBの文字列それぞれの頭と終わりに文字をくっつけるアプローチ。A’:SdzE, B’:SddzzEに変換して部分文字列を見つける処理にする。さっきのパターンは通ったけど不正解
- A:fmmfmmfmm, B:fmmfmmのパターンでうまくいってない。正解は*fmm*だけど、fmmがBの部分文字列になってるので見つかってない。頭と終わりに文字くっつけるのじゃだめか。じゃあ頭と終わりを大文字にする A’:FmmfmmfmM, B’:FmmfmMとやる。これでこのパターンは正しくなったけどやっぱり不正解。
- A:ororor, B:or のパターンでうまくいってない。正解は*orだけどor*になってる。*o*がAを識別できるために、しゃくとり的にoが削られて最後のorが繋がってくれてない。あれ？しゃくとり法したのが間違い？
- 〜Cで2時間経過〜 あと30分だ！シャツのためには、どれかSmall総当たりで解けそうな問題さがして稼いどいたほうがいいかな？ -> あれ、A-large合ってれば大丈夫そう。このままCがんばろう
- 下記の解法のまま時間切れ。不正解。
[cpp]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string solve(string A, string B) {
// A/B:twitter -> A’/B’: TwitteR
string A_dash = A;
A_dash[0] = toupper(A_dash[0]);
A_dash[A_dash.size()-1] = toupper(A_dash[A_dash.size()-1]);
string B_dash = B;
B_dash[0] = toupper(B_dash[0]);
B_dash[B_dash.size()-1] = toupper(B_dash[B_dash.size()-1]);
// しゃくとり法でA’の部分文字列を取り出して、B’の部分文字列になっていないものを探す
int head = 0;
int tail = 0;
int curAstahNam = 0;
string curPattern = A_dash;
while(tail < A_dash.size()) {
string subsec(A_dash, head, tail-head+1); // subsec: subsequence of A
if (B_dash.find(subsec) == string::npos) {
// pattern: *aaa* みたいな最終的な識別パターン。
string pattern = (head == 0 ? "" : "*") + subsec + (tail == A.size()-1 ? "" : "*");
for (int i = 0; i < pattern.size(); i++) pattern[i] = tolower(pattern[i]);
int astahNum = (head == 0 ? 0 : 1) + (tail == A.size()-1 ? 0 : 1);
string prevResult = curPattern;
// patternを、問題の優先順位に従って更新
if (pattern.size() < curPattern.size() ||
(pattern.size() == curPattern.size() && astahNum < curAstahNam) ||
(pattern.size() == curPattern.size() && astahNum == curAstahNam && pattern < curPattern)) {
curPattern = pattern;
curAstahNam = astahNum;
}
head++;
} else {
tail++;
}
}
return curPattern;
}
int main() {
int T; cin >> T;
string A, B;
for (int i = 1; i <= T; i++) {
cin >> A >> B;
string answer = solve(A, B);
cout << "Case #" << i << ": " << answer << endl;
}
}
[/cpp]
反省
- ワイルドカードは空文字を含むって部分を読んでなかった。その時点で正解する可能性は無かった。問題はちゃんと読もう。おちつけ。
- しゃくとり法がやりたくて飛びついてしまった感。そもそも、50文字までなら部分文字列も総当たりできた。ちゃんと問題のサイズを見て考えられるアルゴリズムを検討するべき。おちつけ。
- a*cみたいに文字の間にワイルドカードが入るケースをなんとなくで簡単に切り捨ててた。おちつけ。
- D,E読んでないのもいくなかった。せっかく日本語なんだから、点とれたかわからないけどとりあえず全部読んで、総当たりでSmall解けそうかぐらいは考えてみるべきだった。
予選、決勝と楽しかった！今回で競技プログラミングやる人増えたはずだし、また日本語のCodeJamやって欲しいな。スキルと落ち着きを身につけて次回はもっといい順位とりたい。チャレンジブックとGCJ過去問とTopCoderで鍛えよう