参加しました Codeforces CodeTON Round 3

記録

Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

4完, 約11000人中704位でした Eは10分間に合わなかった…
Dに時間を使いすぎたのは反省.

解法・反省

A

Problem - A - Codeforces
提出 5分 (0)

解法

解法

まず, だともう動かすことはできないのでダメ. は必要.
コンテスト中は十分かどうか判定できなかったが, よく見れば なら を 選ぶことでソートすることが可能.

提出

Pypy3 Submission #179561678 - Codeforces

B

Problem - B - Codeforces
提出 8分 (0)

解法

解法

substring の定義はいわゆる連続部分列のことを指している.
条件を見ると, の場合 がコストになるので, この場合 はともに多い方がうれしい. よって何もしない場合が答えの候補になる.
そのほか の場合は, 連続する の個数が多いほどうれしい. よって, 連続する の個数の最大値が答えの候補になる. も同様.
の含む の個数を , の個数を とする.
連続する の個数の最大値を , の個数の最大値を とする.
このとき が答え.

提出

Pypy3 Submission #179565507 - Codeforces

C

Problem - C - Codeforces
提出 36分 (0)

解法

解法

操作は可換であることがすぐにわかる. あと, 2回同じ操作をすると元にもどる.
だから, 数列の組 が達成可能なとき, 一回操作をした後の数列の組 も達成可能である. 数列の組の間に同値関係がうまれている.
がすべて のとき, 達成可能な は, か, の2種しかない.
よって, 何回か操作することで の要素を全部 にしてみて, その後の の様子を見ればよい.

を全部 にする方法はどうするか？
ぼくは なら とすることで他に影響を与えずに にすることができると気づいた.（1個だけ余ったときはちょっと複雑）
他には, たとえば左から潰していく戦法で
→ →
→ →
→ →
→ →
→ おしまい
って感じにやるとできるが, 少し計算量削減が必要になる.

提出

Pypy3 Submission #179600405 - Codeforces

D

Problem - D - Codeforces
提出 1時間20分 (0)

解法

解法

40分近くかけてしまい、反省…
まず で, が成り立つので, である.
つまり, は の約数になってないといけないということである.
この条件を満たしてない時点で答えは . また, は明らかである.
を考えよう. であることが必要十分. ここから が導かれるので, 全部 で割っちゃえば, とすれば, となる. これを満たす整数 () を数え上げればよい.

これには約数系包除が有用. を, ちょうど となる の個数とすれば, であるから, の約数だけを数え上げればよい.
となる の個数は 個. そこから, となる について, を取り除くので, が求められる.
あとは を取り出せばよい. これを繰り返すことでok.
最後は計算量だが, 高度合成数とかの議論で 以下の約数の個数の最大値を とすると, 各計算 . いま なので, から全体 .

提出

Pypy3 Submission #179615045 - Codeforces

E

Problem - D - Codeforces
提出 コンテスト後

解法

解法

10分遅れてしまった…
カッコ列のコストを見ていく. カッコ列に内蔵する正しいカッコ列の要素はもう触らないでok. よって, カッコ列から '()' を除くことを繰り返す. そうすると, ')))))((((' みたいな文字列ができる.
')(' に操作をして消滅することを繰り返し, 余ったやつは補完していく. カッコ列から '()' を除くことを繰り返すした後の '(' の個数を , ')' の個数を とすると, コストは .
もともとのカッコ列には消された '()' の要素があった. この数を とする. また, もともとのカッコ列の'(' の個数を , ')' の個数を とする そうすると, となる.
この をすべての の連続部分カッコ列に対し求めるのがこの問題になる.
については, 主客転倒が効く. いいカッコ列(高さが同じ)のペアについて, それを含む連続部分列の個数を数えるのは容易である. 左側を , 右側を とすれば である. そういうペアは 個以下なので, ok.
が問題だが, に対して , に対して を計算すればよい.
これは個数とから までの各の値, 各の値の総和を管理する BIT (もしくは segtree ) を使えば, 高さによって と の大小が違うので, 求められる.

提出

Pypy3 Submission #179684054 - Codeforces