ABC288D 別解法メモ

前書き

なるべく愚直な操作でなんとかする解法です。(実質的には同じかもしれませんが、)mod  K での累積和を使っていません。

コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。

公式解説を読むほうが勉強になると思います。

問題

atcoder.jp

考え方

  •  l_i=1であれば、左から順に可能な限り0にしていき、0にできない残り K-1個が0になっているかを確かめればよい
  •  l_i \ne 1であるときは、一旦左から順に0にしていったあと、左から 元の数列の値に戻していく ことを考えていく
  • すると、 l_iから K-1個については、0ではない値になる

  • 「左から0にする」操作のあと、「左から元の数列に戻す」ということをすると、0で初期化された長さ r - l + 1の数列に範囲の右から K - 1個の値と左から K-1個の値をそれぞれ足した数列ができる
  • 範囲の長さが 2(K - 1)以上のとき:
    • 範囲左右端の値の間は、 r - l + 1 - 2 (K - 1) = r - l - 2K + 3個の0で埋められることになる
    • ここで、 0, \dots, 0, a (0はK個)は、操作で a, 0, \dots, 0にすることができる*1
    • つまり、 r - l - 2K + 3個の0は、(r - l + 3) \% K個でも同じになるため、最終的にできる数列の長さは  3(K-1)以下にできる
  • あとは、できた数列に対して愚直に操作を実行して、すべて0にできるか確かめればよい
  • 計算量について:
    • 範囲の両端の K-1個の値の事前計算: \mathcal{O}(NK)
    • 愚直に作った数列が0にできるか確かめる計算量:  \mathcal{O}(K^2)
    • よって、全体で  \mathcal{O}(K(N + QK)) で解ける

AC提出

atcoder.jp

なお、

https://

 

ということだそうなので、こちらの考え方を持っておいたほうが活かせる気がしています。

https://twitter.com/chokudai/status/1621872224465727489?s=20&t=rGTI6O6y-GB3eZShdcJysg

*1:本当はもっと強い主張ができる(公式解説参照)。なぜこれがわかったのに、解説のやり方が思いつかなかったのか……

ABC260 精進メモ

問題

atcoder.jp

思考過程

長ければ長いほど、とりあえず条件は満たせるので、どこまで「短くできるか」ということを考える。となると、おそらく各区間の端っこの部分で、ここでどうなるかを考える。

最初に、区間の「 A_iの最大値」と「 B_iの最小値」を考えてみる。が、いまいちピンとこない(入力例1だとなにか言えそうだが、入力例3だとよくわからない)。「 A_iの最大値」と「 B_iの最小値」のどちらが大きいかは入力によりそうなので、この値からなにかいうのは難しそう。

 

では端からどちらか選んでみることを考えてみるとどうか?
入力例3の1つ目(と2つ目)の区間で "1" を選ぶとする。すると、どこまで長くしなければいいか考えてみると、「1よりも大きい中で最大の区間の端のどちらか」である。この場合は "5" になる。ということで、"1"始まりの良い数列の長さは、長さが5から9まで1つづつある。

つぎに、5つ目の区間で "2"を選ぶ、つまり始まりを"2"にすることを考えると、2つ目の区間では"1"が選ばれなかったため、 "7"を選ぶ必要がある。つまり、最低でも"7"以上まで伸ばす必要がある。

こう考えていくと、「良い数列の左端を固定したとき、選ぶ必要のある数の中での最大値が、右端になりうる最小値」として考えられる。ある区間については、最初は A_iが選ばれる候補であるが、良い数列の左端の数字が A_iを超えてしまった場合は B_iが候補になる。最小の B_iよりの大きい数が左端の数字になったら打ち切る。

 

 

ということで、候補の数は最大で  N個で、入れ替えが生じるものに対して最大値が取れればいいので、sorted_setを使えば高速で判定が可能になる。Pythonであれば、tatyamさんのSortedSetを使って、追加・削除で O(\sqrt{N})、最大値の取得に  O(\log{N})でできるので、全体として計算量は  O(N\sqrt{N} + M\log{N})でできる。
あと、作れる長さを範囲で足し算するのは、imos法*1を使うことで  O(N)でできる。

 

ACコード

atcoder.jp

*1:厳密にはimos法とは言わないという話を聞いたような気がする(うろ覚え)

ARC129C 精進メモ

問題

atcoder.jp

思考過程

パッと見てどう構築するか思いつかず、色々と手で書いて考えてみる。

後ろに継ぎ足して生やしていこうとすると、場合の数を数えるのが色々とややこしくなりそう。

