Mujin Programming Challenge 2018 F - チーム分け(600)

• 問題

解法

良解説を聞くのが良い

• とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく
• 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理
• 視点を変えて,人数がk人であるようなグループを全て作っていく,というようなことを考える
• 昇順にやっていこうとすると,2人組を作るときにaの値が(2,3)をペアにするのと(2,4)をペアにするのは区別しないといけない
• 降順を考えると,x人のグループを作ろうとしているときにa_i>=xであるようなa_iは区別しなくていいことに気づけたら勝ち

def.
dp[i][j] := (i人以上のチームをすでに作っていて, i人チームを作るときに自由に使える人がj人残っている)
初期.
dp[N+1][0] = 1
遷移.
解説の通り
ans.
dp[1][0]

メモ

これむずいけど好き.
制約はゆるい方から決めて行った方がいいのかな

コード

ARC 103 D - Robot Arms (600)

• 問題

解法

sample2をじっと見ると,必要条件として

• X_i, Y_i の和のパリティが全て一致する

というのがあることがわかる
パリティに注目するのはよくやるのでこれは気づかないとどうにもならない.

実際に,そのときdとして1を20個/21個用意すれば300点は取れる.
(例えば (-3,2) のとき LLLUU(UD)*8 )

このような構築ゲーで2冪に注目するのが定跡なことを念頭に置いて,
アームを 2⁰ , 2¹, 2² , ..と増やしていくことにしよう.
すると 2^k まで使ったときに, abs(x) + abs(y) <= 2^k+1 - 1 のひし形内の和が奇数の点を全て取れることがわかる.
abs(x),abs(y) < 2³⁰ - 1 だから, abs(x) + abs(y) < 2³¹ - 2 で k = 30としてやれば十分.
和がevenの時は 2⁰, 2⁰, 2¹, .. , 2³⁰ とすれば良い.
このようにすれば必ず構築できることもわかったので,列挙した必要条件が必要十分条件だったこともわかった.(よくあるパターン)

実際の構築に関しては 2^k のkが大きい方から決めていき,
abs(x+dx) + abs(y+dy) が0に近くなるようにしてやれば良い
そうしていけば最終的に(0,0)に一致することは上で確かめられている.

メモ

2冪は頭にあったけど実際に書いて見なかったのがよくなかった.

コード

ARC 103 E - Tr/ee (700)

• 問題

解法

まず十分条件を列挙していく.
0-indexedとして,

• s[0] = 1
• s[N-1] = 1
• s[i] = s[N-1-i]

D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン.

s = "100..01.." として,k番目に初めて1が現れるとする.
このとき,1つの辺を切断することで現れる高さ2の部分木は,k-1個の子をもつものしか作れないことがわかる.
これをどんどんやっていくと,
k-1番目までで x_1 = 1, x_2, x_3, .. (1<=a_i<=k-1) の子が作れるとして,
次に1がk番目に現れたとする. このとき,
k-1 = a_1 * x_1 + a_2 * x_2 + .. とx_iの線形和でノードがk個(子要素がk-1個)の木を作ってやることが必要になる.
一瞬DPをしたくなるが, よく見れば a_1 = k-1, a_2 = a_3 = .. = 0 としてやって 1の子要素で数を合わせれば良いことがわかる.
実際そうすれば解説動画のように必ずその木が作れることがわかり, 列挙した必要条件が必要十分条件であることもわかる.

メモ

閃きゲーかと思ったけど,実際に考察ができて見るとただの論理的帰着な気もする..
構築ゲーに関しては最小単位で数合わせ+2冪を考えてみるのがテンプレかな.
今回からけんちょんさんのブログの書き方(タグ付けとか)がわかりやすいので真似していくことにした.

コード

CODE FESTIVAL 2018 qual A C - 半分

• 問題

解法

関連した以下のような簡単な問題について考える.

• n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか.

これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける)
def : dp[i][j] := ( 前からi個取った数列 {a_0, .., a(i-1)} に対して j 回 操作を行った時のできる数列の数 )
初期化 : dp[0][0] = 1 , dp[0][k] = 0 (k>0)
漸化式 : dp[i+1][j] = sum(0<= k <= j)( dp[i][j] )

これに沿ってこの問題を考えてみると,以下のようになる

• 数列の各要素に対して以下の操作を合計K回行う. 数列は何通りできるか
• 操作は cnt_i = floor( log2( a_i) ) + 1 として, cnt回行うまでは毎回違う数に変化し, cnt回以降はずっと0.

この問題に対して先ほどと同じDPは使えない.
なぜなら a_i に対して cnt_i 回操作を行った場合とそれより多く操作を行った場合を複数回数え上げてしまうため.
なので, disjointに数え上げるために以下の制約を付け加える.

• a_i に対しては cnt_i 回までしか操作を行えないとする

この制約を付け加えた時点で,求める答えが変化することに注意する.

• 元々条件での答え
• : 合計K回操作を行った数列の数
• 制約を加えた時の答え
• : 合計K回操作を行った or 何回操作をやったかに関わらず1つでも0を含む数列の数 制約を加える前は 0 ができたら何回でも操作を稼げたが,制約でそれができなくなったからである.

またK<=10⁹だが, A_i <= 10¹⁸ < 2⁶⁰ より cnt_i < 60.
つまり 操作は 数列全体に対して 60N回もできないので K = min(K,60N) とすれば良い.

答えを数えるために,以下のようにおく.
dp1[i][j] := ({a_0, .. ,a(i-1)} が0を含まず,j回操作を行った時の組み合わせ)
dp2[i][j] := ({a_0, .. ,a(i-1)} が0を含み,j回操作を行った時の組み合わせ)

この時, a_i にk回操作をすると考えると漸化式が立てられる.
dp1[i+1][j] = sum(0 <= k < cnt_i ) dp1[i][j-k]
dp2[i+1][j] = sum(0 <= k <= cnt_i )(dp2[i][j-k]) + dp1[i][j-cnt_i]

答えはdp1,dp2が全てdisjointであることを考えれば
dp1[K][N] + sum_( 0<= j <= K ) dp2[i][j]
で求められる.

メモ

まあ解けなかったんだけど

コード

Warshall-Floyd の本質ミス

ミス

o rep(k,N) rep(i,N) rep(j,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);
x rep(i,N) rep(j,N) rep(k,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);

なぜか

Warshall-Floydの証明を考えれば明らか.
証明
Warshall-Floydが何をしているかというと,最初のループがk回終わった時点で, V_k = {0,.. ,k-1} を経由点とする最短路を全て求めている.
これによって帰納法により全点最短経路が求められる.
逆に,そうしなければ正しく最短路が求められない.

メモ

1行で書けるので毎回書いてたけど,間違えて覚えたらしい.
ハマった.

AGC 027 B - Garbage Collector

• 問題

解法

本番中の考察

• 何回原点に戻ってくるかでXの係数が変わるのでこの回数を決めうちして1回O(N)でやったら部分点取れそう
• 部分最適構造( [l,r) 間のごみの最適なとり方が x=l,..,r として [l,x),[x,r) の最適なとり方を各々やってきたうちコスト最小のもの ) ある？

• それがあったら区間DPでO(N²)、RMQで早くしてO(NlogN) とかになるね

• とりあえず実験してみる.
  1回で x_1, x_2, .. ,x_k のごみをとってくるとする.
  比較的明らかに一番最初に x_k まで行って,帰りに全てをとってくるのが最適であることはわかる.
  このコストは 拾って捨てるコストを除くと,
  (行きの分) x_k
  (帰りの分) 2² (x_k - x{k-1} ) + 3² (x{k-1} - x_{k-2} ) + ... + k²(x_2 - x_1) + (k+1)² x_1 となる.

