ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 127 E - Cell Distance

E - Cell Distance

解法

この問題は結構考察ステップが多いです。順番に考えていきましょう。

数え上げの順番を変える

まず考えることは「数え上げの順番を変える」ことです。抽象的な書き方ですが、これが具体的にどういうことか説明します。

問題文では以下のことが問われていますね。

  • 駒の全ての配置に対して以下を求め、合計する。
    • その配置における駒2つのペア全通りを考えて、そのマンハッタン距離を合計したもの。

処理イメージとしては以下のような感じです。(文法とかはあまり深く気にしないでください)

for(haichi in all_haichi){
    for(pair in all_pairs(haichi)){
        ans += kyori(pair);
    }
}

これはとても考えにくいです。というのも、ループの外側で回っている通り数が膨大にあるからです。

ということで考え方を変えましょう。for文の順番を逆にします。

  • マス2つのペア全通りに対して、以下を合計する。
    • そのマスに駒が置いてあるような駒の配置の通り数と、マス間のマンハッタン距離の積。

処理イメージはこんな感じになります。

for(pair in all_possible_pairs){
    haichi_num = calc_num_of_haichi(pair);
    ans += kyori(pair) * haichi_num;
}

これだと多少は考えやすくなります。マスの数を  A = NM と置くと、マス2つのペアとしてあり得るのは  \frac{A(A-1)}{2} 通りです。これでもまだ間に合いませんが、先ほどと比べると何とかなりそうに思えます。

ここで「あるマス2つに駒が置いてあるような駒の配置の通り数」を計算してみましょう。これはその2マスがどこであっても、残りのマス  A-2 個に残りの駒  K-2 個を置く場合の数になります。そのため通り数は  _{A-2}C_{K-2} となります。(問題文の最後に書いてあるように、駒同士は区別しないことに注意してください)

そのため結局求める値は、

  • マス2つのペア全通りについてそのマンハッタン距離を合計して、最後に  _{A-2}C_{K-2} を掛けたもの。

として求めることができます。かなり見通しが良くなりました。

縦横の分離

次に考えるべきは縦横の分離です。求めたいのはマンハッタン距離の総和であり、縦の距離と横の距離を別々に計算して足しても同じ結果が得られます。

以降は縦の距離だけについて考えていきます。横の距離は以降の計算を、  N M を入れ替えて行えばよいです。

距離を固定して計算

ここからの計算量削減の考え方はいくつかありますが、公式解説に準拠しましょう。

2マス間の縦の距離を、ある値  d に固定します。距離0は計算に入れなくて良いので  1 \le d \le N-1 とします。そして、「縦の距離が  d になるようなペアの通り数」を求めます。

このとき以下の図のように、2つの縦座標の選び方は  N-d 通りあります。そしてそれぞれに対して横座標が  M 通りあるので、ペアの通り数は  (N-d)M^{2} あります。

f:id:betrue12:20190526155257p:plain

つまり「マス2つのペア全通りについてマンハッタン距離(の縦だけ)を合計した値」は

 \displaystyle \sum_{d=1}^{N-1} d(N-d)M^{2}

で求められることが分かります。

あとはこれを横についても求めて足し、最後に  _{A-2}C_{K-2} を掛ければ答えになります。

ACコード

Submission #5627987 - AtCoder Beginner Contest 127

さいごに

ここまで見てきたように、この問題は考察ステップが多く難しめです。しかしこの「数え上げの順番を変える」というテクニックは、数え上げ問題を攻略していく上では欠かせない超重要テクニックになります。

イメージとしては「for文の順番を入れ替える」、もしくは「縦に見るものを横に見る」というのも良い表現だと思います。この感覚を身に着けて、直接数えにくいなと思ったときに「順番を入れ替えたら楽になったり、二項係数などでまとめて計算できないだろうか?」と目を付けることができたら、難しめの数え上げ問題でも糸口が掴めるようになります。

その意味でも、新ABCとしてとても良い問題だったんじゃないかなと個人的には思います。