仮のブログ

仮です

Codeforces Round #734 (Div. 3), Codeforces Round #739 (Div. 3), Codeforces Round #744 (Div. 3) バチャ

Codeforces Round #734 (Div. 3)(2022/5/20)

A: Polycarp and Coins

3の剰余で場合分けをすればよい.
https://codeforces.com/contest/1551/submission/157784800

B1: Wonderful Coloring - 1

2回以上現れるアルファベットにはそれぞれの色を塗るマスが一つずつあるとしてよい.
1度しか現れないアルファベットには半分を赤に, 半分を緑に塗る.
https://codeforces.com/contest/1551/submission/157785009

B2: Wonderful Coloring - 2

各数毎に登場回数を管理して置き, その数が  k 回現れるまで色を塗っていけばよい.
https://codeforces.com/contest/1551/submission/157786127

C: Interesting Story

この問題はかなり面白いと思う.
まず各文字の並びはどうでもいいので, 各文字列での各アルファベットの登場回数をメモっておく.
答えを計算する際は, どの文字を一番多く出現させるかを全探索する.
これを決め打ちした後は, その文字の出現回数-それ以外の文字の出現回数の多い文字列から貪欲にとっていけばよい.
https://codeforces.com/contest/1551/submission/157786469

D1: Domino (easy version)

 n が奇数の時は最下段は横に並べるとしてよい.
 m が奇数の時は最右列は縦に並べるとしてよい.
すると, 残りのマスは2行2列毎の塊と考えることができ, 各塊を縦ドミノ2つで並べるか横ドミノ2つで並べるかを選ぶと考えればよい.
https://codeforces.com/contest/1551/submission/157787207

D2: Domino (hard version)

D1の時のように考えて右上から順番に横ドミノの数が規定に達するまで横にして後を縦にすればよい.
https://codeforces.com/contest/1551/submission/157788005

E: Fixed Points

DP \lbrack i\rbrack\lbrack j\rbrack で前から  i 項まで見て  j 項を消したときのスコアの最大値を表すとする.
 a_{i}不動点とする場合, それより前の項を何個消していればよいかは値とindexの値を比べればよいので各遷移は  O(1) でできる.
DPテーブルが完成した後は, 配列の値が  k 以上のところで何個の項を消しているかを調べればよい.
https://codeforces.com/contest/1551/submission/157788740

F: Equidistant Vertices

 k=2 の時は任意の頂点対が条件を満たす.
以下それ以外の時を考える.
簡単な観察から  k 個の頂点の任意の2つの頂点が同じ共通祖先をもつ必要があると分かる.
言い換えると, ある頂点を根としたとき, その頂点からの深さが等しい頂点を根の直接の子につき最大一つずつ, 計  k 個選べばよい.
よって, 各頂点を根にして深さ  d の頂点が根の子の部分木にいくつあるかを計算すればよい.
https://codeforces.com/contest/1551/submission/157793722

総括

1時間43分全完10ペナ73位. Fに苦労した. 考察が固まりきる前に実装に入ってしまったのが敗因.

Codeforces Round #739 (Div. 3)(2022/5/21)

A: Dislike of Threes

予め配列を作っておいても毎回1から順に確認していっても間に合う.
https://codeforces.com/contest/1560/submission/157910068

B: Who's Opposite?

かなり時間を取られた. 向かい合う人の差から全体の人数が分かる.
この時, 与えられた2人が向かいあい得ない場合やの題意の1人の向いが存在しなければ-1を, 向いあい得るなら全体の人数から向かい合う人の番号を計算できる.
https://codeforces.com/contest/1560/submission/157910821

C: Infinity Table

1行目に注目すると, 平方数が並ぶ.
また,  i i+1 列目には  i(i+1) が入る.
これらの情報から, 与えられた数が何行目に入るかあるいは何列目に入るかが特定できる.
その後にもう一方の情報を特定すればよい.
https://codeforces.com/contest/1560/submission/157911533

D: Make a Power of Two

どんな数でも, 全て消した後に2を書けば2冪になるので, 10が答えの上界である.
よって, 付け加えるのは最大でも9桁だけで良く, 計算過程の値は  10^18 に収まる.
2冪の候補が数十通りしかないので, これを全て試せばよい.
試し方は与えられた数と目標の数を文字列と思って, 与えられた数の部分列で最大何文字目標の数の接頭辞を作れるか貪欲に調べればよい.
https://codeforces.com/contest/1560/submission/157913195

E: Polycarp and String Transformation

