仮のブログ

仮です

Codeforces Round #713 (Div. 3), Codeforces Round #725 (Div. 3), Codeforces Round #731 (Div. 3) バチャ

Codeforces Round #713 (Div. 3)(2022/5/12)

A: Spy Detected!

初項と末項が等しければその間に, 異なればそのどちらかが異なる数であるので場合分けをすればよい.
場合分けをすると, 多数側の数を確定できるのでそれを比較に用いればよい.
https://codeforces.com/contest/1512/submission/156893367

B: Almost Rectangle

2点が異なる行, 列にある時はその2点が対角線になるようにすればよく, そうでないときはその2点が長方形の1辺となるので, 残りの辺をその辺と平行になるようにすればよい. 座標を1だけずらすのが楽で良い.
https://codeforces.com/contest/1512/submission/156893707

C: A-B Palindrome

対称の位置の文字と比較することで, 各?が0,1,どちらでもよいの3パターンに分かれる.
確定の場所を更新した後, どちらでもよいのところを埋めれるかを判定すればよい.
https://codeforces.com/contest/1512/submission/156894237

D: Corrupted Array

取り除く項が決まった時, 残った項で最大の値が総和となる.
この時, 取り除いた項と最大の項以外の総和が最大の数となるかを判定すればよい.
毎回総和を求めるわけにはいかないので, 事前に全体の総和を求めて置き, 取り除くときに引くようにする.
https://codeforces.com/contest/1512/submission/156894697

E: Permutation by Sum

長さ  n の順列の, 長さ  k区間で作れる総和は  1+2+\dots+k 以上  (n-k+1)+(n-k+2)+\dots+n である.
よってまずこの不等式から判定問題を解くことができ, 構築可能の時, 大きい値から追加を試みて, 追加後も上記の不等式を満たすなら追加, そうでなければその数は追加できないとすればよい.
最後に関係ない項に残った数を押し付ければよい.
https://codeforces.com/contest/1512/submission/156895150

F: Education

最終的なポジションを全探索する.
最終的なポジションを決めた時, 昇格は出来るだけ早くした方が良い.
よって, 事前に各ポジションに到達するまでの最短時間と, その時に持っているお金を求めておく.
これはポジションの昇順に, そのポジションでお金を溜めて昇格試験を受けてというのをシミュレーションすればよい. 但し溜める際は計算によって, 一気に更新すること.
この前計算によって, 各ポジションに到達する時間とその時に持っているお金が定数時間で求まるので, そのポジションで不足分のお金を稼げばよい.
実際には前計算ではなく並行して計算した方が楽かもしれない.
https://codeforces.com/contest/1512/submission/156895535

G: Short Task

エラトステネスの篩のような感じで  10^{7} 以下の数の約数の総和を求めておく.
次に各総和となる値の最小値を全て求めておけば各ケース  O(1) で答えが求めれられる.
https://codeforces.com/contest/1512/submission/156896329

総括

43分全完0ペナ13位. 概ねヨシ. GでMLEかTLEヤバくないか?という疑念の元改善の考察をしてしまったのがややもったいなかった. 結果論だが一旦出してみても良かったかもしれない.

Codeforces Round #725 (Div. 3)(2022/5/12)

A: Stone Game

どちらも左から取り出す, どちらも右側から取り出す, 両側から取り出すを全て試せばよい.
https://codeforces.com/contest/1538/submission/157010040

B: Friends and Candies

飴の総数が人数で割り切れなければ答えは-1, 割り切れるならその値以上の飴を持っている人から徴収すればよい.
https://codeforces.com/contest/1538/submission/157010202

C: Number of Pairs

 i に対して,  l-a_{i}\le a_{j}\le r-a_{i} となる  j の数を数えた後, 重複分を取り除けばよい.
これは数列を昇順にソートしておけばlower_boundでできる.
https://codeforces.com/contest/1538/submission/157010346

D: Another Problem About Dividing Numbers

操作回数の上限は  a,b の素因数の指数の和である. 基本的には  k が上限以下ならば素数1つずつ割っていき, 操作回数が足りなくなりそうなら最後の2回でまとめて割って  a,b を共に1にすることができる.
 k=1 の時が例外で, 一方にしか操作を行えないので別で考える.
