仮のブログ

仮です

2023/5/25~2023/5/31

2023/5/25 (木)

7:30起床. あさかつARC.

A: D[i]=#{(B,C)|B*C<=i} を累積和使って求めて置いて, Σ(D[K/A]) をする.
B: x=A/2 を全探索
C: 答えで二分探索
D: Qが奇数なら1回愚直に操作してQ:偶数にする. 操作を2回まとめると単にrotateになるので計何回rotateするか計算する.
E: xを右にずらしたときに答えが増える間右にずらす

その後は先週出れなかった一限のオンライン講義. これは数学の講義を英語で受けてみようという趣旨のもので元は留学生向けの講義であるが, 誰でも受けられる.
代数学, 幾何, 解析の3パートに分かれており, 今日は代数の最終回であった. 内容としては素数定理周りで, 後でちゃんと自分で手を動かさないと実感が無いというのが正直なところである. 課題も出たことなので時間のある時に色々いじるつもり.

その後昼寝をしたのち, こどふぉのバチャ.
https://codeforces.com/contest/600

A: Extract Numbers

正規表現で殴れるのかな?
分からんかったので前から文字列を愚直に舐めていった.
https://codeforces.com/contest/600/submission/207117620

B: Queries about less or equal elements

二分探索や尺取りなりをするだけ. なるほどEducationalって感じ.
https://codeforces.com/contest/600/submission/207117807

C: Make Palindrome

最終的に並べ替えるので, 各文字の出現数だけ記録しておけばよい.
奇数登場する文字の種類を,  c 種類とすると, 変更回数の最小値は  \lfloor \frac{c}{2}\rfloor 回である.
この時, できるだけ大きい文字を小さい文字に変更するのが良い.
文字を変更した後は貪欲に辞書順最小を構成.
https://codeforces.com/contest/600/submission/207118272

D: Area of Two Circles' Intersection

数学をして, 交わらない, 内包, その間それぞれで計算をする.
途中謎にlong long で計算してしまってペナを多数吐いてしまった.
https://codeforces.com/contest/600/submission/207120054

E: Lomsat gelral

各部分木毎に, 各文字の出現回数とその最大値等を記録していきたい.
しかし, それをするとマージの際に計算量が大変なことになる.
そこで, マージテクをする.
各頂点に記録を残していくのではなく, 各頂点の記録がどこに保管されているかをメモっておけば, 毎回コピーせずにその記録をいじることができる. よって, 子の記録のうち, 要素数が最大のところにその他の子の記録を追加していって, 最後に自身の記録がその子のところにある旨を保持しておけばよい.
https://codeforces.com/contest/600/submission/207124239

F: Edge coloring of bipartite graph

次数の最大値が答えになるのは知っているのが, 如何せん二部グラフの辺彩色の実装が面倒くさくて投げ出してしまった. いつかはちゃんとやります......

総括

5完5ペナ8位. みんなDでペなりまくっていた.

夜はOMCに出た.

A

一瞬ぎょっとしたが,  x\in \mathbb{Z} が不適なため,  \frac{n+1}{n}\le\frac{2357}{2345} を考えればよい.

B

最後に残った数を  (0,k) とすると, その直前は  (k,k) に限られ, さらにその前は  (k,2k) に限られる.
その前は2通りあり,  (k,3k),(2k,3k) のどちらか.

C

 AE,AF を延長して角度を追うと,  AE=AF が出るので, 角度が全て求まる.
角度が出てしまえば, 三角関数で殴りやすい.

D

 a_{1}=\frac{p}{q}(a_{2}+a_{3}),  a_{1}+a_{4}+a_{7}=S とすると, 条件式を全て足して  S=\frac{45p}{p+q} が得られる.
 S の範囲や,  S\in \mathbb{Z} を使って候補を絞る.

E

 f(1),f(2),f(3),f(4),f(9) はすぐに出る. ここで実験から  f(8)=8エスパー. すると, 総和の条件から残りはほぼ決まる.

F

時間内に解けなかった.

総括

5完2ペナ29位. 久しぶりにしては健闘できた.

2023/5/26 (金)

7:30起床 あさかつARCに出た.

A:  A,B をどっちも全探索.
B: 上の桁から決定.
C: どーせ片方  (1,2,\dots,N) でいいだろ→ACしたので証明完了をした.
D: 二回操作しても, 一回の操作で代替できる. よって, 操作は一回のみとしてよく, 各bitの寄与で求まる.
E: 場合分けを頑張る.
F: 数十分遅れでAC.

日中は昼寝や数学をしていた.

夜になって, 一昨日までにやらなければいけなかったタスク(電気代振込)があったことを思い出したので慌てて深夜徘徊にでた.

帰宅後はこどふぉバチャ
https://codeforces.com/contest/1622

A: Construct a Rectangle

