hogecoder

tsutaj 競技プログラミングの記録

天下一プログラマーコンテスト 2016 C: たんごたくさん

初めて Trie 木を使ったので、ハマったところとかを記事でまとめておきます (完全に自分用)

問題概要

原文参照 → C: たんごたくさん - 天下一プログラマーコンテスト2016本戦(オープンコンテスト) | AtCoder

解説

与えられる単語すべてを検索対象として、Trie 木を作ります。

文字列  S i 文字目  s_i を左端とする  S の部分文字列であって、単語と完全一致するものを考えます。単語の長さが高々  200 であることから、部分文字列の選び方は  200 通りしかありません。この制約だと、部分文字列の左端を決め打ちしてこの  200 通りを全て試すことで間に合うため、それを基にして DP を実装すればよいです。

ただ、部分文字列を作るために substr を使ったり、文字列検索のためにいちいち trie 木の根から走査していくと TLE になるため、前の結果をうまく使う必要があります。自分の実装では、文字列検索時に Trie のポインタを動かして、部分文字列の右端が右に移動する (= 部分文字列が 1 文字増える) ときに前の結果を用いて高速に処理するようにしています。

ソースコード

struct Trie {
    Trie* node[26];
    int score;
    Trie() {
        score = 0;
        fill(node, node+26, (Trie *)0);
    }
    void insert(const string &s, int val) {
        Trie* r = this;
        for(size_t i=0; i<s.length(); i++) {
            int c = s[i] - 'a';
            if(!r -> node[c]) r -> node[c] = new Trie;
            r = r -> node[c];
        }
        r -> score = val;
    }
    Trie* find(const char &s, Trie* pos) {
        int c = s - 'a';
        if(!pos -> node[c]) return (Trie *)0;
        return pos -> node[c];
    } 
};

string p[5010];
int score[5010], dp[200010];

signed main() {
    Trie trie;
    string s; cin >> s;
    int M, N; cin >> M; N = s.length();

    rep(i,0,M) cin >> p[i];
    rep(i,0,M) cin >> score[i];
    rep(i,0,M) trie.insert(p[i], score[i]);

    rep(i,0,N) {
        Trie* cur = &trie;
        repq(k,1,200) {
            if(i+k > N) continue;
            char target = s[i+k-1];
            Trie* next;
            if(cur != (Trie *)0) {
                next = trie.find(target, cur);
                cur = next;
                chmax(dp[i+k], (cur != (Trie *)0) ? dp[i] + cur -> score : dp[i]);
            }
            else chmax(dp[i+k], dp[i]);
        }
    }
    cout << dp[N] << endl;
    return 0;
}

ハマったところ

  • 出現する文字は英小文字のみなので Trie のポインタ配列は 26 あれば十分 (ライブラリでは 256 にしていて、それをそのまま使うと MLE した)
  • find は前の結果をうまく使わないと遅くなる (いちいち trie 木の根からやるのはアウト)
  • 左端を固定するとき、ある部分文字列に対してマッチするものがなければ、その後右端を伸ばしてもマッチするはずはないが、値の伝搬は忘れない (break で抜けると伝搬が起こらないのでアウト)

AtCoder Regular Contest 079 D: Decrease (Contestant ver.)

どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。

問題概要

日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder

解説

まず、出力する数列の長さは  N = 50 に固定してしまいます。この方が大きな入力にも対応できるからです。(もちろん、小さな入力にも対応できる)

 i 番目の要素の値を  a_{i}、また  i 番目の要素に対して操作を行う回数を  s_{i} と表すことにします。

まずは、  s_{i} の値がなるべく均等になるように操作回数を各要素に配分しましょう。すると、 i 番目の要素の値は、他の要素で操作を行うことで  \sum_{1 \leq j \leq N, j \neq i} s_{j} 増えることがわかります。この増分を  D_{i} とします。

これで、 i 番目の要素は  a_{i} + D_{i} という値まで増え、操作回数は  s_{i} 回必要であることがわかりました。あとは、この情報を元に  a_{i} を決めれば答えがわかります。

要素の値が  N 以上なら操作を 1 回行う必要があり、  2N 以上なら 2 回・・・ということを考えると、このような式を満たせば良いことがわかります。

 \displaystyle \lfloor \frac{a_{i} + D_{i}}{N} \rfloor = s_{i}

