ICPC アジア地区予選 2014 F: There is No Alternative

今年ももう終わりですね。

問題概要

原文 → http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf

重み付き無向グラフ が与えられる。 の最小全域木に必ず含まれる辺はいくつあるか？ 重みの総和と共に出力せよ。

• 
• 

解説

まず、普通に最小全域木を求めてしまいます。説明のため、ここで使われる辺の集合を 、最小全域木のコストを とします。

に含まれない辺は、最小全域木を構成する時に必要なかった辺ですので、「最小全域木に必ず含まれる辺」になりえないことは明らかです。以下、 の各要素 について考えます。

最小全域木に必ず含まれる辺 というのは、言い換えれば「その辺 がないと最小全域木が作れない」ということです。したがって、以下を試せばよいです。

• 以外の辺で最小全域木をつくろうとしてみる
• 最小全域木ができなければ (連結でなければ) 、その辺は「必ず含まれる辺」である
• 最小全域木はできるが、そのコストが より大きければ、その辺は「必ず含まれる辺」である

の要素数は高々 しかありませんので、各辺を無視した最小全域木計算のループは 回です。

クラスカル法を用いれば、辺のソート 、各辺を無視した最小全域木計算 より、実行時間内に解くことができます。

ソースコード

プリム法、Union-Find木のソースコードは省略します。

signed main() {
    int n, m; cin >> n >> m;
    Graph(int) G(n);
    vector< Edge<int> > es;
    int s, d, c;
    rep(i,0,m) {
        cin >> s >> d >> c; s--; d--;
        G[s].pb(Edge<int>(s, d, c));
        G[d].pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(s, d, c));
    }
    pii ans = pii(0, 0);
    pair< int, vector< Edge<int> > > v = prim(G);
    sort(es.begin(), es.end());
    int E = es.size();
    rep(i,0,v.sc.size()) {
        UnionFind uf(n);
        int res = 0;
        for(int j=0; j<E; j++) {
            Edge<int> e = es[j];
            if(e.to == v.sc[i].from && e.from == v.sc[i].to) continue;
            if(e.to == v.sc[i].to && e.from == v.sc[i].from) continue;
            if(!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                res += e.cost;
            }
        }

        int par = -1;
        for(int j=0; j<n; j++) {
            if(par == -1) par = uf.find(j);
            else if(par != uf.find(j)) res = INT_MAX;
        }

        if(res > v.fr) {
            ans.fr++;
            ans.sc += v.sc[i].cost;
        }
    }
    printf("%lld %lld\n", ans.fr, ans.sc);
    return 0;
}

ただのライブラリ貼るだけ問題じゃないので、好きな問題です。この手の問題たくさん解けるようになりたいですね。

おそらくこれが今年最後の投稿になるでしょう。良いお年を。

CODE THANKS FESTIVAL 2014 B日程 G: 石取りゲーム

久しぶりに解説記事。またまたゲームの問題。

問題概要

原文 → G: 石取りゲーム - code thanks festival 2014 B日程 | AtCoder

個の石が積まれた山があり、人のプレイヤーが交互に石を何個か取っていき、最後の石を取ったプレイヤーが勝ちとなるゲームを行う。1手で取れる石の個数は、ゲーム開始時に先手が取るときはの範囲、それ以降は (前のプレイヤーが取った石の個数) の範囲である。が与えられるので、両者が最善に行動した時の勝者を出力せよ。

解説

まず、solve(i, j)なる関数を考えます。これは、山に i 個石があり、1 〜 j 個の範囲で石が取れる時の勝者を bool 値で返します。

この問題で重要なことは、i と j が決まれば勝者が決まるということです。solve 関数同士の関係をみていきます。

• 取れる石の個数の最大値が残りの個数以上である場合、全部取れるため必ず勝てる
• 取れる個数を全て試して、その中でも一つでも false が返ってくれば勝てる
• 全て試してもヒットしなければ、勝てるパターンが無いため負け

ということが言えます。2つ目の条件でなぜ false なのかというと、ここで参照しているのは前のターンの出来事であり、先攻と後攻の扱いが逆転しているからです。したがってもう少しシンプルに書くと

• i <= j ならば true
• i > j のとき、1から j の範囲まで solve を試し、どこか1つでも false ならば true
• false が1回も返ってこなければ false

と判定できます。もちろん、メモ化が必須です。

ソースコード

int n, p;
int dp[510][510];

// 勝敗判定
bool solve(int rest, int range) {
    // メモ化 (すでに書いてあったらそれを返す)
    int &res = dp[rest][range];
    if(res != -1) return res;

    // range が rest を覆えるならば勝てる
    if(rest <= range) return res = true;

    bool ok = false;
    // 以下は range が rest を覆えない時の話
    // 範囲の中に一つでも false
    // (つまり前のターンで後手必勝) があるなら true
    // 取る石は 1 個以上 range 以下
    repq(i,1,range) {
        // 石は i 個なくなり、範囲は i+1 になる
        if(!solve(rest-i, i+1)) ok = true;
    }
    return res = ok;
}