いくつかパターンがあるので丁寧に場合分け.
https://codeforces.com/contest/1622/submission/207365340

B: Berland Music

誤読してかなり時間がかかった.
読解をちゃんとやれば座圧的な事をするだけであった.
https://codeforces.com/contest/1622/submission/207367520

C: Set or Decrease

 a を単調非減少としてよい.
デクリメントは,  a_{1} のみにすれば良い. それ以外は  a_{1} への置き換えの方が真に強い.
また, 置き換えは大きい方から順にやるのが最適.
ここまでくれば, 置き換えを何回するかで全探索という方針が立つ.
累積和をもっておけば, 置き換え  x 回の時の,  a_{1} のデクリメント必要回数が求まる.
https://codeforces.com/contest/1622/submission/207368633

D: Shuffle

 1 が少ない場合答えは  1.
そうでない場合,  1 が丁度  k 個ある区間の条件は,  1 が丁度  k 個以下の区間へと変えられる. (適当に両側を伸ばして k 個含むようにしてその部分を動かさなければ良いので)
ここから重複を取り除くために, 区間の両端は必ず変更するという制約を付ける.
これで過不足なく数えられる.
後は二項係数とかで.
https://codeforces.com/contest/1622/submission/207371436

E: Math Test

絶対値の条件が厄介なので, bit全探索でこれを外す. すなわち, 生徒を二つの集合に分けて, 高得点を目指す集団と低得点を目指す集団にする.
すると, 高得点を目指す集団への得点の寄与-低得点を目指す集団への得点の寄与が大きいところに高い配点を割り当てればよい.
https://codeforces.com/contest/1622/submission/207372932

F: Quadratic Set

分からーん

総括

ooooo- 128位.
Bが10分早く解けていれば順位が50上がっていたらしい.
こどふぉのシステム的に前半で詰まると影響が大きい.

2023/5/27 (土)

7:30起床, あRC.
今回からあさかつdiscordサーバーにお邪魔しているので感想はそちらに書いているのをコピぺ.

ooooo- 31:57
1: 左上から貪欲に, 4近傍で使ってない色を塗っていく.
2:  a+b の値で全探索.  a+b=k の時,  a の範囲は \lbrack\max(1,k-N), \min(N,k-1)\rbrack.
3:  10^N 未満でどの桁も同じ数は  O(N) 個だけなので全探索できる.
4: 上の桁から決める. その数にするために各  A_i に加算する必要数を  C_i として  C の小さい  K 個の値が  M を超えないならそのbitを採用.
5: 繰り上がりを考慮しない桁和の和を求めて, 繰り上がりの回数だけ9を引く.
各桁毎での繰り上がリの回数を求める.
6: 区間スケジューリングぽくなる気がしたけど上手くできなかった 出来ました(+30分, 嘘解法感有).

その後昼寝をしたら15時過ぎまで爆睡してしまった.
起床後目覚めのこどふぉばちゃ.
https://codeforces.com/contest/1644

A: Doors and Keys

前から持っている鍵の管理をしていく.
https://codeforces.com/contest/1644/submission/207440032

B: Anti-Fibonacci Permutation

フィボナッチになっている箇所がある数列が割合としてかなり少なそうだったのでランダムに順列を作ってチェックをした.
手元でやったら高速だったので提出 https://codeforces.com/contest/1644/submission/207440891

C: Increase Subarray Sums

まず区間 d 毎に, 区間和の最大値  M_{d} を求める.
 f(k)=\max_{1\le d\le N}\lbrace M_{d}+x\times\min(k,d)\rbrace である.
https://codeforces.com/contest/1644/submission/207441777

D: Cross Coloring

操作を逆順に見ていくと, そこで塗った色が最後まで露出するか否かが分かる.
露出する色数が分かれば後はべき乗するだけ.
https://codeforces.com/contest/1644/submission/207442682

E: Expand the Path

対称性があるので最初に右に進むとする.
すると, 右移動を伸ばすのは, 最初の右移動の時のみとしてよい.
同様に, 下移動を伸ばすのは最初の下移動の時のみとしてよい.
すると後は座圧して寄与を求めるだけだが, これが添え字バグらせ祭りで大変.
https://codeforces.com/contest/1644/submission/207448086

総括

oooo1- 118位.

夜はABC303
https://atcoder.jp/contests/abc303

A: Similar String

頑張って全ての場合を尽くすように書く.

B: Discord

各写真で隣り合っているペアを記録していく. 制約的に  O(N^{3}M) でも通るので何しても良さそう.

C: Dash

setでアイテムを管理して移動をシミュレート.

D: Shift vs. CapsLock

DP[何文字目まで見たか][Capsの状態]=最小回数

E: A Gift From the Stars

レベル3以上の頂点を取り除く→残った(次数  1 以上の頂点からなる)サイズ  n の連結成分は元々 n//3 個のレベル  2

