C - Sugar Water - AtCoder Regular Contest 083
A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。
- 100A[g]の水追加
- 100B[g]の水追加
- C[g]の砂糖追加
- D[g]の砂糖追加
現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、最大濃度のときの砂糖水と砂糖の重量を答えよ。(答えはいくつかある)
A, B, C, Dの操作を行い、メモ化再帰で容量Fに到達するまで全探索する。それぞれの制限が小さいからといってメモ化をサボるとTLEになるので注意。メモ化のキーは現在の{水の量, 砂糖の量}など。double型ではなく、整数型で全部決定できるのでできればその方針で行う。
ACしたら力尽きてブログを更新する気力がなくなる件
時間かけてACした問題は復習も兼ねてブログに書くべきなんだけど、通した時点で力尽きてしまうのなんとかしたいですね。3連休に一気に積みAC？をまとめるか…
D: Derangement - AtCoder Regular Contest 082
順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。
p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ l に対して、この部分列をすべてp[i] ≠ l となるようにするにはペアを作って l / 2(小数以下切り捨て)回で可能である。これは、最初から順にペアを作ってそれらをSwapしていけば偶数この場合はすべて条件をみたすようにでき、奇数個の場合は最後の1個を、その次のp[i] ≠ iであるような要素と入れ替えれば条件を満たすことができるからである。終端にちょっとだけ注意する。
よって、p[i]の中でp[i] = iとなるような部分列を抽出し、(int)(l / 2) を足していけばよい。O(N)。
C: Together - AtCoder Regular Contest 082
数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。
v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。すると、v[n-1] + v[n] + v[n + 1]の最大値が求める答えになります。ただし、両端に注意。O(N)。
TopCoder SRM 720 Div1 Med
n, k (n>=k) が与えられる。n x n行列で、任意の行及び列を取り出した時、その中で異なる要素がk個になるような行列を構成したい。このような行列の中で、全要素について異なる要素が最大のものを一個構成せよ。
なんかEasyでも良さそうな問題。(今回はEasyがやたら難しかったので問題を取り違えた説もある)。まず全要素を0で並べた行列を作成し、1行目は {1, 2, 3,...,k, 0, 0, 0, ...} 、
2行目は{0, (k+1), (k+2), (k+3),...,(k+k), 0, 0, 0, ...} という感じで、{1, 2, 3..k, 0, 0, ..} という数列を非ゼロ要素をk-インクリメントしながらローテーションしたものを並べると目的の行列が構成できる。
Hackケースとして、ローテーションではなく末尾を落とした場合がたくさんあった模様。
Codeforces Round #429 D. Leha and another game about graph
無向連結グラフが与えられる。自己ループはないが二重辺は存在する。各頂点iにはd[i]=0 or 1 or -1 という数が割り当てられている。このグラフのサブグラフを構成して、degree(i) % 2 = d[i] or d[i] = -1 を満たす、つまり、0または1の場合は頂点の次数のmod2にd[i]が一致するようにしたい。このようなサブグラフが存在するか？存在するならば具体的に構成せよ。
-1の頂点がない状況を考える。頂点次数のmod 2がd[i]と一致している頂点を「正しい頂点」、一致していない頂点を「正しくない頂点」と定義すると、正しくない頂点同士を結んだエッジは取り除いて除去することができる。また、正しい頂点と正しくない頂点を結ぶエッジは取り除くことによって、正しいと正しくないをSwapすることができる。
そこで、ある頂点を根とする全域木を考える(と言っても単に未訪問の頂点をdfsで辿っていくだけである)このとき、正しくない頂点が根から遠いところにある場合は、根の方向のエッジを取り除く(この取り除いたエッジのインデックスはメモしておく)。すると、エッジの両端は正しい頂点になるか、または根に近いほうが正しくない頂点になる、のいずれかになる。これを葉から再帰的に行うことで、最終的に根が正しい頂点になっていれば構成可能ということで、メモしておいたインデックスを除くサブグラフを出力する。
次に-1の頂点が1個以上ある場合、同じような考え方で、正しい頂点とみなしておくが、もし接続されたエッジを取り除いたあとも正しい頂点のままとみなしておく。ただし、この時根が正しくない頂点になっていても、-1の頂点に向かって正しくない頂点を移動してけば構成可能になる。このような判定をしないために、元から根として-1が割り振られた頂点を選んでおくと、最終的に根のところは常に構成可能になる。つまり、-1の頂点が1個以上ある場合、常に構成可能になる。O(V)。
Codeforces Round #429 (Div. 2) C. Leha and Function
長さnでmin(a[i])>=max(b[i])であるような数列a[i], b[i]が与えられる。F(n, k)を Σ[S⊆{1, 2, ... , n}, #S=k] min(S) / nCk (つまり、k個の要素からなる部分集合の最小値の期待値) とする時、a[i]を並び替えて、ΣF(a[i], b[i]) を最大化したい。最大値を与えるa[i]の並び替えを一つ求めよ。
実験してみるとわかるが、F(n, k)はnを固定したときにkの単調減少関数、kを固定したときにnの単調増加関数になっている。(漸化式を立てれば一応証明はできる)
更にこちらは実験でしか確かめていないが、F(n1, k1)+F(n2, k2)について、n1>n2のとき、k1<k2の場合のほうがk1>k2のときよりも大きくなる。そのため、a[i]とb[i]はそれぞれ昇順と降順で組み合わせるのが最適とわかる。
ほとんど実験だけの問題であるが、あとはソートして組み合わせ、元のb[i]の順序で出力すればよい。O(n logn)。