簡単に数えられるのは、ひたすら "7" を続ける場合で、k個続けるなら  k (k - 1) / 2個の組ができることまではわかる。
kの値を変えてできる数列にでてくる数を組み合わせて、Nが作れないだろうか……?、7の連続する間を "1" とかでくっつければできたりしないだろうか…?

簡単に実験してみると、 10^6までなら6つの数字の組み合わせで実現することが可能っぽい。

 

この方針で提出してみるが、WA。

手元で愚直に通り数を計算するものを探して見ると、  N = 14だと 717717777と出力するが、 71771が7の倍数なのでNGっぽい。

どうもこの方針だと筋が悪そう。  k (k - 1) / 2の値のいくつかの和で表すのはそれっぽそうなんだけど……。

 

この後色々考えていたが思いつかず。解説を見る。

「7の倍数になる区間は、ある桁数で区切った時の端からの7で割ったあまりの数が等しい」ということまではなんとなく考えていたが、「それの数を  k(k -1) / 2のkの値にしていく」、というところに思い至らず。

下から生やす(これまでの値を10倍する)やり方だとうまくいかないという点にややハマりしながらAC。(あまり綺麗なコードにならず)

ACコード

atcoder.jp

ABC271F 精進メモ

問題

atcoder.jp

思考過程

コンテスト中にTLE解法を投げていた。

成約が小さいので全探索できそうな雰囲気を感じる。が、本当に全探索してしまうと、 {}_{2(N - 1)} C_{N - 1}通り、 N = 20なら 約  3.5 × 10^{10} 通りあるため、間に合わない。

そこで、スタートとゴール*1から半分ずつに分けて、真ん中まで全探索させてみる(半分全列挙)。この場合、スタートからN-1回だけ進んだ真ん中までの通り数は約  2^{N -1} \le 2^{19} = 5.2 × 10^5通りなので、これは列挙できる。

スタートとゴールから辿ったものが出揃った後、「マス(i, j)で値がaになる」場合の数を辞書で管理しておけば、 O(1)で参照することができるため、「スタート→マス(i, j)までの通り数」×「マス(i, j)→ゴールまでの通り数」を足し上げて行けばOK。

 

ちなみに、対称的に実装すると真ん中のマスについて、両方で考慮される or されないになるが、適宜マスの値の排他的論理和を取ってあげて調整すればOK。

ACコード

atcoder.jp

*1:反対から辿っても同じ結果になるため、「ゴールから左か上に移動する」として計算する

ABC227D 精進メモ

問題

atcoder.jp

思考過程

最大ペアをどうにか構築できないかを考えてみようとする。

貪欲に多い部署からK人のペアを作るようにすると、最大ペアは作れなさそう(雑感)。他にうまく構築する方法が思いつかない。

なんとなくこういう、うまく組み合わせられるか考えるのが面倒なタイプの問題は、二分探索で判定問題にするとできるかもしれないので、考えてみる。

つまり、「m組のグループに分けるとき、すべてのグループでK人以上所属できることができるかどうか」という判定を考えてみる。

 

やっぱり人数が多い部署から、それぞれのグループに割り当てていくことを考える。

m組より人数が多い場合は、すべてのグループに割当させることになる。それ以上割り当てはできない。

m組まで足りない場合、途中のグループまで割り当てる。そのあと、次に考える部署についてはその続きから割り当てていく。このとき、同じグループに同じ部署が入ってしまうようなことが起こらない。なぜなら、続きから割り当てていって、同じグループに同じ部署の人が入ってしまうのは、部署の人数がm人を超えている場合であるが、続きから割り当てているということは、すでにm人を下回っている状況になっている。人数の多い部署から考えることで、同じグループに同じ部署の人が入るような状況にならないのである。

 

 

上のやり方であれば、可能な限り最大に割り当てを行えているはず。

ということで、このときのグループの所属人数の最小値を計算し、K以上かどうかで判定する。

グループが作れる最大値は  sum(A) なので、  O(Nlog(sum(A)))で解ける。

 

ACコード

atcoder.jp

ABC223F 精進メモ

問題

atcoder.jp

思考過程

最初の方針(遅延セグ木解法)

対応するカッコがちゃんと閉じているか判定する問題。この手の問題ですぐに思いつくのは、"(" なら +1して ")" なら-1していく数列を作り、「範囲の両端で同じ値」かつ「間の数字が両端の数字を下回らない」を満たしているかチェックすること。

問題は、2箇所の文字を入れ替えた時の処理。数列の値がどうなるかに着目すると、"(" が ")" になると以降の値が-2、逆だと+2になる。範囲の値が変化するのが対応できるのは遅延セグ木が考えられる。

