cf #427 div2 D. Palindromic characteristics
問題ページ
Problem - D - Codeforces
問題概要
k-palindromeを以下のように定義する。
- 文字列の左半分と右半分が空文字列ではなく一致している
- 左半分と右半分がともに(k-1)-palindromeである
1-palindromeは通常の回文と同様である。
文字列sが与えられる。この文字列に含まれる連続する部分文字列においてk-palindrome(1<=k<=|s|)の数はそれぞれ何個あるか求めろ。
解法
dp[l][r] = (lからrまでの部分文字列で最大のk)とおいたDPを考える。
lからrまでの文字列がk-palindromeである条件はlからrまでの文字列が回文であり、左半分が(k-1)-palindromeであることである。したがって、小さい幅の部分文字列の情報を先に得たいため、小さい幅のものから順番に計算していく。
l = r のときは明らかにdp[l][r] = 1
l = r-1 のときは s[l] = s[r] ならば dp[l][r] = 2、s[l] != s[r] ならば dp[l][r] = 0 となる。
これ以外のときは
- s[l] != s[r] または dp[l+1][r-1] であれば回文にはなりえないため dp[l][r] = 0
- それ以外の場合、左半分のdpの値+1が求める値になるため dp[l][r] = dp[l][m] + 1 (ただし m = ceil((l+r)/2) - 1）
となる。これはO(|S|^2)で計算できる。
ここでk-palindromeは(k-1)-palindromeでもあることを利用すると、k-palindromeの数はdp[l][r]の値がk以上の個数であると言える。cnt[k] = (dp[l][r] = kの数) として、後ろから累積和を取ることで、各k-palindromeの数を求めることができる。
cf #427 div2 C. Star sky
問題ページ
Problem - C - Codeforces
解法
t秒目での各星の明るさは(s[i]+t) % (c+1) で求められる。星の明るさは周期c+1で同じものが現れるのでc+1回分2次元累積和を取っておいて各クエリにO(1)で答える。同じ地点に複数の星が存在するケースがあることに注意。
cf #426 div2 B. The Festive Evening
問題ページ
Problem - B - Codeforces
解法
各文字について最初に現れるタイミングと最後に現れるタイミングを調べてimosする。
cf #426 div2 A. The Useless Toy
問題ページ
解法
操作には周期4の周期性があるので周期性を使って判定する。
ARC079 F Namori Grundy
問題ページ
F - Namori Grundy
解法
0以上a[i]未満の整数xが頂点iから辺が伸びている頂点jの値a[j]として全て使われているようなa[i]の決め方をする。
すなわち、a[i]から辺が伸びている頂点jの値として使われていない最も小さい値がa[i]の値となる。
サイクル以外の頂点の値a[i]は葉から順番に見ていくことで簡単に決められる。
サイクル上の適当な頂点を一点取ったとき、その頂点が取りうる値は、
- その頂点に辺が入る頂点の値として使われていない最も小さい値
- その頂点に辺が入る頂点の値として使われていない二番目に小さい値(サイクル上で頂点iに入る辺を持つ頂点jが最も小さい値を取る場合)
の2つしかありえない。
サイクル上の1頂点の値が決まればサイクル上の残りの頂点の値も順に決まっていく。この2パターンで成立するものがあれば"POSSIBLE"、なければ"IMPOSSIBLE"となる。
学んだこと
なもりグラフでサイクル外の頂点だけを探索する方法
grundy数の定義
ARC079E Decrease (Judge ver.)
問題ページ
E - Decrease (Judge ver.)
解法
a[i]がn以上であればn未満になるように引き、数列の他の要素に適切な値を加えることを繰り返した。
最初からn未満になるように操作すると途中で遷移がバグってるところがあったので一回 7*n 未満になるように操作したあと n未満になるように操作したら通った（ア
正当性の証明を一切してないすごい怪しいコードになった。
