目次

AtCoder Beginner Contest 226 F,G,H 問題メモ

AtCoder Beginner Contest 226

PythonistaはさぞかしA問題でWAした人が多いことでしょう。
偶数丸め、忘れがち。

F - Score of Permutations

F - Score of Permutations

問題

解法

K 乗させることの意味をいまいちわかってない……
と思ったら、入力が N だけだと手元で時間かけて計算して埋め込めるからか、なるほど。

言い換えとDP定義

このように順列を ipi に置換していく問題は過去に何度も出ているが、 ipippi...i と追っていき i に戻るまでを1つのサイクルとすると、 順列はいくつかのサイクルに分割できる(長さ1もサイクルとする)。

1つのサイクルだけを見ると、それが何回ごとに元に戻るかの周期は、サイクルの長さと一致する。

よって P を固定した時、P が長さ L1,L2,... のサイクルから成っていたとして、 スコアは Li 全体の最小公倍数となる。

スコアが x となる P の個数を x ごとに数えられたら、答えは求められる。

DP[i][j] から新たに長さ l のサイクルを追加すると、DP[i+l][LCM(j,l)] に遷移することになる。

DP遷移

重複して数えないように注意が必要。たとえば

前者で (1,3,4),(2,5)、後者で (2,5),(1,3,4) をそれぞれ別に数えてしまうと、重複してしまう。

このような場合、 「新しく追加するサイクルには、残っている中で番号が最小のものは必ず入れる」 と考えると重複を除いて数えられる。

よって、DP[i][j] から長さ l のサイクルを追加する遷移は以下のようになる。

j の取り得る値の種類数(総和が N 以下の複数の値のLCMとなりうる数)を T として、O(N2T) で全てを計算できる。

T のオーダー計算がちょっと難しいが、 N=50 で試しに実行しても1056程度であることが確認でき、十分高速であることがわかる。

全て計算できたら、各 j につき、DP[N][j]×jK の総和が答え。

Python3

G - The baggage

G - The baggage

Gだからそこまでたどり着かなかったり変に難しく考えた人が多いだけで、DとかEに置かれてたらそこそこ(未証明を含め)解かれてそうな気がする?

問題

解法

重さの合計を WA,WB として、WA>WB は問題外として、 WAWB でも不可能なケースがある。

重さ 2 の荷物が 5 個
体力 3 の 人 が 4 人  答えはNo

重さ 4 の荷物が 1 個
体力 3 の 人 が 9 個  答えはNo

貪欲に決められないか考える。

なるべく持てる人が限られる重い荷物から決めていきたい。
また、人は、体力の端数が出ないならばなるべく重い荷物を優先的に持った方がよい。

重さ i の荷物はまず体力 i の人に持たせて損しない。
「荷物 i を持っていない体力 i の人(A)がいるのに、i 以外の体力で荷物 i を持っている人(B)がいる」状態で成立している場合、 (A)の持つ全荷物を(B)の荷物 i と交換しても成立は保たれる。

従って、15 について荷物と人のどちらか一方は相殺して0にでき、どちらかが余っている状態になる。

ここからは重い方の荷物の割り当てから考えていく。どこかのタイミングで、その荷物を持てる人がいなくなればアウト。

重さ5の荷物が余っていたら不可能。

重さ4の荷物が余っていたら、体力5の人がそれ以上余っていれば持たせられる。
荷物を持った人は、以降体力1として扱う。

ここまでは、そうするしか方法が無い。

重さ3の荷物が余っていたら、体力5か4の人に持たせられ、選択の余地が生まれる。
ここで、どちらに持たせるべきか? 貪欲に判定可能か?

残る荷物の重さは 1 と 2 である。

1は最小単位なので、どのように体力を残しても総和が足りていれば持たせられる。
総和が足りていてもアウトになるのは、重さ2の荷物が残るのに、(残り)体力1の人しかいなくなった状態である。

奇数である1,5を多く残した場合、その分だけ端数(残り体力が1となる人)が発生しうる。 しかし、偶数の2,4を多く残せば、端数を最小限に抑えられる。

重さ3の荷物をどちらに優先的に持たせても残る体力の総和は変わらないので、体力 2,4 が多く残るようにした方がよいことがわかる。

実装上は、まずは同じ重さでマッチングした後、 「重さの大きい方の荷物から順に」「体力の大きい方の人から順に」割り当てていけばよい。

これは全体が 15 だから成立するのであって、6 以上では成立しない点に注意。
(その場合はフローで解ける?)

Python3

H - Random Kth Max

H - Random Kth Max

問題

解法

[0,2][1,3] など、区間がズレながら入り交じるとややこしい。

幸い、入力は全て整数で、またその範囲も上限 100 と小さいので、 「K 番目に大きい数が [x,x+1) に入る確率を計算して、そこから期待値を x ごとに計算」という手法を採れる。

これなら仮に [x,x+1) の中に複数の変数が入るとしても、全ての変数はその区間をフルに動くので、区別せず扱える。

さて、ここで重要な事実として、以下がある。

たとえば n=6 なら、小さい方から期待値は順番に 1767 となる。
証明は、なんか累積確率分布を積分してごにょごにょやるとそうなるらしい。

従って、[x,x+1) に何個の変数があるかで期待値が変わってくる。
さらに [x,x+1)K 番目があるかどうかを判断するには x+1 以上の変数の個数も必要なため、以下の情報を持ったDPが考えられる。

怒濤の4重ループだが、O(RmaxN3)107 程度なので、 まぁPythonは厳しいかもだがPyPyやNumbaを使えば大丈夫。

実際は、x については他の x1x+1 に干渉することはないので x=0,1,2,... と最初に決め打つことを Rmax 回やればよいし、 i も直前 i1 の情報があればよくinplaceに更新できるので、 実装上は j,k の二次元配列でよい。

i=N まで埋め終わった後、[x,x+1)K 番目が入る(k<Kj+k となる)j,k の組について、以下を求めて足し合わせれば答えとなる。

DPの遷移は、[Li,Ri] の確率変数を加えるとき、 (便宜的に i の次元を補って説明する)

このようになる。

Python3