仮のブログ

仮です

Codeforces Round #634 (Div. 3), Codeforces Round #636 (Div. 3), Codeforces Round #642 (Div. 3) バチャ

Codeforces Round #634 (Div. 3)(2022/4/28)

A: Candies and Two Sisters

偶奇で場合分けしたりしなかったりで計算すると  \left\lfloor\frac{n-1}{2}\right\rfloor となる https://codeforces.com/contest/1335/submission/155258825

B: Construct the String

 b 種類の文字を周期的に繰り返せばよい.
https://codeforces.com/contest/1335/submission/155258934

C: Two Teams Composing

条件的にチームを作りにくそうなのは2つ目のチームである.
よって一旦人数が等しいという条件を忘れて2つ目のチームの人数を最大化する.
これは, 各スキルを持つ人数を連想配列等でカウントしてその最大値を求めればよい.
ここで最後の調整用のためにそのスキルを持つ人のうち1人をチームに入れずにおくとよい.
残った人で1つ目のチームを作る時, これはスキルの種類数-1 (2つ目のチームのスキルは使わないと)となる.
ここで, 調整用に残していた1人は現在作られたどちらのチームに加入しても良いチームになるので, 人数の少ない方のチームにその人を加入させる.
そして, 2つのチームの人数をそろえるため, 人数の少ない方のチームの人数を答えとすればよい.
https://codeforces.com/contest/1335/submission/155259123

D: Anti-Sudoku

各行, 各列で1つずつ計9個数字の変えるようにすると, 元が正しい解であるという条件からその列, 行で数字をダブらせることができる.
後は各ブロックで数字の重複を作りたいので, 上記で選ぶ9個の数字を各ブロックから1つずつ選び, そのブロック内にある他の数に変えればよい.
https://codeforces.com/contest/1335/submission/155259445

E1: Three Blocks Palindrome (easy version)

両端の値と使う数を全探索する. これらを決め打ちした時, 両端の数として使う項は出来るだけ端に寄せた方が良いので, 各値の出現indexを配列で持っておけば, 第何項から第何項を真ん中の数として使えるかがすぐに求まる.
この時, 真ん中に挟む数はその間に最も多く出現する数を選べばよく, 各値の出現数は累積和を作っておくと高速に求まる.
最初の決め打ちとその後の真ん中の数を選ぶパートで計算量が  O(\sum n\sigma^{2}) と一見なるが(この制約ならそれでも間に合うが), 実際は両端の値と使う数のペアは高々  n 通りであるので, 計算量が  O(\sum n\sigma) である. https://codeforces.com/contest/1335/submission/155260088

E2: Three Blocks Palindrome (hard version)

E1の計算量解析からE2も同じで通ると思ったら累積和を作る過程でMLEした.
そこで累積和を取らず, indexだけ配列で持っておいて, lower_boundによって各値が間にいくつあるかを計算した. 計算量に  \log が付くが何とか間に合った.
https://codeforces.com/contest/1335/submission/155260208

F: Robots on a Grid

最初の実装とACを取った実装が大きく違う.
最初は, SCCをしてロボットの動きのループを探し, ループ内の各位置と同じ位置に到達する初期位置をDFSで求めて, その中に黒マスがあるかを探す方針でいったが, MLEが取れなかった.
この方針で考えるのを一旦諦めて, 考察を深めると, 十分大きな時間がたてば全てのロボットは上記のループ内に入ることが分かる.
よって, ループを検出したり各ループにDFSを生やすのではなく, ダブリングのノリで十分時間経過した後の移動先をもって衝突を起こす場所の分類を行い, その中に黒マスがあるかを数えた.
https://codeforces.com/contest/1335/submission/155264687

総括

1時間40分全完5ペナ115位. Fで苦労したが, 方針を変えてACをとれたのはとても良い傾向. F問題が面白いと思う.

Codeforces Round #636 (Div. 3)(2022/4/30)

A: Candies

 k=2,3,\dots,32 位まで試せばその中に答えがある.
https://codeforces.com/contest/1343/submission/155359723

B: Balanced Array

 n が4の倍数でない時, 奇数の方の総和が奇数となる事から答えは存在しない.
 n が4の倍数の時, 偶数2項の和と奇数2項の和が等しいように構成すると構成しやすい. (私はは  M+2, M-2 M+1, M-1 ([tex; M] は適当に大きな値) のように作っていった. )
https://codeforces.com/contest/1343/submission/155360088

C: Alternating Subsequence

数列を前から見ていって正負の切り替わる回数+1が長さの最大値である.
また, このことから長さを最大化したうえで総和を最大にするには, 正負の切り替わるところで数列を分割した時に各分割列の中で最大の物を選ぶようにすればよいことが分かる.
https://codeforces.com/contest/1343/submission/155360439

D: Constant Palindrome Sum

 x の値を決め打ちすると, 各ペア  (a_i,a_{n-i+1}) について何個の数を変えればよいかが分かる.
具体的には,  a_i,a_{n-i+1} の小さい方, 大きい方をそれぞれ  m,M として,

  •  x\lt 1+m の時: 2つとも変える必要がある
  •  1+m\le x\lt M+m の時: 大きい方のみ変える必要がある
  •  x=M+m の時: 変えなくて良い
  •  M+m\lt x\le M+k の時: 小さい方のみ変える必要がある
  •  M+k\lt x の時: 2つとも変える必要がある

となる.
これらはうまい具合に区間になっているため, imos法をすれば,  x の値毎に何個要素を変更する必要があるかが求まる.
https://codeforces.com/contest/1343/submission/155361064

