naoya_t@hatenablog

いわゆるチラシノウラであります

SRM727

久しぶりに参戦。1完。

o-- +0/-0 119.36pt 72nd 1438 -> 1478(+40)

問題を1つでも開いた参加者の数はDiv Iで190人。順位2桁でもratingは大して上がらない。

Easy - OnlySanta (250)

SATAN/SANTAのすべてのprefixについて、Sの各位置までに存在しているか否かを(DPで)調べて
文末に足りないSANTAのsuffixを足す。
但し、SATAと来てる時にそれより後にNを入れると死なので、SATの後にNTを挿入するとか。
先にSAT + NTAの組み合わせを考えてたせいでそうしてるけど、Tの前にNを入れればよりシンプルに済むけど書き直さなかった)
→AC (119.36pt)

#include <bits/stdc++.h>
using namespace std;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define all(c)  (c).begin(),(c).end()

#define p_ 0
#define p_S 1
#define p_SA 2
#define p_SAN 3
#define p_SANT 4
#define p_SANTA 5
#define p_SAT 6
#define p_SATA 7
#define p_SATAN 8

const char* sp_[9] = { "_", "S", "SA", "SAN", "SANT", "SANTA", "SAT", "SATA", "SATAN" };
//
class OnlySanta {
private:
    int check(string& S, vector<int>& stat) {
        int L = S.size();
        vector<vector<int>> st(L+1, vector<int>(9, 0));
        rep(j,9) st[0][j] = 0;
        int sat = -1;
        rep1(i, L) {
            rep(j,9) st[i][j] = st[i-1][j];
            switch (S[i-1]){
                case 'S':
                    ++st[i][p_S]; break;
                case 'A':
                    if (st[i][p_S]) ++st[i][p_SA];
                    if (st[i][p_SANT]) ++st[i][p_SANTA];
                    if (st[i][p_SAT]) ++st[i][p_SATA];
                    break;
                case 'N':
                    if (st[i][p_SA]) ++st[i][p_SAN];
                    if (st[i][p_SATA]) ++st[i][p_SATAN];
                    break;
                case 'T':
                    if (st[i][p_SAN]) ++st[i][p_SANT];
                    if (st[i][p_SA]) {
                        if (sat == -1) sat = i;
                        ++st[i][p_SAT];
                    }
                    break;
                default:
                    break;

            }
        }
        stat = st[L];
        return sat;
    }
public:
    string solve(string S) {
        vector<int> st(9, 0);
        int sat = check(S, st);

        string ans;
        if (st[p_SATAN]) ans = "IMPOSSIBLE"; // impossible
        else if (st[p_SANTA]) ans = S;

        else if (st[p_SANT]) ans = S+"A";
        else if (st[p_SAN]) ans = S+"TA";

        else if (st[p_SATA]) {
            // SAT(NT)A
            ans = S.substr(0,sat) + "NT" + S.substr(sat);
            // ↑↑ここは SA(N)TA で良かったんだけどね ... ans = S.substr(0,sat-1) + "N" + S.substr(sat-1); で
        }
        else if (st[p_SAT]) {
            // SAT(NTA)
            ans = S + "NTA";
        }
        else if (st[p_SA]) ans = S+"NTA";
        else if (st[p_S]) ans = S+"ANTA";
        else ans = S+"SANTA";

        return ans;
    }
};

Medium - Subrectangle (500)

開いた
とりあえずRLE見てみる
前後のスペースは(文字数のカウントは記憶しつつ)一旦消す

余分な文字は挿入されていないから、くっついてるmarkedが分断されることはない
というか
markedが分断される時 = 左から右までびっしり埋まってる時のみ
あとは幅をあれこれ変えてみて、文字を補って辻褄が合わせられるか見る
みたいな方針を考えてたんだけど
時間切れ

Hard (900)

開いてない

Challenge Phase

座るだけ
落とされなかった

System Test

通った