精進メモ 2021/09/20~ - ツバサの備忘録

もうすぐ秋学期が始まりますね。夏休み返して…

AOJ-ICPC
Educational Codeforces Round 114 E. Coloring
Aizu Competitive Programming Camp 2021 Day 1
Aizu Competitive Programming Camp 2021 Day 2
ARC127
Aizu Competitive Programming Camp 2021 Day 3
ABC220

AOJ-ICPC

これまで通り下から埋めるか、星付きを優先するか悩みます。

2170 Marked Ancestor

後ろから見ると見通しがよくなるやつです。
クエリが起きたタイミングを管理して、葉からのぼりつつ処理します。
クエリが起きたタイミングが、今見ている頂点のマークされるタイミングよりも遅ければ、その頂点の値を加算します。そうでなければ親にまわします。
親に渡すパートはマージテクを使えばＯＫです。

2224 Save your cats

閉路がない = 木(森)である
ということが条件なので、コストの正負を反転してから最小全域木を作成していきます。使わなかった辺のコストの総和が答えです。

1318 Long Distance Taxi

燃料を補填できる都市同士を移動できるかどうかを、それぞれの都市を始点としたダイクストラで調べます。
その後、移動できる都市に辺を張りなおしたグラフで再びダイクストラすればいいです。

1244 Molecular Formula

頑張って構文解析します。
式全体は ()1 で囲んでるとすると実装が楽になるかも？しれません。

Educational Codeforces Round 114 E. Coloring

縦で見ると、黒白…と白黒…のどちらかを選択することになります。
$2^{M}$ 通りです。
横も同様ですが、全体が綺麗な市松模様になっている箇所が重複するので上手くひく必要があります。
また、隣接する2列が同じ並びになっているものが存在した場合、横方向で見ると黒黒、となっているため、一意に定まってしまいます。
そうなっていない行、もしくは列について、まだ確定していない部分の並びを決めていけば数えることができます(手抜きだと説明が難しいですね)。

Aizu Competitive Programming Camp 2021 Day 1

suzuken君、serpent君と3人で出ました。
ユナイトをしていたら開始まで残り5分になっており、チーム名が決まっていました。

E: ヘクト問題

$i$ 番目の数列の $j$ 番目の要素は、 $i \times j \mod{P}$ とすればよいです。
綺麗な性質がありそうだなと思っていたのですが、suzuken君が一言掛け算、と言ったのでこれを思いつきました。

F: SからTを作るやつ

操作2のみを繰り返して、長さを最大にしておきます。すると、0101...という文字列になります。この部分文字列であれば、任意の文字列をつくれます。

G: Round Tour

$dp[i][j] =$ 行きで $i$ 番目、帰りで最後に $j$ 番目を通り、 $1$ から $\max(i,j)$ 全ての頂点を通るルートにおける最小コスト
としてDPすればよいです。復元がバグっており間に合いませんでした。

H: TUAT文字列

子音 $p$ と母音 $q,r$ は全探索します。
これらを一つ決め打つと、作成できる文字列のパターン数は $_{4}H_{N-4}$ となるので、ここから、 $S$ より前、もしくは $T$ より後ろの文字列となっているものを数えればよいです。

Aizu Competitive Programming Camp 2021 Day 2

ICPCのチームで出ました。

B I am sleepy

$dp[i][j] = i$ 秒後に $j$ にいるような移動の方法のなかでの最適解
としてDPすればいいです。pairを持たせます。

D WeightedLIS

$dp[i][j] = i$ までみた時点で数列の最後の値が $j$ になっているときの最適解
としてDPすればいいです。セグ木で更新します。

G Tree Propagation

dfsしながら答えを計算していきます。
$N(N-1)$ から白い頂点の個数を引いていけばよいです。距離が $i$ の頂点については、自分の部分木について、距離が $2i,2i-1$ の頂点の個数だけ部分木サイズ分の答えを引きます。
最後に $N-1$ を引けばおしまいです。

K All Clear

それぞれのステージに対して、腕前が $X$ であったときにクリアできる回数の最小値を計算すると、 $X$ の増加に対して単調減少していきます。
この回数が切り替わるタイミングが答えの候補で、 $4N$ 回しかありません。
ので、 $X$ の降順でソートして逐一計算して、全探索すればＯＫです。

ARC127

Cの速度が…

A - Leading 1s

なんでもいいので実装できればいいです。がんばります。

B - Ternary Strings

先頭が0,1,2の文字列が $N$ 個ずつあります。先頭が2の文字列について、辞書順をできるだけ小さくするようにすればいいです。
そのためには、先頭以外の残りの部分を、3進数で $0$ から $N-1$ まで表現していけばよいです。
先頭が0,1については問題の条件を満たすよう適当に文字列を生成すればいいです。
先頭が2の文字列を作成した後、 $\mod{3}$ で1ずつ加算していくのが楽でした。

C - Binary Strings

上位ビットから見ていくと一意に定まります。よく見る問題。
引き算は遅延セグ木で実装しました。

Aizu Competitive Programming Camp 2021 Day 3

ソロ参戦でした。チーム戦にソロ参戦は夢でした。

B: Sufficient Condition

素因数が2個以上含まれているものがあれば、答えが存在します。
個数を半分(切り上げ)にしていけばいいです。

C: Separate Number

総和が $A_{i}$ になるまで $B_{i}$ の累積和を取っていく、という操作を繰り返していきます。
その区間ごとに答えを計算します。
場合分けが少々多いので注意します。

D: Successive Tree

頂点 $i$ が選ばれたときに足される距離の期待値を計算すると、あとは平均を取れば答えです。
頂点 $i$ について加算される距離の期待値は、 $[0,i)$ についての距離の期待値の平均 + 1になります。
あとは愚直に計算していけばOKです。

E: +- Switch

未証明です。鳩ノ巣っぽい問題なので、DFSで適当に調べたら通りました。

F: A2B

まずは、総和が変わらないことに気づきます。この手の問題は、何かが隣接swapになっていることが多いので頑張って探すと、累積和の隣接swapになっていることに気づきます。
あとは転倒数を計算すればおしまいです。

G: XOR Walk

$x$ と $y$ の距離が奇数であれば、合計が奇数個になるように頂点を選んだ総XORであればなんでも作れます。
偶数であれば、頂点を偶数個選んだ総XORであればなんでも作れます。
二部グラフでない場合は奇数と偶数のルート両方作れるので、なんでも作れます。奇数個、偶数個選んで総XORを最大化するには、 $2^{61}$ を全要素に追加して基底を求めると、 $2^{61}$ のビットが立っている場合は奇数個、そうでない場合は偶数個になります。
奇数個のパターンは、基底全体での最大値を求めればよく、偶数個は、 $2^{61}$ のビットが立っていない要素のみで最大値を求めればいいです。