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みたいなのがあったらもう少しすっきりしそうなんだけどなあ、って思いながら書いてた
  • 圧縮かけたら良く縮みそう
  • 実は各色に関して偶奇性だけ見ればよかったらしいよ