signed main() {
    cin >> n >> p;
    memset(dp, -1, sizeof(dp));
    bool ok = solve(n, p);
    cout << (ok ? "first" : "second") << endl;
    return 0;
}

前にこのブログで紹介したゲームの問題の中にも、同じ方針で解けそうなものがありますね。ゲームの問題も奥が深いですね。

※追記: 前に紹介した問題たちは制約が大きいのでそもそもメモ化できないですね。同じような問題ですがこの解法は使えないです。難しいなあ・・・

DDCC2016 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト 2016 本戦に参加しました。どこよりも早く、を目指して参加記書いてみます。

-N日目 (予選)

セキュリティミニキャンプ in 北海道(過去記事参照) の1日目の夜にDDCCの予選があったので、ホテルからコンテストに参加した。

A問題はすぐ解けた。B問題は日本語が難しかったけどAC。Cは制約をくぐりぬける方法が分からず、結局2完・・・。このときボーダーラインを把握していなかったので絶対通ってないだろうなあと思っていた。

あとあと調べて、自分の順位でも本戦の可能性があることを知った。結局、161位で通過してた。うれしい。でも前回のDDPCを見るにこのままだと本戦で玉砕されるので頑張らないとなあという気持ちになった。

0日目 (本戦前日)

本州に住んでいないので前日移動必須。東京到着が遅くなりそうだったので、空港でラーメンとビールを食べてから飛行機へ。なんか天気予報では雪が降るとか言われてて、飛行機飛ぶのかどうかちょっと怖かったけど無事飛んでよかった。22時くらいにはホテルについてまったりしていた。

1日目 (本戦当日！)

23時半くらいに就寝を試みるも寝れず、睡眠が断続的になる。でも当日は5時に起きた。はやすぎ。前回のDDPC解いたりとかあがいていた。

少し早めに会場につくものの電源争奪戦に敗れる。パソコン2台もってきてよかった。Tシャツとシールをもらって「これがオンサイトか・・・」という気持ちになりテンションが上がる。

オープニングビデオがDDCC開会の合図。自分は北海道から来たのに「北は東北からお越しいただき～」みたいなアナウンスが入り笑ってしまった。開会式終わったらへんからめっちゃ緊張してきてやばかった (緊張のあまり手を震わせながらツイートしていた)。あと隣がやたらインタビューされてて大変そうだった。

そしていよいよ本戦スタート！

• 1問目はEPS考慮したら逆にバグったりしてつらかった(たぶん自分のライブラリに問題がある？)けどAC。
• 2問目は3つ目のケースがどうもうまくいかず唸ってたら部分点解法出すの忘れていた。結局満点取れなかったしつらさしかない・・・。
• 3問目は見たけどやってない。4,5問目は見てすらいない。こうして私の初オンサイトコンテストは散ったのだった・・・(オンサイトの洗礼)

幾何っぽい問題と文字列で攻められたら途端に点数が全く取れなくなるのはダメですね。分野によって理解度にムラがありまくるので、もっと精進していきたい・・・。

コンテストが終わって昼食フェーズ(懇親会)に入る。フォロワーに何人か会えてとてもテンションが上がり、オンサイト最高という気持ちが最高潮に達した。他の大学の競技プログラミング事情とか、競プロサークル等に所属せず趣味でやっている人の話とかいろいろ聞けて面白かった。

特別講演で厚切りジェイソン氏のお話を45分間ほど聞いた。米国と日本の会社の体質の違いとか、厚切りジェイソン氏本人の経験などなど貴重な話をたくさん聞けて良かった。リンゴの話が一番なるほどなあとなって、今だけでなく未来も見据えたうえでベストな答えは何なんだろうということを常に頭に入れて動かないとなと考えさせられた。

表彰式後に、懇親会パート2が始まった。ここでもフォロワーの何人かとお話しできてとても良い時間を過ごせた。来年のICPCの話とかもしてて、来年は国内予選抜けてアジア地区でまたいろんな人に会いたいなあ・・・とか思ってた。

総括

今回が初オンサイトだった私は、問題が解けるかどうかももちろん不安だったけど、競プロerの輪の中に入れるかどうかが結構不安だった。でもそれは意外と何とかなってとても楽しい時間を過ごせたし、何より今回で競技プログラミングに対するモチベーションがだいぶ上がったので行けて本当によかったなあと思う。またオンサイトの機会があればぜひ行きたいし、行けるようにもっと頑張りたい。

こんなとこかな。次のオンサイトはいつだろう・・・。