hogecoder

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

CS Academy: Sorting Steps

公式の解説が鮮やかだったけど、英語がちょっと読みにくかったので日本語解説を作ってみたくなりました。

問題概要

原文 → CS Academy

長さ  N (1 \leq N \leq 10^{5}) の配列をバブルソートすることを考える (どんな実装かは、原文にサンプルコードがあるのでそちらを参照してください)。

ソートが完了した時の、"steps" の値を出力せよ。

解説

なんとなくセグ木とかを使いたい気持ちになりますが、公式の解説を見るとソートをするだけで解いているのでビックリです。どうやれば解けるのか、詳しく見ていきましょう。なお、説明のため、 A_{i} := 配列の  i 番目の値 とします。 (ここからの内容はほぼ公式解説と同じです)

まず、 C_{i} :=  i 番目の要素より左にあり、かつ値が  A_{i} よりも大きい要素の個数 と定義します。もしも全ての  i について  C_{i} = 0 ならば、既にソート済みです。

ここで重要な考察として、バブルソート 1 ステップ進めると、 C_{i} \gt 0 を満たす全ての  C の値がそれぞれ  1 減少します。 なぜなら、それを満たす要素それぞれについて、自分より左にある要素の中で最大の要素とスワップされ、自分より左にあって自分より大きい要素の個数が  1 個減るからです。全ての  C の値が  0 (= ソート済み) になるために必要なステップ数が  \max(C) + 1 回であることは明らかなので、あとは  \max(C) を求められれば OK です。

全ての  C を求めるのであれば前述の通りセグ木等を使う必要がありますが、今回必要な値は  \max だけなので、もっとシンプルに解くことができます。

まず、どのような要素が  \max(C) の候補になりえる・またはなりえないかを考えます。これについて、 ソート前配列の  i 番目の要素について、その右に自分より小さい要素があるならば、 C_{i} \max になることはない という重要な考察ができます。

これを簡単に証明します。 i \lt j であって  A_{i} \gt A_{j} である組  (i, j) を考えます。このとき、 C_{j} の計算において  i 番目の要素を考慮すると  C_{i} \lt C_{j} が成り立つことがわかります。これにより、自分より小さい要素が自分より右にあるならば  \max(C) の候補になりえないことが示せました。 (個人的にここの部分が一番巧妙だと思います。)

つまり、 \max(C) の候補になる要素は、 自分より小さい要素全てが自分より左の位置にあること を満たす必要があります。そしてそのような候補について、 C は (ソート済みの状態であるときのインデックス) - (ソート前の状態であるときのインデックス) で計算できます。よって、元のインデックスの情報を保持しながら配列をソートして、前述の計算の  \max を取れば良いです。

ソースコード

ほぼ Writer 解と同じですが・・・。

signed main() {
    int N; cin >> N;
    vector<pii> v(N);
    rep(i,0,N) {
        int p; cin >> p;
        v[i] = make_pair(p, i);
    }
    sort(v.begin(), v.end());

    int ans = 0;
    rep(i,0,N) {
        chmax(ans, v[i].second - i);
    }
    cout << ans + 1 << endl;
    return 0;
}

こういうシンプルな考察ができる頭になりたい。

天下一プログラマーコンテスト 2016 予選 A C: 山田山本問題

この手の問題すき。すきだから記事を書いてしまう。

問題概要

原文を参照してください → C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder

解説

まずは、  A_{i} B_{i} より辞書順で小さくするには、どのような戦略が必要かを考えてみましょう。

辞書順で大きく / 小さくなる場合は

  1. 両方の文字列の  k-1 文字目まで一致しており、 k 文字目が異なっている場合
  2. 片方の文字列が、もう片方の文字列の prefix と完全一致している場合

の、  2 通りしかありません。

 1 番目については、各文字列の  k 文字目を見て、どの文字がどの文字よりも辞書順で小さくなる必要があるかを見れば十分です。例えば、 "yamamoto" と "yamada" は  4 文字目まで一致していますが、 5 文字目が異なっているので、 5 文字目のアルファベットについて注目すれば十分であり、この場合だと 'm' が 'd' よりも辞書順で小さく定義される必要があります。

 2 番目については、 1 番目と違って辞書順の定義を変えたらどうにかなるものではありません。どういうことなのか、もう少し掘り下げてみましょう。

文字列  S が、文字列  T の prefix と一致しているとします。 S = "yama"、  T = "yamamoto" などがその例です。このとき、 S T よりも辞書順で必ず小さくなります。 これを踏まえると、

  •  B_{i} A_{i} の prefix と一致する場合は、条件を満たすアルファベットの順番が存在しない

と言えます。

さて、辞書順で 大きい / 小さい / そもそも不可能 かどうかの判定はこれで良いことが分かりましたが、あとはどのように構築すればよいでしょうか?

これは、各アルファベットを頂点とみなし、「アルファベット  c_{1} c_{2} よりも辞書順で小さく定義される必要がある」という情報を、  (c_{1}, c_{2}) の有向辺を張って*1 表現することで、糸口が見えてきます。この有向グラフが DAG であることと、条件を満たすアルファベットの順番が存在することが同値なので、トポロジカルソートをすれば良いです。

ただし、適当にトポロジカルソートをやってしまうと辞書順最小が果たせないため、少し工夫をします。例えば Kahn のアルゴリズムでは入次数  0 の頂点を queue に入れてよしなにトポロジカルソートをやると思うのですが、この queue を priority_queue に変えることで、現時点で使える頂点のうち常に辞書順最小のものが手に入るため、辞書順最小のアルファベット列が構築できます。

ソースコード

template <typename T>
vector<int> tpsort_Kahn(const vector< vector< Edge<T> > > &g) {
    const int V = g.size();
    vector<int> indeg(V, 0);
    priority_queue< int, vector<int>, greater<int> > S;

    rep(i,0,V) rep(j,0,g[i].size())
        indeg[ g[i][j].to ]++;
    repr(i,V-1,0) if(indeg[i] == 0) S.push(i);

    vector<int> ans;
    while(S.size() > 0) {
        int u = S.top(); S.pop();
        ans.push_back(u);
        rep(i,0,g[u].size()) {
            indeg[ g[u][i].to ]--;
            if(indeg[ g[u][i].to ] ==  0)
                S.push( g[u][i].to );
        }
    }
    return ans;
}

int keynum(string a, string b) {
    int N = a.length(), M = b.length();
    rep(i,0,min(N,M)) {
        if(a[i] != b[i]) return i;
    }
    if(N < M) return -2; // OK
    else return -1; // NG
}

signed main() {
    int N; cin >> N;

    Graph<int> G(26);
    bool ng = false;
    rep(i,0,N) {
        string a, b; cin >> a >> b;
        int key = keynum(a, b);
        if(key == -1) ng = true;
        else if(key >= 0) {
            int p = a[key] - 'a', q = b[key] - 'a';
            G[p].push_back(Edge<int>(q, 1));
        }
    }

    vector<int> tp = tpsort_Kahn(G);
    if(tp.size() != 26) ng = true;

    if(ng) cout << -1 << endl;
    else {
        string ans = "";
        rep(i,0,tp.size()) {
            ans += ('a' + tp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

ライブラリを少しいじらないと正解にならない問題ほんとすき。

*1:例えば "yamamoto", "yamada" では 'm' が 'd' よりも小さい必要があるので ('m', 'd') の有向辺を張る

天下一プログラマーコンテスト 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;
}

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