E: Weights Distributing

どのような経路を取ったとしても, ある頂点  v が存在して,  (a,v),\ (v,b),\ (b,v),\ (v,c) という移動をする. ( (s,t) s から  t への移動を表すとする. 以下でも同様.)
この時, この4回の移動で  (v,b),\ (b,v) の移動のペア以外では同じ辺を通らないとしてよい. (厳密に証明もできるが, 図を描いてみて, このようなペアがあった場合他の頂点を  v としたときに同様の移動経路が表されることを確かめた方が直感的で分かりやすいと思う.)
よって, 3頂点  a,b,c から  v への経路で用いる辺数を求め, 2回通る  (b,v) 間の辺に小さな重みを割り当て, 残りの辺に残ったうち小さい重みを割り振っていけばよい.
3頂点  a,b,c それぞれを始点としてBFSを行うことで辺数は求まり, 小さい重みから順に割り振るのは辺の重みを昇順にソートしておいて累積和を取っておけばよい.
https://codeforces.com/contest/1343/submission/155362573

F: Restore the Permutation by Sorted Segments

前から  r-1 項が決まっているときに,  r を右端として得られる数列の条件を考えると, その数列の要素が1つを除いて出現していてかつその出現が直前まで連続で続いていることである.
よって以下の手順で元の数列の構成を試みることができる.

  1. 先頭の値を決め打ちする.
  2. この値を含んでいる数列からその値を取り除き, 0回目に消した旨を記録しておく. この時, 数列の要素数が1になる数列があればその数列の項の値を次の値とする.
  3. 2.で決めた値を含んでいる数列からその値を取り除き, 1回目に消した旨を記録しておく. この時, 数列の要素数が1になる数列があればその数列の項の値を次の値とする.
  4. これを繰り返す.

ただし, 各数列には何回目で要素を消したかが記録されていくがこの値が不連続になったらその時点で構築は不可能である. また, 数列の要素を消したとき, 要素数が1となる数列が存在しない場合も次に来る値が存在できないので構築不可能.
https://codeforces.com/contest/1343/submission/155364907

総括

59分全完0ペナ10位. とても良い. diffを確認したところFは赤だったので解けたのは単なる偶然の可能性が高いが嬉しい. DEFがとても面白い.

Codeforces Round #642 (Div. 3)(2022/5/1)

A: Most Unstable Array

 n=1 の時は  a=(m) とするしかない.
 n=2 の時は  a=(0,m) とするのが最適.
 n\ge 3 の時は  a=(0,0,\dots,m,0) とするのが最適.
https://codeforces.com/contest/1353/submission/155486310

B: Two Arrays And Swaps

明らかに  a の最小値と  b の最大値を交換していくのが最適である. これを, スコアが増加しなくなるか交換回数が  k 回に達するかまで行えばよい.
https://codeforces.com/contest/1353/submission/155486533

C: Board Moves

真ん中に集めるのが良い.
全てのマスに対して計算を行うと時間がかかるので, 移動回数が等しいところを纏めて計算する.
計算を頑張れば  O(1) にもできるが  O(n) でも0msなので.
https://codeforces.com/contest/1353/submission/155486716

D: Constructing the Array

優先度付きキューに, 数列の長さと左端の位置をペアにして持たせておく.
最も数列の長さが長いものを取り出して, 答えの数列に記録して, そこで数列を2つに分け, キューに突っ込むを繰り返せばよい.
左端の位置は-1倍する等の工夫をして, 同じ長さなら最も左の物を取り出せるように工夫する.
https://codeforces.com/contest/1353/submission/155487144

E: K-periodic Garland

あかりを付ける場所は  \pmod{k} で等しい場所になる.
よって, この剰余を全探索する.
剰余を固定した時, 場所の剰余が異なる場所は全て0に,
剰余が等しい場所だけを抜き出すと, 00001111100000 のような形になっている.
前者は全体の1の位置を事前にカウントしておき, 剰余が等しい場所の1の位置をカウントするとその差から操作回数を求めることができる.
後者も, 1を+1に, 0を-1に対応させるなどして累積和を取ることで高速に操作回数の最小値を求めることができる.
https://codeforces.com/contest/1353/submission/155489044

F: Decreasing Heights

 a_{i,j} から  i+j+a_{0,0} を引いておくと, 同じ高さにのみにしか移動できないverの問題になる.
この時, 移動経路に含まれる最小の値を  c とすると, 経路中の全ての高さを  c にしないといけないので, 移動経路のマスを  (0,0)=k_0,k_1,\dots,k_{n+m-2}=(n-1,m-1) とすると, この経路でのスコアは  \sum_{j=0}^{n+m-2}(a_{k_j}-c)=\sum_{j=0}^{n+m-2}a_{k_j}-(n+m-2)c で表せる.
 (n+m-2)c c のみに依存して実際の移動経路に依らないことに注目すると,  c を固定した際のスコアの最小値はgrid上の単純なDPによって求めることができる. (但し  c より高さの低いマスを通れないようにしないといけない)
後は最小値  c を全探索すればよく,  c a_{i,j} のいずれかであるので, 候補は  nm 個.
よって全体の計算量は  O(n^2m^2) で間に合う.
(cf: 類題https://atcoder.jp/contests/abc227/tasks/abc227_f)
https://codeforces.com/contest/1353/submission/155490369

総括

58分全完0ペナ53位. Fが早く解けたのは良いが, Eに時間を掛けすぎた. 同程度の順位の人がEを10分~15分ほどで解いているのでそれくらいで解きたかった.