最悪の場合で  10^{4}*\sqrt{10^{9}} かかるので無理だと思い実際に出してTLEをしたので別方針を考えていたが, long longをintに直したら元のコードが通った. とほほ.
https://codeforces.com/contest/1538/submission/157014622

E: Funny Substrings

毎回マージを実際にしてカウントしていたら文字長が大変なことになる.
そこで, 各文字列の前後3文字ずつと内部に"haha"をいくつもつかを管理することにする.
すると元の文字列長が長くなろうとも持たせる情報は高々文字列種の定数倍である.
マージの時は, 各文字列の"haha"の数の和と, マージ時に新たに出来る"haha" の和をカウントすればよく, 後者は前半の後ろ3文字と後半の前3文字を実際につなげればよい.
https://codeforces.com/contest/1538/submission/157012847

F: Interesting Function

 f(l,r) を題意の関数とすると,  f(l,r)=f(0,r)-f(0,l) であるので  f(0,n) が求められれば良い.
0スタートにすると, 各桁の数が何回足されたかは単に10の冪で対称の数を割るだけで求めることができる.
https://codeforces.com/contest/1538/submission/157013131

G: Gift Set

 a=b の時はプレゼントが一種類なのでそのまま解けばよい. 以下  a\lt b,\ x\lt y を仮定する.
答えで二分探索をして判定問題を解く.
判定問題の答え候補を  k とする.
この時, 赤  a 個の方のプレゼントを  t 個作るとすると, 以下の不等式が得られる.
 \displaystyle 0\le t\le k,\ \frac{bk-y}{b-a}\le t\le \frac{x-ak}{b-a} これを満たす  t が存在するかをもって判定問題とすればよい.
https://codeforces.com/contest/1538/submission/157014366

総括

56分全完4ペナ位. Dで沼にハマった感じがする.

Codeforces Round #731 (Div. 3)(2022/5/18)

A: Shortest Path with Obstacle

A,F,B がこの順に同一直線状にある時のみ迂回が生じ, それ以外では最短経路でFを通らないものが存在する.
https://codeforces.com/contest/1547/submission/157580511

B: Alphabetical Strings

両端から大きい方の文字をとりのぞくというのを繰り返し, 除いた文字を逆順で観た時にabcd....となっていればよい.

C: Pair Programming

両者に対して貪欲に出来る操作があればするというのをすればよい.
途中で二人とも操作できなくなったら実行不可.
https://codeforces.com/contest/1547/submission/157581195

D: Co-growing Sequence

当たり前のことではあるが大事な性質として, 任意の  a_{i} に対して,  a_{i}& (a_{i+1}\oplus y)=a_{i} となる  y が存在するというものがある.
よって面倒な調整は全て後ろの方の項の任せていくことができる.
さらに上述の  y を最小にするには,  a_{i} で立っているかつ [tex; a_{i+1}] で立っていないbitのみ立てればよい.
https://codeforces.com/contest/1547/submission/157581720

E: Air Conditioners

右方向にしか冷やさない場合と左方向にしか冷やさない場合のそれぞれの気温を求めてそれらの小さい方の値を出力すればよい.
右方向にしか冷やさない場合を調べるには左から累積minのようなことをすればよい. 反対もほぼ同様.
https://codeforces.com/contest/1547/submission/157582113

F: Array Stabilization (GCD version)

最終的な数は全体の最大公約数になるので初めから最大公約数で割ってしまってよい.
各素因数ごとに独立にみる.
例えば2の倍数が丁度5つ並んでいる場所があれば, その場所を全て2の倍数でない数にするまでに5回の操作が必要である.
よって各素因数を持つものがいくつ並ぶかを見ればよい.
https://codeforces.com/contest/1547/submission/157583462

G: How Many Paths?

もっと上手い方法もあるだろうが, 自分はDFS+BFS+BFSで解いた.
DFSをして行きがけ途中に訪問済み頂点を再訪した場合閉路が存在するので-1である.
それ以外で再訪したら2, 1度も訪問しなければ0である.
但しDFSで全ての頂点にこの情報をいきわたらせるには何周もしないといけないので, ある頂点にのみまず記録をしておく.
DFSでこれを記録した後, 2と書かれた頂点からと-1と書かれた頂点を始点にそれぞれBFSをして, その子たちに情報を伝播させていく.
https://codeforces.com/contest/1547/submission/157584767

総括

61分全完5ペナ85位. ペナが多い.