床関数があって扱いにくいので、変形します。

 N \times s_{i} \leq a_{i} + D_{i} \lt N \times (s_{i} + 1)

したがって、

 N \times s_{i} - D_{i} \leq a_{i} \lt N \times (s_{i} + 1) - D_{i}

この範囲に収まるように  a_{i} を決定すれば良いことがわかりました。あとはこの範囲内の値になるように適当に決めたら良いです。

※注意:  a_{i} の下限は  0 ですので、負の値にならないように気をつけましょう。

ソースコード

int K, rec[60], ans[60];
const int N = 50;

signed main() {
    cin >> K;
    int div = K / N, mo = K % N;
    rep(i,0,N) rec[i] = div + (i < mo);

    rep(i,0,N) {
        int sum = 0;
        rep(j,0,N) if(i != j) sum += rec[j];
        ans[i] = N * (rec[i] + 1) - sum - 1;
    }
    cout << N << endl;
    rep(i,0,N) cout << (i ? " " : "") << ans[i];
    cout << endl;
    return 0;
}

ICPC 国内予選 2017 参加記

今日を終わらせたくないので、この勢いのまま参加記を書いてしまいます。

チーム情報

今年は構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と就寝のプロ・自分 (tsutaj) の 3 人で、チーム four-t で出場しました。チーム結成は 4 月くらいだった気がします。

振り返り

リハーサルは圧倒的エスパー力により全完 1 位と幸先の良いスタート。このまま国内予選もうまくいってくれ〜〜〜となる。(これは罠でそんなにうまくいくわけがない)

本番までの空き時間は Primepop で精神を落ち着かせながら過ごした。3 桁の素因数分解つらい。やってるうちに慣れてきて素因数分解のプロに変化していくえび君を見ているのが楽しかった。

そしてなんだかんだで本番になる。自分はテンプレート書いて印刷かけて A 問題をやる担当になっていたので A 問題をやった。7 分くらいで AC。

その後、えび君が B 問題を難なく AC (自分が問題文を 1 文字も見ないまま終わってしまった)。その間に自分が D を考察していたけど、これ DP では? みたいになったので早速実装する。想定解法ではなさそうだけど (わりと実行時間かかるやつだった) 時間制限 3 時間の ICPC なので大丈夫やろ!w と思って動かしたら動いたのでよかった。D 問題無事 AC。

TAB 君が C 問題の実装に取り掛かった。自分は 4 完を最優先に考えていたのでデバッグに回った。今思うとこの選択がすごく良かったのかなあと思う (結局早解きで通過できたので)

バグをとって C も AC。ここまで 1 時間 15 分で、割と早いのでは?という気持ちになったけど、順位表を見ると既に結構 4 完がいたのでもう 1 問解いて安心しておきたいなあとなる。

残りの時間で F 問題を詰めようという話になり、ずっと考察していた。途中で方針が立ったので実装したけど、境界条件が非常に面倒でデバッグが辛い。全員でコードを睨みながら間違いを潰していく。コンテスト終了 5 分前くらいに惜しいところまではいったけれど、結局詰められず終了。悔しかった。

結果は 4 完 31 位、かつ学内 1 位だったのでおそらく通過できました。去年の悔しさからずっと頑張ってきたので本当に良かったです。

反省

E の解法を聞いたら単純な全探索らしく、この問題を早々に捨ててしまったのは完全にミスだったように思う。もっと問題文をよく読んで判断すべきだった。

あと G の解法も最初フローなのかなあ、でも辺どうやって張るんだ・・・とかいろいろ考えて諦めたけど結局左手法でうまくいくようで本当につらかった。まさか G 問題でそんな解法の問題が出るとは思わなかった・・・頭が固い・・・。

F で TAB 君を助けきれなかったのも心残り。デバッグの方法とかいろいろ提案したけど、もっと早いうちから提案しておけば少しは状況違ったのかなあ・・・とか、いろいろ考えてしまう。次に実装でハマる問題が出てきた時はもっと早急に助けられるようにしたい。

全体で見たら成績はそれなりに良かったものの、反省点は結構多いです。アジア地区までに修正したいです。

さいごに

国内予選だいすき!一番好きなコンテストです。

次も頑張ります。精進するぞ〜〜〜〜〜