• 部分最適構造はあるか?
  5つのごみを2回で拾ってくるとして,(同じ色のものを同じ回でとってくる)
  (1) x_1 x_2 x_3 x_4 x_5
  (2) x_1 x_2 x_3 x_4 x_5
  のどれが最適か実験してみる.
  (1) = 7x_1 + 5x_2 + 5x_3 + 5x_4 + 5x_5
  (2) = 5x_1 + 5x_2 + 7x_3 + 5x_4 + 5x_5
  x_1 < x_3だから, (1) < (2) となるので, 部分最適構造は成り立たなそうなことがわかる. 多分DPは使えない.
  一方で回数を決めうちした時に, そのごみを何個持った状態で拾うか,というのは
  x_1 x_2 x_3 .. x_5 に対して 回数 m=2 とすると 1 1 2 2 3 を割り振らないといけないことがわかる.
  この時, 大きい数は近いごみに割り振った方が良い(負担が少なくなるので)ことが直感的にわかる(本番中にちゃんとした証明はできなかった)

• 計算
  N=5, m=2とすると,
  行きの分 = x_4 + x_5
  帰りの分
  = 4(x_5 - x_3) + 9(x_3 - x_1) + 16x_1

• 4(x_4 - x_2) + 9x_2
  これは愚直に計算して1つのm当たり O(N) で求められる. よって全体でO(N²)になり部分点が取れる.

また, これを縦に見ていくと和を累積和で計算できることがわかり項数はN/mになるので,
sum_(1<=m<=N) O(N/m) = O(NlogN) となる.

本番中でできなかった部分

x_1 x_2 .. x_k を1回で取ってくるコストは,
1 2 .. k と順番を割り振ることになるので
(行きの分) x_k
(帰りの分) 2² (x_k - x{k-1} ) + 3² (x{k-1} - x{k-2} ) + ... + k²(x_2 - x_1) + (k+1)² x_1 と書いたが,
これはもっと簡潔に書けて, 5x_k + 5x{k-1} + 7x{k-2} + 9x{k-3} + .. + (2k+1)x_1 となる.
( (k'+1)² - k'^2 = 2k'+1 となるので )
これに気づけたら相当早く解けた.

メモ

• 青くなった. やったぜ
• long longでオーバーフローしたので誤差怖かったがdoubleにした.
• そもそもllに入らない答えは出ないと思うので,毎回INF超えないかチェックしてやれば大丈夫そう
• 累積和の計算は場合分けがめんどそうだが,
  rsum := ( [l,r) の和 ) と定義してやって,
  r <= 0 の時 0, l < 0 の時 l = 0, r > N の時 r = Nと定義してやれば簡潔に書けて,凡ミスもしない
  (本番中xとxの累積和を間違ったりして解けなかった(よくやる))

コード

codeFlyer 2018 final C - 部分文字列と括弧

• 問題

問題概要

'(' と ')' のみからなる文字列Sがある.
1 <=i < j <=|S| で, S[i :j] が対応が取れているのは何組あるか.
1 <= |S| <= 10⁵

思考と反省

• 考えたこと 構文木作れば k 個の子を持つ親を見つける度に kC2 足していけば出来る -> 再帰で実装しよう
  -> (k+1)C2 - kC2 = k なのでその高さに戻ってくる度にもともと持ってた子を足していけば良さげ

• 詰まったこと kC2を足していく方針にすると,再帰で実装するとき根がない時困った .. 例えば ()() -> ダミーでSを(S)にするかと思ったけどヤバそうなのでやめた
  -> 差分とってkだったので,戻ってくる度にそれまで見た子を足していく方針でOKだった -> 結果的にけんちょんさんのブログと全く同じだったけど,こっちの方がとても明快

普通に)で毎回returnしていくと )( みたいな文字列でめっちゃ困る
-> 意味をなさない ) は分けなきゃいけなかった

結局よくあるstackの +1/-1 で考えるべきだった.
このstack上で,どういうクエリになるかを一番先に考える.
-> その発想で考えると,この問題だと安直なRMQで解けた

メモ

逆ポーランド記法っぽい問題,発想はすぐ出るけど実装詰まるから困る

コード