hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

天下一プログラマーコンテスト 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 君を助けきれなかったのも心残り。デバッグの方法とかいろいろ提案したけど、もっと早いうちから提案しておけば少しは状況違ったのかなあ・・・とか、いろいろ考えてしまう。次に実装でハマる問題が出てきた時はもっと早急に助けられるようにしたい。

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

さいごに

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

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

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

本番出てた回。ようやく復習できました。

問題概要

原文 → Problem - C - Codeforces

長さ  N の数列があり、 i 番目の要素を  a_{i} と書く。

次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合計を最大化せよ。

  • 区間内に登場する要素  val それぞれについて、  val と同じ値を持つ全ての要素が必ず同一の区間内に含まれていなければならない。
  • 区間の重みは、区間内に登場した数字の集合の XOR である (例えば、 \left[ 2, 5, 2, 3 \right] という区間であれば、区間の重みは  2 \oplus 5 \oplus 3 = 4 となる。)

解説

まず、各値について最左、及び最右のインデックスを覚えておき、これを  l_{val}, r_{val} と表記することにします。

取りたい区間の左端  L を固定して、dp[i] = [0, i) の範囲での重み合計の最大値 なる DP を解くことを考えます。問題文の条件より、取りたい区間の中にある要素のうち、最左のインデックス  l_{a_{cur}} L より左であるものがあれば、その区間は invalid です。逆にそうでない場合、区間の右端  R \max ( R, r_{a_{cur}} ) に伸ばす、すなわち今まで出てきた要素と同じ値をもつ全ての要素を同一の区間内に入れられるまで区間を伸ばしたあと、 DP 配列を更新します。

ソースコード

実装はとても楽です。大正義半開区間

int N, a[5010];
int l[5010], r[5010], dp[5010];

signed main() {
    cin >> N;
    rep(i,0,5010) l[i] = INF, r[i] = -1;
    rep(i,0,N) {
        int p; cin >> p;
        a[i] = p;
        chmin(l[p], i);
        chmax(r[p], i+1);
    }

    rep(i,0,N) {
        chmax(dp[i+1], dp[i]);
        if(l[ a[i] ] == i) {
            int ub = r[ a[i] ], cur = i, val = 0;
            bool ng = false;
            while(cur < ub) {
                if(l[ a[cur] ] < i) ng = true;
                if(l[ a[cur] ] == cur) val ^= a[cur];
                chmax(ub, r[ a[cur++] ]);
            }
            if(!ng) dp[ub] = dp[i] + val;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

問題で要求されている条件のわりに実装が簡単で面白いですね。

AtCoder Beginner Contest 020 D: LCM Rush

もう 7 月かあ・・・。

問題概要

 \sum_{i=1}^{N} lcm(i, K) \mod 1,000,000,007 を求めよ。ただし  lcm(a, b) a b の最小公倍数を指す。

制約:  1 \leq N, K \leq 10^{9}

解説

愚直にやるのは無理なので、数学をします。

まず、 lcm(a, b) = a \times b / gcd(a, b) なる関係があります。これを使って与式を変形すると

 \sum_{i=1}^{n} i \times K/gcd(i, K) が求めたいものになります。

ここで、 gcd(i, K) の取りうる値の数は  K の約数の数ぶんしかないことに注目します。この制約下では最大  1344 個であり、比較的少ないです。最大公約数の値が同じものについて、まとめて処理できると嬉しいよなあという気持ちになるため、 gcd の値ごとに分けて考えることにしましょう。

まずは、 gcd(i, K) = 1 を満たす  i について、 lcm(i, K) の総和  S を考えてみましょう。これは、

 S = \sum_{1 \leq i \leq N, gcd(i, K) = 1} lcm(i, K) = K \times \sum_{1 \leq i \leq N, gcd(i, K) = 1} i

となり、条件を満たす  i の総和と  K の積になります。

条件を満たす  i の総和は包除原理によって求めることができます。 K の素因数を列挙し、素因数偶数個の積を約数にもつ数の総和は足し、素因数奇数個の積を約数に持つ数の総和は引き・・・という方針で求められます。(包除原理に関しては他サイトを参照してください)

次に、 gcd(i, K) = x を満たす  i について、 lcm(i, K) の総和  T を考えてみましょう。これは変形すると先ほどの計算と同じ方針でできます。

 gcd(i, K) = x は、  gcd(i/x, K/x) = 1 と同値です。よって、

 T = \sum_{1 \leq i \leq N, gcd(i, K) = x} lcm(i, K) = K \times \sum_{1 \leq i' \leq \lfloor \frac{N}{x} \rfloor, gcd(i', \lfloor \frac{K}{x} \rfloor) = 1} i'

となります。

まとめると、

  1.  K の約数  M それぞれに対して以下を行う
  2.  1 \leq i \leq \lfloor \frac{N}{M} \rfloor かつ  gcd(i, \lfloor \frac{K}{M} \rfloor) = 1 を満たす  i の総和を答えに足す
  3. 2 の操作は包除原理によって高速に処理できる

ということになります。

ソースコード

割と綺麗に書けて個人的には満足です。

int N, K;

// 約数の列挙
vector<int> divisor(int n) {
    vector<int> ret;
    for(int i=1; i*i<=n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(n / i != i) ret.push_back(n/i);
        }
    }
    return ret;
}

// 素因数の列挙
vector<int> pFactorization(int n) {
    vector<int> ret;
    for(int i=2; i*i<=n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            while(n % i == 0) n /= i;
        }
    }
    if(n != 1) ret.push_back(n);
    return ret;
}

