C - Synthetic Kadomatsu

atcoder.jp

この問題は個人的に過去のABC-Cでも一二を争う難しさではないかと思いました。一言で言うと「全探索するだけ」なんですが、その全探索の仕方が独特というかいくつかの気づきが必要な問題だと感じました。

まず一つが「延長・短縮・合成の操作の順番を自由に入れ替えても最終的な状態や総コストは変わらない」ということです。延長・短縮の操作が入れ替え可能なのは明らかで、延長と合成も「竹Xを延長した後、竹Yと合成する」としても「竹XとYを合成した後、その竹を延長する」としても一緒だと言うことが分かります。短縮と合成についても同様です。

「操作の順番を好きなように入れ替えられること」を「操作が可換である」と言ったりもします。競プロにおいてはしばしば何か(数列とかグラフとか)に対して操作を繰り返すような問題が出ますが、「与えられた操作が可換であるかどうか?」は常に気を配りたいポイントですね。

そして延長・短縮・合成の中で一番複雑な操作が合成です。操作が可換だと分かったので「合成を先に全てやってしまって、残った竹に延長・短縮をやってA,B,Cを作る」と考えると少し考えやすくなる気がします。(もちろん複雑な操作は最後にまとめてやってしまう、という考え方もあると思いますしその方が考えやすくなる問題もあるかもしれません……その辺はアドホックなのかな、少なくとも今回は合成を先にやってしまう方が楽になりそう、というのは勘みたいなものが働いている気がします)

なのでまず合成を考えることにします。合成の順番も関係無いので、次のような操作に置き換えて考えると分かりやすくなりそうです。

  • 合成: 1本以上の竹を選んで、それらを全て接続した竹を作る。このコストはk本の竹を選んだとすると  10(k-1)

このように考えておくと「合成した竹を合成する」のは一回の合成で置き換えらえることも分かるので、合成した竹を合成するのは考えなくてよくなります。(1本の竹だけ選んだものも合成と呼んでる点に注意です)

次に大事なポイントが「合成した竹を使わないのは明らかに損」ということです。ここでいう「合成した竹を使わない」というのは作りたいA,B,Cのために割り当てない、ということです。これも明らかで使わないんだったら最初から合成しなかったことにしたほうが明らかにコストが小さくなるからです。

これらの考察から合成の仕方として考えるべきは、全ての竹について

  • Aのための合成に使う
  • Bのための合成に使う
  • Cのための合成に使う
  • 何もしない

という4つの場合全てを考えれば十分だということが分かりました。

これで合成に対して考えるべきことは終わりました。後は、

(Aのために使われた竹の長さの総和とAの長さの絶対値) + (Bのために使われた竹の長さの総和とBの長さの絶対値) + (Cのために使われた竹の長さの総和とCの長さの絶対値)

が延長・短縮にかかるコストの最小であることは明らかです。

最後に計算量を考えます。

各竹について選択肢が4つありますから、全ての場合を試すと4^n通りです。指数時間は一般的には遅いと思われていますが、今回の場合ですと n \le 8とかなり小さいので最大ケースでも 4^8 = 2^{16} = 65536通りとなり十分計算可能であることが分かります。

ここまで分かれば解ける人も多いと思いますが「4^nの全探索ってどうやるの?」という人も少なくないと思います。やり方は思いつく限り3通りあって

  1. 深さ優先探索(DFS)
  2. 4進数で全探索
  3. bit全探索(2進数の全探索)でゴリ押し

です。オススメ順に並べてみました。

深さ優先探索

一番素直だと思うのがこのDFSによる解法です。今回のような各点での枝分かれがk本みたいな状況に限らず、もう少し複雑な枝分かれをする場合にも応用が効きます。放送でchokudaiさんも言っていましたが汎用性がかなり高いのでスラっと書けるようになっておくとよいです。

部分的なコードは以下のような形です。

// idx は今見ている竹の番号、 gc はこれまで合成に使った竹の本数
int dfs(int idx, int la, int lb, int lc, int gc) {
    if (idx == n) {
        if (la == 0 || lb == 0 || lc == 0) {
            // A, B, Cの合成の竹に使われた竹が存在しないときは有効な回答ではない
            // このときは答えに影響が起きないような十分大きな値を返すことにする
            return inf3;
        }
        else {
            return abs(la - a) + abs(lb - b) + abs(lc - c) + 10 * (gc - 3);
        }
    }
    int res = inf3;
    // idx番目の竹を A のための合成に使う場合
    res = min(res, dfs(idx + 1, la + l[idx], lb, lc, gc + 1));
    // idx番目の竹を B のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb + l[idx], lc, gc + 1));
    // idx番目の竹を C のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb, lc + l[idx], gc + 1));
    // idx番目の竹は使わない場合
    res = min(res, dfs(idx + 1, la, lb, lc, gc));
    return res;
}