答えが存在する場合の消す順番は,  t の逆順で文字の出現順を見ればよい.
すると,  t に各英小文字がいくつあるかの情報から,  s に英小文字がいくつ含まれている必要があるかが分かる. (例えば 'a' が3番目に消えたとしたら,  s に含まれる 'a' の数の3倍の 'a' が  t に含まれる)
すると,  s の文字数が分かり,  s が特定できるので, これから  t が正しく生成されるか確かめればよい.
https://codeforces.com/contest/1560/submission/157914819

F1: Nearest Beautiful Number (easy version)

F2本質的にはと同じ https://codeforces.com/contest/1560/submission/157918004

F2: Nearest Beautiful Number (hard version)

使う数字の集合を決め打ちする. これは[tex: {}{10}\mathrm{C}{5}=252] 通りと意外と少ない.
使う数字を決め打った後は上の桁から, 桁DPを行えばよい.
毎回組み合わせを全探索したらTLEしたので, 事前に全て計算しておいた.
https://codeforces.com/contest/1560/submission/157919313

総括

1時間35分全完5ペナ245位. うーん.

Codeforces Round #744 (Div. 3)(20225/21)

A: Casimir's String Solitaire

Aの個数+Cの個数=Bの個数かを調べる.
https://codeforces.com/contest/1579/submission/157997585

B: Shifting Sort

 n 回の猶予があるのでソート後に最も左にあるものを最も左に寄せて二番目の物を二番目に寄せて...というのを繰り返せばよい.
区間は常に  \lbrack i,n\rbrack というものを選ぶと考えやすい.
https://codeforces.com/contest/1579/submission/157998132

C: Ticks

各マスに対して, そのマスを中心としたtickの設置可能な最大サイズを求め,  k 以上だったものを実際に置き, 全ての色付きますが塗られるかを調べる.
https://codeforces.com/contest/1579/submission/157999019

D: Productive Meeting

値の大きい二人を選んで会話させるというのを繰り返せばよい.
全ての値を優先度付きキューに入れるとこれは実現できる.
計算量の  \log も落とせそう.
https://codeforces.com/contest/1579/submission/157999446

E1: Permutation Minimization by Deque

現在のdequeの先頭より大きな値を追加するときは末尾に, そうでないときは先頭に入れてやればよい.
https://codeforces.com/contest/1579/submission/157999732

E2: Array Optimization by Deque

各値をdequeに突っ込むとき, dequeの中の値は集合としては操作に依らない.
そして, その値とそれ以前に入れた値による転倒は個別の順番は影響せず, 新たな値を先頭に入れるか末尾に入れるかにのみ依る.
結局, セグメント木等によって, 新たな値をdequeの先頭/末尾それぞれに入れた時の転倒数の増加を計算し, 小さい方を採用すればよい.
https://codeforces.com/contest/1579/submission/158000706

F: Array Stabilization (AND version)

 a_{0} が0になるまでの操作回数は,  a_{0},\ a_{0-d},\ a_{0-2d}\dots の連続する1の個数に等しい.
よってこれを求めればよいが, 全て愚直に調べるとTLEするので, メモ化したり再帰にしたりすればよい.
https://codeforces.com/contest/1579/submission/158001386

G: Minimal Coverage

とても面白い.
まずかなりナイーブな方法として思いついたのが, 前からいくつかのセグメントを見終わった時に, 覆っている区間の左端の座標, 右端の座標, 今いる座標の組になるような置き方が存在するかをboolで持たせるというものであるが, これの計算量は  O(nA^3)\ (A:=\max\lbrace a_{i}\rbrace) で当然間に合わない.
一段階目の高速化として, 前からいくつかのセグメントを見終わった時に, 左端の座標, 今いる座標の組ごとに右端の座標の最小値を値で持たせるというものである. 右端の情報を配列の値として持たせることで次元を落とせる. これの計算量は  O(nA^2)\ (A:=\max\lbrace a_{i}\rbrace) でまだ間に合わない.
次に注目することとして, 上で持たせた情報のうち, 左端の座標, 今いる座標は相対的な位置関係さえ同じなら同じ遷移をするという事である. よって, 各座標の代わりに相対的な座標を持たせることにする. これによりさらに次元を落とすことができ, 計算量は  O(nA)\ (A:=\max\lbrace a_{i}\rbrace) で間に合う.
各遷移は, 右側に伸ばす, 左側に伸ばすのそれぞれの場合に, 右/左端の値が更新されるか否かで場合分けをすればよい.
https://codeforces.com/contest/1579/submission/158012658

総括

1時間39分全完0ペナ62位. 全体的に実装が重めのセットでしんどかったがペナなしでできたのは良かった. (サンプル合わせの段階でかなり苦労はしたが). G問題が段階を追って高速化する感じがしてとても面白かった.