AtCoder Regular Contest 014
Cまで。
A - 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう
やるだけ。
awk '$0=$1%2?"Red":"Blue"'
- perlに負けてた。
awk '...'
という呼び出し部分が無ければ勝ててた - この複雑さならbrainfuckで遊んでもよかったかも
B - あの日したしりとりの結果を僕達はまだ知らない。
やるだけ(ただし丁寧に)。1RE, 1WA。
awk -f <<'EOF'
...
EOF
ってやって1RE。cat a.awk | xclip -i
ってやって、提出のtextarea上で適当にしたがための悲劇。
しりとりなので単語を重複させても敗北なの忘れてて1WA。
awk 'BEGIN { result = "DRAW" }
NR == 1 { n = $0 }
NR == 2 { w = $0 }
NR >= 3 {
v = w
used[v] = 1
w = $0
if (result == "DRAW") {
if (substr(v,length(v),1) != substr(w,1,1) || w in used) {
result = NR % 2 ? "WIN" : "LOSE"
}
}
}
END { print result }'
- 結構いける
substr(s,i,1)
じゃなくてs[i]
って書きたい- atcoderは何故awkを直接提出させてくれないのか
C - 魂の還る場所
やったら運良く通った。
とりあえず、問題文の理解の確認やサンプルの生成器を兼ねて、部分点解法を書いた。$n \le 15$なので普通に試せば間に合う。std::deque
が便利。
なんだか貪欲っぽさを感じたので、消せる場合は消せる側からのみ入れるようにしてみた。すると手元で生成したケース全てにACした。しかも$n = 50$のケースにもかなり高速に解答していた。投げてみたら通った。制限時間2sのところを1番遅いケースでも221msとけっこう高速。
#include <iostream>
#include <deque>
using namespace std;
int f(int i, string const & s, deque<char> & q);
int push_back(int i, string const & s, deque<char> & q) {
int result;
if (not q.empty() and q.back() == s[i]) {
q.pop_back();
result = f(i+1, s, q);
q.push_back(s[i]);
} else {
q.push_back(s[i]);
result = f(i+1, s, q);
q.pop_back();
}
return result;
}
int push_front(int i, string const & s, deque<char> & q) {
int result;
if (not q.empty() and q.front() == s[i]) {
q.pop_front();
result = f(i+1, s, q);
q.push_front(s[i]);
} else {
q.push_front(s[i]);
result = f(i+1, s, q);
q.pop_front();
}
return result;
}
int f(int i, string const & s, deque<char> & q) {
if (i == s.size()) {
return q.size();
} if (q.size() <= 1) {
return push_back(i, s, q);
} else if (q.back() == s[i]) {
return push_back(i, s, q);
} else if (q.front() == s[i]) {
return push_front(i, s, q);
} else {
return min(push_back(i, s, q),
push_front(i, s, q));
}
}
int main() {
int n; string s; cin >> n >> s;
deque<char> q;
cout << f(0, s, q) << endl;
return 0;
}
- ずっと同じ参照を引き回してるのを複製をstackに積むように変えてみたらTLEした
- $O(1)$の
reverse
みたいなのがあったらもう少しすっきりしそうなんだけどなあ、って思いながら書いてた - 圧縮かけたら良く縮みそう
- 実は各色に関して偶奇性だけ見ればよかったらしいよ