はじめに

こんにちは、テクノロジーイノベーショングループ・DXチーム所属兼、競技プログラミング部のtutuzです。

2018年11月17日に開催されたPG Battleというプログラミングコンテストに社内チームで参戦しました。

今回はその結果について説明します。

参加のキッカケ

私の競技プログラミング部での活動は、主にAtCoder, Codeforcesで開催されるコンテストへの参加です。

そんな中で、PG Battleの参加した理由は、弊社の tanzaku さんからの一言でした！

https://products.sint.co.jp/pg_battle_2018
申込み期限まで日がないですが、誰かチーム組んで参加しませんか。
(by tanzakuさん)

せっかくの機会で是非参加したみたかったので、

参加してみたいです！！！
(by tutuz)

…ということで参加が決まりました！

競技のルール

プログラミングコンテストのルールはシンプルです。

• 1チーム3人で参加
• チームで1つの問題に取り組むのではなく、エントリー時に選択した難易度の問題に3人それぞれで挑戦し、チームの合計点を競う
• 問題は「ましゅまろ」「せんべい」「かつおぶし」の3つの難易度の問題が用意されていて、エントリー時に決める
  • ましゅまろが一番易しく、かつおぶしが一番難しい
• チームでの相談はOK ¹
• 合計点が同じ場合は、解答時間の短い方が上位
• 企業の部と学校の部のそれぞれで順位が決まる

チーム編成

• tanzaku
• kou65536
• tutuz

解く問題の難易度については、当時(2018年11月5日)の AtCoder のレートの高い順に、tanzakuさん・kou65536さん・私でしたので、順に難しい問題に取り組むことになりました。

コンテスト当日(By tutuz)

コンテストは13時からでした。私はいつもの通り自宅で精神を整えてからコンテストに参加しました。

私が取り組んだ「ましゅまろ」の問題は、 問目から 問目はすぐに解くことができました。 問目の問題は難しかったです。

以下のような問題でした。

■解説内容
「ましゅまろ　難易度1，2，3，5」から、難易度5「旅」
「せんべい　難易度2，3，4，6」から、難易度4「除去とスコア」
「かつおぶし　難易度3，4，5，6」から、難易度6「リフルシャッフル」

※補足：PG BATTLE受験者様へ
上記解説対象の3問につきましては、問題・模範解答等のコンテンツの他、自らが作成したコードや解法についての見解などを、SNSやブログなどを通じて第三者に開示していただいて問題ございません。

※なお 問目のこの問題はPG Battle 公式サイトに記載がある通り、問題や解法などを開示しても問題ないことが示されています

問題(旅)

町が 個あり、 本の双方向に移動可能な道で結ばれています。
町には から までの番号が、道には から までの番号が付いています。
番目の道は、町 と町 の間を結んでいて、通ると の幸福を得ることができます。
町 と町 を を満たすように選び、同じ町を2回以上訪れないように町 から町 まで移動するとき、得られる幸福の総和の最大値を求めてください。

制約

• 制限実行時間： 秒、制限メモリ使用量： MB

考えていたこと

と は任意に定めることができます。

例として以下のような重み付きグラフを考えます。町がグラフの頂点、道がグラフの辺として任意の 点間の最長パスを求めれば良いです。

この例では頂点 と を選んだときに幸福の総和の最大値が になります。

さて、ナイーブな解法は、訪問する頂点の順番を決め打ちして、順番に試せばよいです。訪問する頂点の順番は 通りあるので全体の計算量は となります。しかし、この計算量では制限実行時間内に問題を解くことができません。

少し考えてtanzakuさんに相談しました！

制約的にはbitDPな気もするんですが、まだ解法わかってないです…
(by tutuz)

(…数分後…)

dp[訪れた都市の集合][今いる都市] := 幸福度のdp
巡回セールスマン問題まんまっぽい気がします
(by tanzakuさん)

確かに…🌄 と思いながらおもむろに実装するもバグがとれず、tanzakuさんに再度相談(というか雑にコードを投げつける)

始点の情報がうまく実装できていないゆえにバグっていると思っているのですが、
どの辺直したら良さそうとかわかりますでしょうか…？
(by tutuz)

// 一部省略してあります
public void solve(int testNumber, InputReader in, PrintWriter out) {

    int n = in.nextInt(), m = in.nextInt();
    int[][] mat = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(mat[i], -1);
    }

    for (int i = 0; i < m; i++) {
        int a = in.nextInt()-1, b = in.nextInt()-1, h = in.nextInt();
        mat[a][b] = h;
        mat[b][a] = h;
    }

    int[][] dp = new int[1 << n][n];
    for (int i = 0; i < 1 << n; i++) {
        Arrays.fill(dp[i], 0);
    }
    dp[0][0] = 0;

    for (int bit = 0; bit < 1 << n; bit++) {
        for (int now = 0; now < n; now++) {
            for (int to = 0; to < n; to++) {
                if ((bit >> to & 1) == 0 && mat[now][to] != -1) {
                    dp[bit | 1 << to][to] = Math.max(dp[bit | 1 << to][to], dp[bit][now] + mat[now][to]);
                }
            }
        }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, dp[(1<<n)-1][i]);
    }
    out.println(max);

}

始点というより、if ((bit >> now & 1) == 1 のチェックが足りないような…
(by tanzakuさん)

またも確かに…🌄 と思いながらこの部分を…

if ((bit >> to & 1) == 0 && mat[now][to] != -1) {
    dp[bit | 1 << to][to] = Math.max(dp[bit | 1 << to][to], dp[bit][now] + mat[now][to]);
}

このように修正しました。

if ((bit >> i & 1) == 1 && (bit >> to & 1) == 0 && mat[now][to] != -1) {
    dp[bit | 1 << to][to] = Math.max(dp[bit | 1 << to][to], dp[bit][now] + mat[now][to]);
}

なんとか制限時間内に修正でき、 問とも提出できました。

コードの完全版はこちらです。
https://gist.github.com/future-tsuji/7e0ae4515616d9d0320666e9482faffc

結果

正解/不正解は 時以降に運営から連絡が来るようなので気長に待ちました。

…

企業の部 チームのうちなんと 位 でした👏👏👏

ちなみにこのコンテストの3位の賞品は

• Amazonギフト券3万円(チームで3万円)
• 超小型PC「Raspberry Pi（ラズパイ）」Pi 3B+ Starter Kit(チームで3台)
• トロフィー

でした。

トロフィーはこんな感じでオフィスに飾ってあります。

tanzakuさん、kou65536さんは賞品でもらった Raspberry Pi を使って、CO2 センサーを開発しているとか 🌿

おわりに

今回はプログラミングコンテストに社内チームで参加した内容を紹介しました。

チームでコンテストに取り組むことができ、面白かったです！

フューチャーアーキテクトには競技プログラミング好きが集まる競技プログラミング部があります。

弊社での競技プログラミング活動に興味を持っていただけた方、ぜひランチ🍝や、カフェでコーヒー☕でも飲みながら話しましょう♫

We are hiring engineers!!

2020年の参戦記録も仁木さんによって公開されています！

• PG BATTLE 2020参戦記 ～チーム結成法、注意点、作戦など～

  ---

  1. 1.HPには明記されていませんが、運営に確認しました。 ↩