4進数で全探索

次に4進数による全探索です。こちらはややテクニカルな印象がありますが、dfsのような関数を書かずforループを回すだけでさくっと書けるのがポイントでしょうか。bit全探索を知っている方はこちらの解法を思いつきやすい気がします。

以下のコードでは(0 -> 使わない、 1 -> Aに使う、 2 -> Bに使う、 3 -> Cに使う)と対応付けています。その他の部分はdfsによる解法と大きな違いは無いです。

int ans = inf3;

foreach (s ; 0 .. 4^^n) {
    int la, lb, lc;
    int gc;

    foreach (i ; 0 .. n) {
        if (s % 4 == 1) {
            la += l[i];
            gc++
        }
        else if (s % 4 == 2) {
            lb += l[i];
            gc++
        }
        else if (s % 4 == 3) {
            lc += l[i];
            gc++;
        }
        s /= 4;
    }

    if (la == 0 || lb == 0 || lc == 0) continue;
    ans = min(ans, abs(la - a) + abs(lb - b) + abs(lc - c) + 10*(gc - 3));
}

bit全探索によるごり押し

上記2つと比較してスマートでもなく自然でもないのであまりオススメできない解法です。それでもなぜ書いたかというと、私がコンテスト中に書いたのがこの方法だったからです……

あまり多くは語らないので雰囲気だけ掴んでもらえたらと思います。 2^{3n}くらいかかってそうでやばくね?って思いますが、よく考えるとs,t,uの各bitが立つ本数が高々1本しかないので実は 4^nに収まっているという奴です(多分)

(2019.02.26 追記) と思ったんですが4^nに収まっているというのは嘘な気がしてきたのでやっぱり参考にしないでください

long ans = inf6;

foreach (s ; 1 .. 1 << n) {
    long tmp;

    int la;
    foreach (j ; 0 .. n) {
        if (s & (1 << j)) {
            la += l[j];
            tmp += 10;
        }
    }
    tmp -= 10;

    foreach (t ; 1 .. 1 << n) {
        auto ttmp = tmp;
        int lb;
        if (s & t) continue;
        foreach (k ; 0 .. n) {
            if (t & (1 << k)) {
                lb += l[k];
                ttmp += 10;
            }
        }
        ttmp -= 10;

        foreach (u ; 1 .. 1 << n) {
            if ((s | t) & u) continue;
            auto tttmp = ttmp;
            int lc;
            foreach (e ; 0 .. n) {
                if (u & (1 << e)) {
                    lc += l[e];
                    tttmp += 10;
                }
            }
            tttmp -= 10;
            tttmp += abs(la - a) + abs(lb - b) + abs(lc - c);
            ans = min(ans, tttmp);
        }
    }
}

おわりに

分かっているように書きましたが、実際コンテスト中は難しすぎてテンパってしまい、いろいろと最悪でした。一番下のコードになった理由も「合成する竹としない竹で分ければいいのか」→「いや、A,B,Cの3つに分ければいいのか」→「いや、使わなくていい竹もあるんじゃん」となってネストがどんどん深くなってしまったからです(しかも計算量は何となく大丈夫でしょみたいな感じで本当に適当だった)

いろいろと反省すべき点が多いコンテストでした。ABC-Cでも難しく感じたら焦らずに、考察はじっくりやらないとダメですね。

No.794 チーム戦

概要

N 人(偶数)の人がいて、i 番目の人は整数 A_i を持っている。これらの人々を使ってペアを N / 2 組作りたい。ただし、各ペア(i, j)について A_i + A_j <= K が成り立っていないといけない。

そのようなペアの分け方は全部で何通りあるか?

制約

  •  2 \le N \le 2 \cdot 10^5,  Nは偶数
  •  1 \le K \le 2 \cdot 10^9
  •  1\le A_i \le 10^9

考察

まず人の順番は無視していいので、A_iは昇順にソートしておくことにする。すなわちA_1 \le A_2 \le \dots \le A_Nが成り立っているものとする。

