GCJ2016 Round1B C.Technobabble

問題

N個の単語ペアが与えられる。ペアは前側と後ろ側の単語と区別する。
これは、N人が順番に、前側、後ろ側どちらかがそれまでその側で使われていない新しい単語を使って作られるようにしたはずのものである。
しかし、fakerと呼ばれる人はそれまで出てた単語を組み合わせて単語ペアを作ってしまっていた。
最大でfakerは何人いたと考えられるか？

small: 1<=N<=16
large: 1<=N<=1000

考え方

smallは、fakerかどうかをbitで表し、2^16試す。fakerじゃない＆faker条件を満たす集合かどうかを確認して、満たす場合の最大faker数を返す。


largeは、使うすべての単語を最小のペア数で抑えたとき、fakerじゃない集合(ちゃんと新しい単語で作った人)の数になるので、「N-(使うすべての単語をカバーできる最小のペア数)」が答えになっている。
(これは、2部グラフの頂点被覆最小辺カバー問題になっている。)


まず、前側、後ろ側で頂点が1度だけ使われるように辺を選びたいので、最大マッチングを取る。
このとき、マッチングに選ばれなかった頂点があるはずだが、これは新しい単語を使ったものなので、fakerにはなりえない。
したがって、「最大マッチング数＋最大マッチングで選ばれなかった頂点数」が「使うすべての単語をカバーできる最小のペア数」となる。
(「最大マッチング数+最小辺カバー数=頂点数」という性質を使えば、「最小辺カバー数=頂点数-最大マッチング数=左右の単語数合計-最大マッチング数」でも求められる。Nから個最小辺カバー数を引けば答え)

SRM669 div1 250

とぷこだ

解答に必要なことを一つも考えつけてなかったorz
最適分割の部分の理解が怪しいが、理解したと思う範囲でまとめておく。

問題

体積Sのスライムがある。
1回の操作で、今あるスライムの塊を一つ選んで、2つに分解することができる。
このとき、体積Aのスライムを体積aと体積bに分解した場合、a*b点もらえる。(a,bは整数でなければいけない)
得点がM点になるために必要な操作の最低回数は何回か？

2<=S<=1000
1<=M<=10^9

考え方

「できるだけ大きい者同士を掛け合わせるほうが大きい得点が得られる」ことから、今あるスライムの中で一番大きい体積のものをできるだけ半分に分けていく、という方針が考えられるが、これは嘘解放。
例として、S=6の時、{6}->{4,2}->{2,2,2}と分解した場合、2回で12点が得られる。
これは、最初は得点が小さくても後で高得点が得られそうという可能性と、小さい数での総当たり実験で見つけられる。(そもそも上の方針だと証明できない)


S=6の場合で考えると、M=9なら{6}->{3,3}が選ばれるべきだし、M=12なら{6}->{4,2}->{2,2,2}が選ばれるべきで、「どのように分解するか？」をトップダウンに考えると、総得点Mによって選択が変わってしまう。全探索やDPとかで求めようとすると、状態数が多すぎて難しい。


そこで、二分探索+greedy的に考えてみる。
もし、K回分解すると仮定すると、M点以上得られるか調べて、一番小さいKを返せばよくなる。
(KはS-1回まで調べればよいので、二分探索でなくてもよい)


K回分解でM点以上得られるか？を考える。
K回分解するということが分かった場合に使える条件としては、「最終的に(K+1)要素に分解される」ことがある。
しかし、これでも、トップダウンに分解する方向で得られる得点を考えるのは難しいので、ボトムアップに考える。
ボトムアップ的に、結合する方向に得点を求めていってもトップダウンに計算する得点と同じになることがわかれば、次に進める。


以下、要素がa,b,c,dの4つに分解されたとして考える。
結合の仕方を変えて得点を計算してみると、
ab+cd+(a+b)(c+d) : {a,b,c,d}->{ab,c,d}->{ab,cd}->{abcd}
ab+(a+b)c+(a+b+c)d : {a,b,c,d}->{ab,c,d}->{abc,d}->{abcd}
cd+(c+d)b+(c+d+b)a : {a,b,c,d}->{a,b,cd}->{a,bcd}->{abcd}
= ab+ac+ad+bc+bd+cd　・・・①
と、結合の仕方によらず、同じ得点が得られることがわかる。


次に、このスコア①が得られる最大値を考える。
各要素は0より大きいので、、相加相乗平均の関係式から「(a+b)/2>=(a*b)^(1/2)」<=>「(a+b)^2/4>=a*b」であることを使って、
① <= (a+b)^2/4 + (a+c)^2/4 + (a+d)^2/4 + ・・・ + (c+d)^2/4
で、等号はa=b,a=c,a=d,b=c,b=d,c=d、すなわち、a=b=c=dの場合に成り立つ。
ただ、a,b,c,dは整数なので、できるだけ均等になるように用意すればよい。


