ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

精進メモ 2021/06/14~

久々にきちんと月曜に記事を作成した気がします。

Binary Trie

ARC122のDで貼るだけと言われたので早速作成です。
Trie木はいままでフルスクラッチで書く派だった上、BinaryTrieの問題をそこまで解いたことがない気がする?ので、どのような構成にすればいいのかあんまりわからずです…

Submission #23466114 - Tokio Marine & Nichido Fire Insurance Programming Contest 2021(AtCoder Regular Contest 122)

https://judge.yosupo.jp/submission/50358

ZONeエナジー プログラミングコンテスト “HELLO SPACE” F - 出会いと別れ

提出 なんでコンテスト中解けなかったのかびっくりするくらいシンプルですね。AtCoder Problemsをなんとなく開いたら、黄diffでACしていなかったのがこの問題だけだったので、久々に典型90以外での精進です。
基底を取ると、その部分集合の総xorが、"可能な辺を張った場合に"0から行ける場所になります。
基底を取る時、その元となった値を記録しておき、それらと、0,1,\ldotsのxorを取ってUnionFindで全域木を作成していけば良いです。辺がN-1本になっていれば成功です。
0,1,\ldotsを、Aにして1ペナです。

典型90

066 - Various Arrays(★5)

1 \leq i, \lt j \leq Nとなる(i,j)すべてについて、ありうるパターンを全部試せばよいです。
それぞれで転倒数が1加算される確率を求め、その和を取れば答えです。

067 - Base 8 to 9(★2)

素直に8進数を10進数に直し、それを9進数に直す方法を取ります。
N=0になるパターンで2ペナしました…

068 - Paired Information(★5)

A_{i+1} = V - A_{i}なので、 X_{i}の偶奇どちらか一方の場合はV-1倍します。
すると、BITで管理して区間和取れば答え求められます。
いろいろバグらせて2ペナしました。

069 - Colorful Blocks 2(★3)

(K-2)^{N-2} (K-1)Kが答えです。
Nが2と1の場合はそれぞれ(K-1)K,\,Kになるので注意です。

070 - Plant Planning(★4)

X,Y座標独立に考えることができます。
選ぶべき点は中央値です(偶数の場合はどちらでもいいです)。
あとは愚直に計算します。

071 - Fuzzy Priority(★7)

1ペナ。
素直にDFSをすればよいです。今使える頂点のリストをセットで持っておき、その中から1つ選んで次に進みます。

ABC 206

途中まで1ページ目ワンチャンあるなぁと思っていましたがさすがに最後は順位が落ちました。

D - KAIBUNsyo

これDにあるの結構びっくりしました(まぁ解法的にEにおけるかと言われると…?)。
前からi番目と後ろからi番目の文字を辺で繋ぐことを考えます。
連結成分については、最終的に全て同じ文字になっている必要があります。
すると、最低でも(連結成分 - 1)回操作をすると、その連結成分の文字を揃える必要があります。なので、それぞれの(連結成分 -1)を足したものが答えになります。

E - Divide Both

脳みそ破壊されるシリーズです。
gをまず固定します。
このとき、x/gy/gの公約数がhとなっているような(x,y)の選び方は包除原理で求めることができます。
欲しいのはh=1のパターン数です。hが大きい方から計算していくと楽に計算できます。
そして、このときにx,yのどちらかが1になっているものを引きます。
あとはこれを全てのgについて求めればよいです。

F - Interval Game 2

知識ゲーと典型を組み合わせているので、こちらの方がサクっと解けました。面白かったです。
ある区間が残っているとき、選べる区間は最初から決まっています。
それぞれの区間を選んだ時のグランディ数を求めることができれば、今見ている区間についてのグランディ数も求めることができます。
選ぶ区間を一つ決めたとき、今見ている区間は2つ(1つの場合もありますが)に分かれます。
それぞれについて、次のターンからは好きな方を選べるので、分けた区間それぞれのグランディ数を求め、そのxorを考えます。これが、今選んだ区間についての遷移先のグランディ数になります。
あとは、それを選べる区間それぞれについて求めれば、定義通り計算できます。
グランディ数 + 区間DPです。