F: Damage over Time

逆から見ると,  y=ax y=b みたいなグラフの集まりで各  x での最大が欲しくなるので最大が切り替わる場所を求めてその区間での総和を求めて.......を丁寧にする. 添え字で頭が壊れる~~

G: Bags Game

Exの方が解けそうだったのでそっちへ

Ex: Constrained Tree Degree

知識ゲーとして求める式を閉じた形に持っていけるので後はFPSをすれば良い.

総括

oooooo-(1o) 46位!! 自己ベストに近い順位で良きかな良きかな.

2023/5/28 (日)

この日はARCの記憶が強すぎて後日この日の行動を思い出そうとしてもARCのことしか思い出せなかった.

夜はARC161

A: Make M

偶数番目に小さいのを, 奇数番目に大きいのを並べる.

B: Exactly Three Bits

もし  N にbitが  3 つ以上たっていれば, 上  3 つを残して後全部  0 にするのが最適.
そうでない場合, 上に帰着されるまで  N をデクリメント.
デクリメントは雑に見積もっても  7 回で終わる.

C: Dyed by Majority (Odd Tree)

適当に根付き木とする.
葉から順に見ていき, 色がどちらかに確定するかしないかを追っていく.
子の内, 自身の色で塗られた頂点数と, 未確定の頂点数の和がその他より

  • 真に大きければ, 親への制約はない.
  • 等しければ, 親は自身の色で塗らなければならない. (そして矛盾が生じたら塗分け不可)
  • 小さければ塗分け不可

である.
実装ミスでペナと時間をとられたのが痛い.

D: Everywhere is Sparser than Whole (Construction)

完全グラフより辺数が多いのは不可.
そうでない場合, 適当に対称的にやれば通りそうで実際通る.

E: Not Dyed by Majority (Cubic Graph)

これが解けたのが全ての勝因.
まず答えが存在しない場合があるかを考えた.
操作を,  \lbrace 0,1\rbrace^{N} (操作前の色を  0,1 に対応) から  \lbrace 0,1\rbrace^{N} (操作後)への写像  \sigma と思うと, これが全射ですか? (全射じゃないなら像に入らない元はどれですか?) という問題になる.
これは濃度の等しい有限集合間の写像なので, 単射性を調べればよく, 単射性を満たさないことは  \sigma(0,0,\dots,0)=\sigma(1,0,\dots,0)=(0,0,\dots,0) から直ちに分かる.
ここまで考えた段階で, 私は像では  0,1 の分布が偏るのでは? という推測を立てた. 例えば, 元々  0 3 個で  1 100 個あれば  \sigma で送った時に  0 が減る傾向にあるだろうということである.
証明は大変そうなので, 適当なグラフを作り,  \sigma(\lbrace 0,1\rbrace^{N}) の元で,  1 の数が  \frac{N}{2} となるものの数を数える実験をした.
すると, 出現率はかなり低くいという事が分かった.
よって, 乱択すれば結構な確率で像に入らないようにできることが分かる.

後は高速に判定問題を解くだけである.
これについては, 実際に手作業で  \sigma の適当な元の逆像を求めようとして気が付いた.
ある頂点が  1/0 の時, その隣接頂点 3 つのうち, 任意の  2 つ組について, 少なくとも一方が  1/0 である必要があり, 逆に全ての頂点でこのような制約が満たされれば, それは逆像の元となりうる.
これはまさに  2 SATになるので  O(N) で判定問題が解ける.

こうして, 乱択をして  2 SATで判定をしてを繰り返せば良いことが分かった. (  N=4 の時は別処理した)

総括

oo(3o)oo 24位(2190→2306)

  • 自己最高順位更新
  • 自己最高パフォーマンス更新
  • コンテスト中AC最高diff更新
  • 自己最高レート更新
  • 初赤パフォ

最高である. 先週のAGCで水パフォをとってレートを70近く溶かしていたのを大きく取り返した.
その後twitterで嬉しさを放流した後就寝. (後日一部のツイートは喜びがうるさかったので消した.)

2023/5/29 (月)

7:30 起床, あRC.
o(3o)oo--
1:  M=2N
2: めっちゃ時間かかったうえ境界をバグらせ3ペナ
3: 差%3==0なら(差)/3
4: 縦横それぞれいくつ以上減らす必要があるか求める
5: 大変だった記憶があったのでパス
6: (5分遅刻)bit毎に見てよく, すると双方に何回寄与するかが分かる.

その後, 奨励賞の授与式のためスーツを着て大学へ向かう.
普段私服で行くところに違う格好で行くのは結構新鮮だった.
早く着きすぎたので, 薬学部の方を散歩してみた. 薬学棟に近づくにつれて薬局のにおいがしてなるほど薬学部だとなった. 気のせいかもしれない.