なので、元の数列から入れ替わりがあった範囲で±2することで変化量を反映し、変化後の値を見ていけば良さそう。「範囲の両端で同じ値」は簡単にでき、「間の数字が両端の数字を下回らない」も「ある範囲の最小値」と「両端の数字」をもとめて、変化量を比べればできそうに見える。

しかし、この方針だとだめで、「ある範囲」での変化量は一定でない可能性があるため、変化後の最小値がセグ木を利用して求められない。例えば、(1, N), (2, N), ..., (N - 1, N)で入れ替えた場合、変化量が各区間で異なる変化量になる。

ということで、別の方針を考える。

 

組み合わせの更新解法

対応付けされる括弧を管理して、入れ替え時に対応する括弧を更新していく方針を考える。先に結論をいうと、これもダメだった。

上記の方針でうまいくためには、「入れ替え時に関係する括弧だけを組み替えたとき、それに関与しない箇所は対応が変わらない」という仮定が必要になるが、これが成り立たない。

例えば、「((()()))」で1, 4番目の括弧を入れ替えると「)(((()))」となるが、舌の図でいう緑で囲った位置の括弧が、入れ替え位置と関係ない場所にも関わらず対応する括弧が変化してしまっている。

ということで、この方針でもダメということになる。

 

解説を見る

流石に手詰まりになったので解説を見たが、実はセグ木でもいけるし、遅延セグ木でよかったということがわかる……。ただ、セグ木への乗せ方はあんまり自明じゃないような気がして、理解するまでに結構かかってしまった。

最初の方針で作った数列をもとに、「区間での和」と「その区間中で、左から足し算していった時にできる値の最小値」の2つを記録させていくことにする。つまり、各要素は "("なら (1, 0), ")"なら (-1, -1)として乗せる(解説とは要素が逆にしている)。

問題は区間を合わせるときにどう演算するかである。例えば 「()」の場合、左の要素が(1, 0)で右の要素が(-1, -1)のとき、(0, 0)としたい。「区間での和」は単純に足し算すればいいので簡単。もう一方の方の「最小値」の更新方法をどうするかについてだが、こちらは単純に両方の要素の最小値を更新していくだけだとうまくいかない。「左から足し算していった時の最小値」なので、右側の要素については、それまでに左側の要素の合計を足し上げて上げる必要がある。ということで、左の要素をa、右の要素をbとすると、(a[0] + b[0], min(a[1], a[0] + b[1]))となる。

(余談:もともと手元にあったセグ木のコードが演算順序を考慮していない作りになってしまっていたので、その修正が大変だった)

 

なお、遅延セグ木でも解けるらしい(そっちは後日……)。

 

ACコード

atcoder.jp

ARC152B 精進メモ

問題

atcoder.jp

思考過程

2人のスタートする位置と向きさえ決めれば、あとの動きは決まりそう。ただ、このままだと初期状態が  O(N^2) 通りあるので、間に合わない。

 

図を書いてみると、交差点は2つになっていそうなので、この交差する場所をうまく選んであげれば行けそう。

多分初期位置によらずに交差するのは(時間的に最後を除いて)2つだろう思われる(未証明)ので、
最初に交差する地点を決めてシミュレーションレーションができそう。これだと場合の数は  Nで済むので。

 

次に出発してから交差する休憩所を決める。シミュレーションについて、愚直に端から位置を求めようとすると、各シミュレーションごとに O(N) かかってしまい、全体で O(N^2)になってしまうので間に合わない。なので工夫を考える。

よく考えると、なるべく休憩所で待つ時間が少ない方がいいので、道上ですれ違う直前/直後の休憩所で待つほうが良い。なので、交差する瞬間の位置を求める。時間自体は距離と等しいので、簡単に求められるので、「出発して折り返してから、二人のどちらが先についているか」というもので二分探索できる。

 

そこまでいったら、休憩する場所の2箇所でどのぐらい時間がかかるかを求めればいい。色々整理すると、 i番目の休憩所から出発して途中 j番目の休憩所で待機する時間は、「 i番目の休憩所から左右のどちらかの端に行って j番目の休憩所にいくまでのかかる時間の大きい方」+「 j番目の休憩所から左右のどちらかの端に行って i番目の休憩所にいくまでのかかる時間の大きい方」になる。これなら全体で O(NlogN)で済むので間に合いそう。

 

二分探索のとき、0Lを追加していると楽だけど、両端では待機できないので、初期値に注意する必要があったりした。

あと、整理する前は場合わけして混乱していたのでコードではあんまり整理された書き方になっていなかったりする。

 

ACコード

atcoder.jp