// 1 <= i <= n, gcd(i, m) = 1 なるすべての i の和を求める
int solve(int n, int m) {
    vector<int> vp = pFactorization(m);
    int s = vp.size(), ans = 0;
    rep(bit,0,1<<s) {
        int num = 1;
        rep(i,0,s) if(bit >> i & 1) num *= vp[i];
        int a = (n / num) % MOD;
        int b = (a * (a+1) / 2) % MOD;
        int c = num % MOD;
        if(__builtin_popcount(bit) % 2) {
            int sub = (b * c) % MOD;
            ans = (ans - sub + MOD) % MOD;
        }
        else {
            (ans += b * c) %= MOD;
        }
    }
    return ans;
}

signed main() {
    cin >> N >> K;
    vector<int> div = divisor(K);
    int ans = 0;
    rep(i,0,div.size()) {
        (ans += solve(N/div[i], K/div[i]) * K) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

解けるまでだいぶ時間かかったので、これは要復習かも。

Snackdown 2017 Pre-elimination A: Consecutive Snakes

これは良問だなあと思った。

問題概要

原文 → Contest Page | CodeChef

長さ  L (1 \leq L \leq 10^{9}) の蛇が数直線上に  N (1 \leq N \leq 10^{5}) 匹おり、 i 番目の蛇の左端の座標は  S_{i} (1 \leq S_{i} \leq 10^{9}) である。つまり、  i 番目の蛇は区間  \left[ S_{i}, S_{i} + L \right] にいる。

いま、この蛇たちを以下の条件が成り立つように移動させたい。

  • N 匹の蛇すべてについて、区間  \left[ A, B \right] (1 \leq A, B \leq 10^{9}) の中にいる
  • 左から  i 番目の蛇の右端と  i+1 番目の蛇の左端は繋がっている。つまり  1 番目の蛇が区間  \left[ X, X + L \right] にいるとき、 2 番目の蛇は  \left[ X + L, X + 2L \right] におり、 \dots N 番目の蛇は  \left[ X + (N-1)L, X + NL \right] にいる。

ある蛇が  \left[ X_{1}, X_{1} + L \right] から  \left[ X_{2}, X_{2} + L \right] に移動するとき、コストが  | X_{1} - X_{2} | かかる。全体コストはこのコストを  N 匹に対して計算した時の総和である。条件が成り立つように移動させた時の全体コストの最小値を出力せよ。

解説

まず、条件より以下のことがわかります。

  • 一番左にくる蛇の左端の座標を決定すると、全ての蛇の左端の座標が決まる
  • 移動前に左から  i 番目にいた蛇は、移動後も左から  i 番目にいたほうが良い

つまり、蛇を座標順にソートしておいて、一番左の蛇がどこにいるか決めてしまえば、コスト計算はできるということです。しかし、制約を見ると一番左の蛇の配置パターンは非常に多いことがわかるので、何か工夫が必要です。そこで、一旦定式化して考えましょう。

一番左の蛇の左端を  x とします。すると、 i 番目の蛇の左端は  x + i L と表せます (0-indexed)。移動前に左から  i 番目にいた蛇の左端を  S_{i} とすると、全体コストは以下のように書けます。

\begin{align} cost &=& \sum_{i=0}^{N-1} | S_{i} - (x + iL) | \\ &=& \sum_{i=0}^{N-1} | (S_{i} - iL) - x | \\ &=& \sum_{i=0}^{N-1} | T_{i} - x | \end{align}

 S_{i} - iL x の値の設定に関係なく決まるので、定数とみなして良いです。これを新たに  T_{i} とします。

 T_{i} をソートすると、 T_{0} \leq T_{1}\leq \dots \leq T_{N-1} のような形になります。さて、 T_{i} \leq x を満たす最大の  i j とすると、全体コストはこのように書けます。

 cost = \sum_{i=0}^{j} (x - T_{i}) + \sum_{i=j+1}^{N-1} (T_{i} - x)

コスト関数は絶対値付きの一次関数を足しあわせた形になっているので凸関数です。よって、 x について二分探索して解くことができます。

計算量はソート  O(N \log N)、二分探索パートでコスト計算時に upper_bound が必要なため  O(\log N \log C) です  (C = B - A)

ソースコード

累積和を 0-indexed にすると配列外参照が起こるので、そこだけ 1-indexed で書いています。

int T, N, L, A, B;
int s[100010];
int t[100010], acc[100010];

int get(int l, int r) {
    l++; r++;
    return acc[r] - acc[l-1];
}

int calc(int x) {
    int idx = upper_bound(t, t+N, x) - t;
    int vl = idx * x - get(0, idx-1);
    int vr = get(idx, N-1) - (N-idx) * x;
    return vl + vr;
}

signed main() {
    scanf("%lld", &T);
    rep(cases, 0, T) {
        scanf("%lld%lld%lld%lld", &N, &L, &A, &B);
        rep(i,0,N) scanf("%lld", &s[i]);
        sort(s, s+N);

        // 累積和は 1-indexed
        rep(i,0,N) t[i] = s[i] - i * L;
        sort(t, t+N);
        rep(i,0,N) acc[i+1] = acc[i] + t[i];

        // A <= x <= B を満たす x で最小を求めよう
        int lb = A - 1, ub = B - N * L;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(calc(mid) < calc(mid+1)) ub = mid;
            else lb = mid;
        }
        cout << calc(ub) << endl;
    }
    return 0;
}

二分探索に落とし込めた時はちょっと感動した。自力で解けてよかった。

競プロをやりはじめてから一年が経ちました

競プロをやりはじめて、今日でちょうど一年です。半年記事 に引き続き、ポエム的なものを書いていきます。

続きを読む