hogecoder

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

DDCC2017 本戦 参加記

大会参加記

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 に参加しました。去年の DDCC に引き続き、 2 回目の参加となります。

予選

予選は全完 122 位でした。D 問題が解けたのは嬉しかったのですが、結構条件漏れが多くてサブミットデバッグ気味になってしまい、ペナルティ無しの恩恵を受けまくって本戦進出できた感じですね・・・。

今回は就活枠 (19 卒枠) の対象外ゆえ交通費や宿泊費が自己負担なので正直行くかどうか迷っていたところもありましたが、TL の人々に会いたかったですし、なにより去年のあの雰囲気がとても好きだったのでそれをもう一度味わいたいなあと思い本戦に参加することにしました。

本戦の前

去年の反省を活かして受付 30 分前くらいに会場入り。たぶん一番乗りでした。

ロビーで出会った方々とおしゃべりしつつ、謎パネルを撮りつつ、受付開始を待っていました。

受付後、コンテスト本番が始まるまで時間があったので、なけなしのコミュ力を発揮して人々に会いに行きました。人生で初めてサインを求められてびっくりした (おかゆさん、olphe さんありがとうございました！)

そんなこんなでコンテスト本番の時間が近づく。去年ほどは緊張しなかったとはいえ、やっぱり緊張しますね・・・。

コンテスト本番

本戦は 2 完 77 位でした。去年の本戦は底辺みたいな順位だったので、それに比べたらだいぶ成長しました。が、C 解けなかったのは悔しいですね・・・

A 問題

なんかデジャヴを感じる。去年の自分のソースコード引っ張りだそうかなと思ったけど解読に時間がかかりそうなのでやめた (それはそう)

円の半径を R とします。各正方形について 4 つの頂点の座標を列挙し、この 4 点すべてについて円の中心との距離が R 以下なら、その正方形は切り出せます。正直コレだけなんですが、距離を計算するときに x*x + y+y みたいな typo をしたり、配列が作れなかったり (は？) してグダグダでした。大反省ものです。

AC (17:04)

B 問題

正直この問題が最も簡単でした。

自分の解法としてはこんな感じです。早い段階でサンプルから察せたのが良かったのかなと思います。ただ X を作る際に gcd の結果を素因数分解する必要があるんじゃないか、みたいに一瞬逸れかけたので危なかったです。反省。

AC (23:47)

C 問題

解けませんでした (悲しいね)。以下嘘考察です。

距離の総和が 0 でないサイクルを列挙して、そのサイクルすべてについて

  • 共通の辺が少なくとも 1 つ存在する (それがないと一部のサイクルについて総和を操作できないので)
  • 各サイクルの距離の総和が同じ (距離を変えられるのは 1 辺だけなので)

が成り立てば嬉しいよなあと思いましたが、そもそもサイクルの列挙があやしいし共通の辺を探すのも難しい。どうすればいいのかなあという感じでした。

上の条件をクリアする策はあまり出てこなくて、なんか 1 辺だけ取り除いた時にトポロジカルソートできたらいいのでは？みたいな謎の考察を苦し紛れに思いついて、他にやることもないのでそれを実装していたのですが、結局嘘だったようです。完全に思いつきだったので仕方ないです。悔しいので解き直します。

D 問題

1100 点問題だしやばみなんだけど一応読みました。でもこれに時間をかけるのは実力的に間違っている気がしたのであまり考察しませんでした。

解説を読んだ感じだと、割と思いつきやすい DP を枝刈りしたみたいな感じだったので意外でした。あとで解いてみようと思います。

DDCC 特別ビュッフェ

えび

結構いろんな人とおしゃべりしました。らてあさんが tourist じゃんけんの人として認識されているのが面白かったです。

特別対談

将棋は全く詳しくないのでどの程度まで話についていけるのかなあと対談前は不安に思っていたのですが、全然そんな心配する必要なかったです。めちゃくちゃ楽しかったです。

コンピューター将棋 vs. 日本将棋界の変遷の概要やプロ棋士の戦術・学習法の変化、さらにはコンピューター将棋の意義まで、興味深い話題がたくさんありました。

これから頑張らなきゃなあと思えた話としては、「競技プログラミング意外の技能も身につけたほうがいいよ」という話。競技プログラミングが狭く深い世界であることは自分も理解していますし、おそらくそういう認識を持っている競プロ er が他にも多くいるような気がします。これから自分がどう成長していけるのか、どのフィールドで輝けるのか、考えていきたいですね。

あとはこんな話題も。

コンピューターの成長は指数的で、人間の予想をはるかに上回るという話。自分は 5 年後くらいにはコンピューターに競プロ負けてるかも。そうなったら悲しいのでがんばります。

社内ツアー

去年に社内ツアーに行ったので、2 回目以降の人向けのツアーに参加しました。

社用車が電気自動車だったり、オフィスの風通しが良かったり、やっぱりすごい会社ですね・・・

毎度おなじみウェーハカットもばっちり見れました。やったね。

懇親会

懇親会もいろんな人と話しました！

RUPC 以来に会った方が結構いました。半年前に比べて強くなった方ばかりなので、自分も成長しないとなあと思います。

ちょくだいさんが最速最強アルゴリズマー養成講座にサインしてくださいました！うれしい！ありがとうございました！！

まとめ

オンサイト最高！！！！！

来月初めの CODE THANKS FESTIVAL でまたお会いしましょう！！！

CS Academy: Sorting Steps

CS Academy 要考察

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

問題概要

原文 → 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: 山田山本問題

AtCoder 文字列 グラフ

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

問題概要

原文を参照してください → 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') の有向辺を張る