「2人の和がK以下」という制約が無ければ簡単で、答えは

 \binom{N}{2} \cdot \binom{N-2}{2}  \dots  \binom{2}{2} / (N / 2)!

となる。最後に(N / 2)!で割らなければいけないことに注意する。なぜなら、例えば[1,2,3,4,5,6]とあるとき、({1,2}, {3,4}, {5,6}), ({1,2}, {5,6}, {3,4}), ({3,4}, {1,2}, {5,6})...のように同じ分け方でも順序が違うものを重複して数えてしまうからだ。

上の考察は無駄ではなくてKが十分大きいときはこの答えがそのまま使える。より厳密に言うと、 A_{N-1} + A_{N} \le Kであるとき上の答えに帰着される。

こういうのは相方の候補数が少ないもの、つまりA_iが大きい順に考えてその候補数を掛け算していけばよさそうな感じがする。A_iの相方の集合よりA_{i-1}の相方の集合のほうが大きいので、A_iがどれを相方にしても、A_{i-1}の相方候補は1つ減るだけだから。(これを逆順にやってしまうとややこしくなってしまう……ということをABC114-Dで学んだ)

そうやりたいんだけど、問題はA_iA_{i-1}をペアにした場合とかを考えると、次にA_{i-1}を考えるのではなくA_{i-2}を考えなければいけない、みたいになってかなりややこしくなってしまう。どうすればいいんだろう……?

よく考えると A_iA_{i-1}とペアになれるっていうことは、 A_i + A_{i-1} \le Kが成り立っているということで、これは上の「制約が無いパターン」に帰着されていることが分かる。すなわち、 A_i + A_{i-1} \le Kが成り立っているときは、前のi人は自由にペアを組めるのだ。

なので、 A_i + A_{i - 1} \le Kがどこまで成り立つか?でグループ分けすると考えやすくなるのではないか、という考えが浮かぶ。すなわち A_i + A_{i - 1} \le Kを満たす最大の iをmとして、前半組m人、後半組N - m人と分けてみよう。すると前半組のm人はどの2人を選んでもペアに出来るし、後半組のN-m人はどの2人を選んでも絶対にペアに出来ないことが分かる。ということは後半組は相方を前半組から取ってこなければいけない、ということも分かる。

ここまで来ると最初の懸念であった「A_iA_{i-1}をペアにした場合とかを考えるとめんどくさい」という問題も解消されることが分かる。なぜなら後半組は絶対に前半組から相方を取ってくるので、後半組同士でペアになることは一切考えなくていいからだ。

これをアルゴリズムとして落とし込むと以下のようになる。

  1. ans = 1 とする
  2. 後半組の大きい順に、( K - A_i以下を満たす人の数) - (既に処理した後半組の人の数) をansにかけていく
  3. 後半組が全て処理できたら、前半組で残ったm - (N - m) = 2m - N人は自由にペアに出来るので制約条件の無い問題に帰着して、それをansにかける

実際はans = 0になる場合とかがあるのでその場合は少し修正しなければいけないけど、だいたいこんな感じ

感想

解説と少し違ったやり方で解いたので書きましたが、kmjpさんのやり方とほぼ一緒ですね。少し違うのはkmjpさんは A_i \le K / 2でグループ分けしてますね。確かにそっちのほうがシンプルだなあと思いました。

競技プログラミング初めて2年経ちました

去年も書いたので今年も書きます。2年間の振り返りとか今年の抱負とか書いています。

AtCoderのレート推移

f:id:nanae1914:20190122191522p:plain
AtCoderのレート推移

初めてAtCoderに参加したのが2017/01/07のABC051ですね。当時は愚直に全探索をするという思考が身についてなくてB問題のO(N^2)の全探索が書けなくて苦戦したこととか、D問題の解説を聞いてワーシャルフロイドというアルゴリズムを知り、なんじゃそりゃって思ったこととかを覚えています。解説放送といえばりんごさんですが、当時はりんごさんが不在でちょくだいさんが解説していました。ワーシャルフロイドの原理が分からね~みたいなコメントがあって、ちょくだいさんが頑張って分かりやすく解説してくれようとしていたんですが、当時はよく分からなかったです。今は何となく分かります、あれは(経由地点に0 ~ kまで使えるときの最短距離)みたいなDPをやっているってことなんですね(おそらく)。