したがって、「K回分解する場合に得られる得点」は、Sをできるだけ均等にK+1個に分解した場合の①の計算を行えば得られる。


また、①はそのまま計算しようとすると、O(K^2)だが、「1/2ΣAi*(S-Ai)」とも書け、O(K)で求められる。

他の方の分かりやすい解説

Codeforces 582A. GCD Table

こどふぉす

問題

ある長さNの配列a_iがあったとき、この配列自体は与えられず、代わりにgcd(a_i,a_j)の結果N*N個が与えられる。
元の配列に含まれる数値を答える。


1<=N<=500
a_i<=10^9

考え方

与えられたgcd(a_i,a_j)の中で、一番大きい数をMとする。
gcd(M,M)=Mであるので、少なくとも、Mは1つは含まれる。
なので、gcd(a_i,a_j)からMを1つ取り除いておく。


次に、gcd(a_i,a_j)の中で一番大きい数をM2とする。
最初の配列にM2が含まれないとすると、他の要素でgcd取ったらM2になるものがあるはずだが、gcdの性質から、M2より大きい数値でないといけない。しかし、今の最大値はM2であるので、ありえない。
したがって、M2も含まれないといけない。なので、gcd(M2,M2)はのぞかれる。そして、これまで確定しているMに対して、gcd(M,M2)とgcd(M2,M)の分も確定するので、のぞいておく。


これを繰り返せば、矛盾なく、元の配列の要素を復元できる。

CODE FESTIVAL 予選A D.壊れた電車

その他

問題

N車両の電車をM人で点検する。最初、i番目の人はXi車両目にいる。
点検には時間がかからないが、隣の車両への移動には1分かかる。
すべての車両を少なくとも1人が点検した状態にするのにかかる時間は最低何分か？


1<=N<=10^9
1<=M<=10^5, M<=N

考え方

Nが大きいので、車両の状態を配列とかに持ってループを回すのは無理。


各人がどの範囲を点検するかを考えると、一番左にいる人は左側に車両があるなら、そこを点検しないといけない。二番目に左にいる人は一番左の人が点検していないところから点検しないといけない。と、貪欲に決められる。
点検に使える時間tが決まれば、上記のように貪欲に決めていけるので、二分探索で、時間を求めればよい。


ただし、点検する範囲は、左側は「一つ左の人の点検しなかったところ」から点検しないといけないが、右側はどこまで点検できるかというと、、サンプルにある通り、「左に行ってから右に行けるだけ行く」場合と「右に行ってから左に行く」場合があって、そのどちらかできるだけ右側まで点検できる方法で点検する必要がある。
「右に行ってから左に行く」場合は、どこまで左に行けるかというと、(t-(Xi-{左の人が点検していない車両}))/2までなら右に行ってから左の点検していないところまでたどり着ける。

ABC029 D. 1

その他

問題

1からNまでの数字をすべて書き出したとき、「1」は何回書いたか？


1<=N<10^9

考え方

愚直に数えると、O(N*桁数)かかってしまって間に合わない。
以下、1からではなく、0から考えても問題ない。

桁DP

最大桁から考える。
ここで、Nが3桁「xyz」であると仮定する。
100の位は0〜xまであり得るが、0〜x-1までは、10の位以下は00〜99までの1の出現数、xの場合は00〜yzまでの出現数を使ってDPで求められる。

出現パターン

1の位は01234567890123456・・・を繰り返しており、10の位は00000000001111111111・・・・というパターンを繰り返している。
1の出る回数はそれぞれの桁でO(1)で求められるので、全体でO(桁数)しかかからない。

Codeforces 580D. Kefa and Diches

こどふぉす

問題

N種の料理からM種を順番に選んで食べる。
このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。
満足度の最大値を求める。


1<=m<=n<=18
0<=k<=n*(n-1)
0<=満足度<=10^9

考え方

N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わない。
選ばれたM種から最大となるような順序を効率的に求めることを考える。


これは、今まで食べた料理の情報と最後に食べた料理のbitDPで考えられるので、
dp[今まで食べた料理][最後に食べた料理]:=満足度の最大値
で更新すればよい。


さらに、NからMを選ぶ組み合わせとbitDPを分けて考える必要はなく、全部の料理でのbitDPでM個以下のものだけを使えばよいので、O(2^18 * 18 * 18)で済む。