授与式自体は賞状を受け取って写真を撮った後軽く歓談をする簡単なものだった.
会話を切り出す人が少なかったのであのような場面ではもっと自分から話を振るべきだったと反省.

授与されるのはせいぜい賞状くらいだろうと思っていたが, 色々もらえたので嬉しかった. 特に, プリンストン数学大全(1000頁を超える網羅的な全ジャンル数学書)を頂けたのが嬉しい. 読み物として面白いものなのでちょっとずつ読んでいきたい.

2023/5/30 (火)

8:30 起床. 2限のため大学へ向かう.
今日は代数幾何の講義で, 層係数コホモロジーの準備. このあたりの話は存在だけ聞いたことがありそろそろ手を付けようと思っていた話題なので楽しみ.

午後は控室で友人と駄弁りながら数学をし, その後サークルの定例会のために川内へ下山.

今回のボス問( https://atcoder.jp/contests/arc114/tasks/arc114_e ) バチャ中はしばらく考えたが上手く整理できなかったが, 考えていて面白い問題であった.

夜はこどふぉのバチャ.
https://codeforces.com/contest/1821

A: Matching

先頭の桁は 9 通り, それ以外は  10 通りの場合寄与がある.
https://codeforces.com/contest/1821/submission/207863266

B: Sort the Subarray

絶対に含まないといけない区間をまず求める.
これは, 元と後で異なるindexの最大, 最小を求めればよい.
その後は, 前後の境界を伸ばす作業に入る.
これは, 伸ばせるだけ伸ばしていけば良い.
https://codeforces.com/contest/1821/submission/207863595

C: Tear It Apart

最後に残す文字を決め打ちすると, その文字で文字列を分割した後, 各文字列について問題を解けば, 全体の答えはそれらの最大値となる.
文字列  s に関しては, 一度の操作で  \left\lceil\frac{|s|}{2}\right\rceil だけ文字が消せる.
https://codeforces.com/contest/1821/submission/207864099

D: Black Cells

最初に, 重なっている区間を一つの大きな区間にして扱い易くしておく. (後から気づいたが制約で重ならないようになっていたのでこれは不要だった. )
すると, 各区間

  • 先頭から途中まで塗る
  • 全て塗る
  • 塗らない

のいずれかとなるが, 途中まで塗るのは最後の位置区間のみ, 道中で区間が2マス以上ある場合, 全て塗るとしてよい.
よって, 1マス区間の個数を持ちながら, その区間で塗り終わる場合の最小コスト(あるいはその区間では塗り終えられない)を計算すればよい.
https://codeforces.com/contest/1821/submission/207868238

E: Rearrange Brackets

まず初期状態で, どの括弧とどの括弧が対応し, その括弧の内側にいくつの括弧があるかを計算する. これはstackを使えばできる.
その後の操作フェーズでは, 内側に括弧が多く入っている対の, 閉じ括弧を開き括弧の直右にもってくれば良い.
https://codeforces.com/contest/1821/submission/207869463

F: Timber

二乗の包除原理の形になって困ってしまったので就寝した.

総括

ooooo- 52位.
5完内最速だったらしい.

2023/5/31 (水)

8:00 起床即朝活ARC.
o-oo-o
1: 答えが高々Nlog(max(A))なのでシミュレーションできる.
2: 時間かかりそうなのでパス. (終了後AC. 答えの桁数を決めると, 周期させる整数の桁数はその約数で, Nのprefixかそれ-1のみを考えればよい. ←よく考えたら答えの桁数候補len(  N )かlen( N )  -1 だけでした......)
3:  0 -1 にして累積和のrange
4:  X,Y A [0],  B [0]の約数なので先に決め打ち
5: 時間かかりそうなのでパス2
6: 連結の場合: 全域木をとると,(各辺を残すかは葉側から貪欲にきまるので)奇数次数頂点集合が実現可能かは集合サイズのパリティのみに依存するので残った辺は先に自由に決めちゃってOK.→ 一般の場合: 連結成分毎考えて畳み込み

4に関して, 割り算多いわりに計算量結構攻めてるねという話になり, 確かにとなった. 実際自分提出は毎回割り算するもので, 1500ms/5000ms かかっていた.
ここで割り算の大半は前計算できることに気が付いたので, ものは試しということで, こちらのバージョンも書いて見たところ 245ms/5000ms まで早くなりびっくり. これなら大抵の言語でも問題なく通りそうである.

その後は昼寝をしたのち, 本日までの課題をした. 課題内容は素数定理リーマン予想の帰結について調べるもので, 先日いただいたプリンストン数学大全を早速活用した. 活用したいを優先した結果若干本旨と外れてしまった気もするがご愛嬌ということにした.

その後はセミナーの準備をして就寝.

追記

二週目にして早速下書きのまま公開を忘れていたらしい.