それからこどふぉとかにも参加しながら楽しくやっていて、水色は割とすぐでした。そこからなかなかレートが上がらなくなって青色になるにはちゃんと勉強しなきゃいけなさそうだということで、青色を目指しました。青色になったら「競プロ経験者です」という格好がつくかなとか考えていました。いわゆる螺旋本を買って読んだり(蟻本は難しいと聞いていたので)、こどふぉに出まくったりしていました。こどふぉの規模とか深夜特有のアングラ感(?)とか結構好きなんですが最近は全然出ていません……やはり健康的な生活を犠牲にするのはデメリットが大きいです。

印象深い出来事としては「日本橋ハーフマラソン」というマラソン系のコンテスト予選を通って、本戦のオンサイトに行けたことですね。まだ競プロ始めて3カ月とかだったので今思うと奇跡的な気がします……このことで「もしかしてマラソン得意なのかなあ」とかちょっと勘違いしたのですが、そんなことは無いですね。

あと、振り返ってみてよかったなあと思ったのはJOIの過去問を解いたことですね。JOIの過去問はDPを使う問題が多くて、かつAtCoderに出すには典型すぎて出せない(多分)ものも出るので、そういう問題でDPに対する感覚を養うことが出来たのが結構良かったと思います。PythonからD言語に乗り換えたのもちょうどそのときですね。JOIの過去問はTLEとMLEがかなりきつくてPythonでやるのは不可能だったんですね。それでD言語を本格的に乗り換えました。

そして実際に青になれたのが2017/07/23、競プロ始めてから8カ月、rated24回目のAGC018みたいですね。あんまり覚えていませんが、Bの700点までを50分ちょいで通して(Aに20分かかっているのでBは実質30分程度?)黄色パフォが出たようです。今見てみると確かにB問題難しいです……全然分かりません。一時間くらいかけてやっと分かりました。確かに好調だったようです。

しかし当時は青になれたもののあまり実感が無かったです。こんなんで青になれていいのか、とかまぐれかなあとか思っていました。そんな感じで一旦9~11月あたりに間が空いて(競プロに飽きて別のことをやっていた)また復帰して、水色に落ちたり戻ったりしてますね。やっぱり当時は安定した青レベルの実力が無かったのだと思います。

そして2018年一発目のコンテストでぴったり青に戻るんですね。そっから低空飛行を続けるものの、結局2018年は青から一回も落ちてないですね。「レート上がらなくてもいいから、青は維持し続けたいな」と思っていたのでそこは良かったです。でも2018年は振り返ってみても、あまり書くことがないです。というのもコンテストは毎週出るようにはしていましたが、精進らしい精進もしていなかったので……それでもレートは少し上がってるので不思議ですね。2017年の貯金のおかげでしょうか。

レートに関して、今年は明確な目標を立てようと思います。理想は2000(=黄色)ですが、正直黄色になれるビジョンがちょっと見えません。最近黄色パフォも全然出せてないし、黄色になるなら橙に近いパフォをたまに出せなきゃいけないと思うんですが、それは一回も出せていません。なので1900にしておきます。この辺がギリギリ頑張れば達成できそうなラインな気がします。

TiddlyWikiのすすめ

みなさん、コンテスト後の復習メモツールみたいなのって何使ってますか?

ローカルにメモ帳で書くとか、ブログに解説記事を投稿するとか、最近だとScrapboxっていう良さそうなのを使ってる人もいるみたいですね。

私はTiddlyWikiというものを使っています。

tiddlywiki.com

選んだ理由は

  • ネットが繋がってなくても使える
  • ブラウザ上で起動できる
  • 軽い
  • texで数式が書ける
  • タグ付けが出来るので整理しやすい

あたりですかね。デメリットは記法がmarkdownとかとちょっと違うのでアドホックなことと、書いたものをそのままネット上に公開することは出来ないというところです。

結構オススメなのでよければ使ってみてください。

競プロSlack

今年は本格的に競プロ強くなりたいと(今のところ)思っているので、中級者競プロSlackに入ることにしました。結構議論が行われていて赤の人もいたりしてよさそうです。積極的にかかわっていけたらなって思ってます。

作問

今年はyukicoderでいくつか問題出したいです。多分★2以下の問題になると思います。そろそろ★3の問題とかも作れるようになりたいですが、実力的になかなか難しいですね。

まとめ

  • 今年はレート1900を目指します
  • コンテストの振り返りにTiddlyWikiがおすすめです
  • 競プロSlackにも積極的に参加したいです
  • yukicoderで出題したいです