https://csacademy.com/contest/beta-round-1/summary/
アルファベット小文字の順列と$N$個の文字列が与えられるので、与えられた順列を辞書順として、$N$個の文字列を並べ替えて出力せよ。ただし、大文字は小文字より辞書順で大きいとする。
与えられた辞書順で一番小さい文字を0、次に小さい文字を1というように数字に置き換えて、stringをvector<int>に直してソートすればよい。大文字は、小文字に対応する数字に充分大きい定数を足したものとなる。
自力AC。すぐに思いついた。ICPC2018アジア横浜のA問題を思い出したがよく考えるとそんなに似てなかった。
$N$要素の整数配列が与えられる。これらの整数をできるだけ多くの連続な部分列に分割し、分割後の部分列の個数を出力せよ。ただし、分割後の各部分列をソートするだけで配列全体がソートできるような分け方でなくてはならない。
与えられた配列をA, AをソートしたものをBと呼ぶことにすると、Aを前から順にみて、要素aが含まれる部分列はBで要素aが出現する位置まで繋がっていなくてはいけないことがわかる。よって、現在見ている部分列のなかで最大の要素とその個数を常に記録しておき、それらがBのなかですべてあらわれる位置まできたら貪欲に部分列を切りだすことでこの問題が解ける。
自力AC。それほど難しくはなかった。
はじめに$N$要素の整数の集合があり、AlexとBenがゲームをする。Alexのターンでは、集合から空でない部分集合を選んで、選んだ部分集合に含まれる整数をすべて集合から取り除く。Benのターンでは、集合に含まれる整数をひとつ選んで取り除く。Alexの目的は、Alexの取り除いた整数の和を最大にすることであり、Benの目的は、Alexの取り除いた整数の和を最小にすることである。Alexのターンからゲームが始まり、両者が最適に行動するとき、最終的にAlexが取り除くことになる整数の和を出力せよ。
最初に与えられた配列をソートした後、Alexは最初にほしい数字をすべて取る(これは一番大きい数字を含む連続した区間となる)。その後、Benのターンでは一番大きい数字以外を取る理由がないので、Benは毎ターン一番大きい数字を取る。Alexのターンでは最初に取らなかった(不要な)数字はできるだけ多くBenに取らせたいので、一番大きな数字をひとつだけ取ることになる。よって、Alexが最初に取る区間が決まればAlexのスコアが一意に定まるので、これを全通りシミュレートして、答えが最大となるようなものを出力すればよい。累積和を使えば、Alexが取ることになる数字の和を高速に計算できる。
自力AC。ほとんど同じ問題を見たことがある気がしたけど、どこで見たのか思い出せない。解説によると、Alexの最初の行動でありうるものはたかだか数通りしかないとある。全通り試す必要はないということらしい。
整数$N$と、整数のペアが$M$個与えられる。はじめに1から$N$までの数字を昇順に並べた順列があり、ペア$(a, b)$は、順列の$a$番目の値と$b$番目の値を入れ替える操作を表す。与えられた操作列は、操作を1つだけ取り除くことで最終的に順列の$K$番目の値が1であるようにできることが保証されているので、そのような操作のindexを出力せよ。ただし、そのような操作が複数ある場合は最も小さいindexを出力しなければならない。
前から順に$i$番目までの操作を行ったときの1の場所と、後ろから順に$i$番目までの操作を行ったときの1の場所をすべての$i$についてそれぞれ記録しておく。前から$i-1$番目までの操作を行ったときの1の場所が後ろから$i+1$番目までの操作を行ったときの1の場所と一致していれば$i$番目の操作は取り除けるので、前から順番に調べるだけでよい。
自力AC。自然な発想で正解できる。解説によると、最後までシミュレートしたときの結果を見れば累積和は必要ないらしい。
Alexがビー玉の入った袋を持っている。Benはその中から$N$個のビー玉を選ぶ。AlexはBenの選んだ$N$個のビー玉すべてに対して袋の中に同じ色のビー玉がいくつあるかを答えるが、必ず1度だけ嘘をつく。整数$N$とAlexの$N$個の答えが与えられるので、袋の中に入っているビー玉の数の最小値を出力せよ。
数$i$が$x$個あるとき、最小で$\lceil \frac{x}{i} \rceil\times i$個のボールがなくてはならない。これをすべての$i$について足し合わせると、Alexが嘘をついていない場合のボールの数の最小値がわかる。実際にはAlexは必ず1度嘘をつくので、数字をひとつ別の数字に振替えなくてはならない。どの数字を振替えればよいかは、各数字について1つ減らした場合と1つ増やした場合に必要なボールの数の変化を予め計算してソートしておくことでO(1)でわかる。1が1つもない場合でも他の数字を1にすることが最適になる場合や、1しかないときに1をひとつ2にすることが最適になる場合もあるので、そのへんはうまくやる。
解説AC。場合分け($n\times i+m$個あるような$i$が0個、1個、2個以上)で解こうとしていて、全パターン網羅できていなかったらしくWAがどうしても取れなかったので解説を見たら思ったよりシンプルで悔しい。
それぞれ高さの違う水平な台が$N$個あり、各台の左右の端の$x$座標が与えられる。その後、上空から$M$個のボールが落ちてくる。各ボールの$x$座標が与えられるので、すべてのボールに当たらない場所にすべての台を移動させるときの移動距離の最小値を出力せよ。ただし、ボールが台に当たるとは、台の左右の端$(l, r)$に対してボールの$x$座標が$l\lt x\lt r$となることである。
それぞれの台について、動かし方は
自力AC。台を動かす場所を求めるパートはAGC005-Bを彷彿とさせる。自然な発想で解けて気分が良かった。
$N$個の非負整数のみからなる単調非減少数列が与えられる。この数列を正の公差をもつ2つの等差数列(連続である必要はないが、2つ以上の項をもつ必要がある)に分割し、そのうちのひとつについて(最初の要素, 公差, 長さ)を出力せよ。解が2つ以上ある場合は(最初の要素, 公差, 長さ)が辞書順でもっとも小さいものを出力し、解がない場合は-1を出力せよ。
最初の3要素を2つのグループに分ける方法は4通り存在し、このうち要素数の多い方(2つまたは3つ入ったほう)を数列$A$、そうでない方を$B$と呼ぶことにする。最初の3要素を分けた時点で$A$は公差がすでに決定した状態であり、$B$は公差が決定していない状態である。ここで、残った要素を順番に見ていき、それが数列$A$の次の要素として適していれば追加し、そうでなければ数列$B$に追加することを試みる。数列$B$に要素を追加した時点でそれまでの$B$の要素と合わせて等差数列にならないことがわかれば、そこで探索を打ち切って良い。要素を$A$に追加するたびに、その要素より後の要素をすべて数列$B$に追加することができるかどうかを毎回考えることにすると、可能なグループ分けをすべて列挙できることがわかる。最初に$i$番目以降の要素がすべて等差数列になっているかどうかを確認しておけばこの判定はO(1)ででき、探索部分は全体としてO($N$)となる。最後に、探索によって得た解の候補を辞書順でソートして一番小さいものを出力すれば良い。
解説AC。最初の数項を全列挙するという解法でABC055Dを思い出した。解説を見る前にも想定解に近いことは考えてはいたが、各要素は$10^7$以下であるという制約から、LISのようにDPで答えを求める問題ではないかと思い込んでいた。この制約は結局関係なかった。さらに、この問題は実装が非常にややこしく、場合分けをバグらせまくって滅茶苦茶時間がかかってしまった。正直コンテスト本番ではやりたくない問題。
$N$要素の数列が与えられる。この数列から2つの要素を選んで、(値, index)が辞書順で小さい方を削除する操作を繰り返すことを考える。ここで、各操作にかかるコストは選んだ要素のうち大きい方の値と同じである。数列の要素が1つになるまで操作を繰り返すとき、コストが最小になるような操作列の数を$10^9+7$で割った余りを出力せよ。ただし、2つの操作列が異なるとは、$i$番目に選んだ要素のペア(ペア($a,b$)とペア($b,a$)は同じであるとみなす)が異なるような$i$が存在することをいう。
数列の要素の順番は答えに影響しないので、最初に数列を昇順でソートする。最小コストを実現する操作列のうち自明なものは、その時点での数列の一番前の要素とその次の要素をペアにし続けるというものである。ここから、$i$番目に小さい数字が$n_i$個あるとき、最小コストを実現するためには$i$番目に小さい数字どうしのペアを必ず$n_i-1$個つくらなくてはならないことがわかる。$i$番目に小さい数字のうち残ったひとつは$i+1$番目に小さい数字とペアになる。
同じ数字が$n$個あるとき、そのなかで$n-1$個のペアを作り、1つ残してすべて消す場合の数をP[$n$]とする。$n$個のなかから最初のペアを選ぶ方法は$\frac{n(n-1)}{2}$通りあり、その後は$n-1$個の数字が残ることから $$P[n]=\frac{n(n-1)}{2}\times P[n-1]$$ の漸化式で求められる。
$i$番目に小さい数字のうち最後に残ったものは$i+1$番目に小さい数字とペアにならなくてはいけないので、$i$番目に小さい数字の最後のひとつが消えるときにはそれ以下の数字はすべて消えていなくてはならないことがわかる。逆に、$i-1$番目に小さい数字がすべて消えたとき、$i$番目に小さい数字は$n_i-1$個までならすでに消えていてもよい。 DPテーブルを
$DP[i]$=$i$番目に小さい数字を1つだけ残して、それ以下の数字をすべて消す操作列の数
とすれば $$DP[i]=\sum_{x=0}^{n_i-1} \left( n_i-x \right) \left(_{\sum_{j=1}^{i-1}n_j}H_{x}\right)P[n_i]\times DP[i-1]$$ で更新できる。$i-1$番目に小さい数字のうち最後のひとつが消えるとき、$i$番目に小さい数字が$x$個すでに消えていたとする。$i-1$番目に小さい数字のうち最後のひとつは、$i$番目に小さい数字のうちまだ消えていない$(n_i-x)$個のどれかとペアになって消える。すでに消えている$x$個の数字が消えた場所の組み合わせは$_{\sum_{j=1}^{i-1}n_j}H_{x}$通り($i-1$番目に小さい数字以下の数字$\sum_{j=1}^{i-1} n_j$個が消えている最中にどこかのタイミングで消えたはずである)、$i$番目に小さい数字の消え方の組み合わせは$P[n_i]$通りある。最後にこれをすべての$x$について足し合わせたものが上式の意味である。$DP[N]$はこの問題の答えである。
解説AC。考察は大体できていたが、実際に場合の数を求める方法が分からなかった。$i-1$番目に小さい数字までの操作列に$i$番目に小さい数字を消す操作を差し込んで次の操作列を作るDPは、分かってしまえば簡単に見えるが自力で思いつくのは難しい……。