Codeforces Round No.602 Div.2 D2復習
コンテスト中に解けなかったものの復習です。
いろいろな解法（というよりも解くために用いるツールが多様）がありますが、 BITを使った方法が一番自分にとって与し易かったため、BITで解きました。
D2. Optimal Subsequences (Hard Version)
問題
n 要素からなる数列 A が与えられる。
この数列に対して部分列（間の要素を好きなだけ削除し、残ったものの順番を変えずに得られる数列）を考える。
ある部分列の長さ k が与えられたとき、以下の条件を満たす部分列はoptimalであるという。
- 考えられる長さ
kのあらゆる部分列の中で、部分列の要素の総和が最大となる。 - 1の条件を満たす部分列の中で、元の数列の位置に関して辞書順最小である。
一方で、 m 個のクエリが与えられる。
各クエリは k, pos の2つの1以上の整数からなり、このクエリに対して、
「長さ k のoptimalな部分列における pos 番目の値」を答える必要がある。
すべてのクエリに対して、それらの順番どおりに答えよ。
制約:
1 <= n, m <= 2*10^51 <= A[i] <= 10^91 <= k <= n, 1 <= pos <= k
解答
Easyバージョンは制約が小さいため、愚直な解法で通りますが、こちらは賢くクエリを処理する必要があります。
まず整理すると、
1の条件よりoptimalな部分列は、元の数列を降順にソートしその先頭 k 個の数を選択したものとなります。
ただし、2の条件より、同じ要素が元の数列に複数存在する場合、できるだけ元の数列において前の方の位置に登場したものを優先的に選ぶ必要があります。
よって、元の数列 A を、まずは要素の大きさを基準に降順となるようにし、値が同じ場合は元の数列における位置に関して昇順となるようにソートします。
各クエリに答えるためには、まずこのソートした列に対して、先頭の k 要素を取得します。
そして、取得した k 要素の中から、位置に関して pos 番目に小さい要素の値を出力すればOKです。
ただし、これを愚直に行うためには、 k 要素取得するたびにそれらを位置に関して昇順ソートする必要があります。
これは許容できないため、工夫が必要です。
まず、クエリをすべて先読みし、 k が小さい順に答えていくという工夫ができます。
こうすることで、（許されるなら）ソートしたい集合が、単純に新しい要素がappendされていくだけとなり、シンプルになります。
しかしながら、それでも k が大きくなるたびにソートするわけには行かないため、
「要素の追加」と「特定の順番の値の取得」を高速に行う必要があります。
このような操作は「BIT上の二分探索」を活用することで可能なため（詳しくは後述）、各クエリを O(logn) で処理できます。
よって、全体で O(m*logn) で解くことができます。
※1500msecぐらいかかりました。
※Sorterがうざったいかもしれませんが、AtCoderと共通化したいため、このようにしています（こどふぉのGoはバージョンが新しいので実際はもっとスマートに書けるはずです。）
var n int var A []int var m int type BinaryIndexedTree struct { bit []int n int minPow2 int } // n(>=1) is number of elements of original data func NewBIT(n int) *BinaryIndexedTree { newBit := new(BinaryIndexedTree) newBit.bit = make([]int, n+1) newBit.n = n newBit.minPow2 = 1 for { if (newBit.minPow2 << 1) > n { break } newBit.minPow2 <<= 1 } return newBit } // Sum of [1, i](1-based) func (b *BinaryIndexedTree) Sum(i int) int { s := 0 for i > 0 { s += b.bit[i] i -= i & (-i) } return s } // Add x to i(1-based) func (b *BinaryIndexedTree) Add(i, x int) { for i <= b.n { b.bit[i] += x i += i & (-i) } } // LowerBound returns minimum i such that bit.Sum(i) >= w. func (b *BinaryIndexedTree) LowerBound(w int) int { if w <= 0 { return 0 } x := 0 for k := b.minPow2; k > 0; k /= 2 { if x+k <= b.n && b.bit[x+k] < w { w -= b.bit[x+k] x += k } } return x + 1 } func main() { n = ReadInt() A = ReadIntSlice(n) m = ReadInt() // クエリを先読みしてkで昇順ソート L := make(QueryList, 0) for i := 0; i < m; i++ { k, pos := ReadInt2() L = append(L, &Query{id: i, k: k, pos: pos}) // idは0-basedで格納 } sort.Stable(L) // Aを値で降順→位置で昇順にソート S := make(ElementList, 0) for i := 0; i < n; i++ { S = append(S, &Element{val: A[i], pos: i}) // posは0-basedで格納 } sort.Stable(S) // BITをOrderedSetとして扱う bit := NewBIT(n) ck := 0 // クエリの回答保持用 answers := make([]int, m) // クエリをkの小さい順に処理していく for i := 0; i < m; i++ { q := L[i] // BITに格納した要素数がk個になるまで追加する for ; ck < q.k; ck++ { e := S[ck] bit.Add(e.pos+1, 1) } // BIT中のpos番目を回答する ans := bit.LowerBound(q.pos) answers[q.id] = A[ans-1] } // まとめて回答 for i := 0; i < m; i++ { fmt.Println(answers[i]) } } type Query struct { id, k, pos int } type QueryList []*Query func (l QueryList) Len() int { return len(l) } func (l QueryList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l QueryList) Less(i, j int) bool { return l[i].k < l[j].k } type Element struct { val, pos int } type ElementList []*Element func (l ElementList) Len() int { return len(l) } func (l ElementList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l ElementList) Less(i, j int) bool { if l[i].val > l[j].val { return true } else if l[i].val < l[j].val { return false } else { return l[i].pos < l[j].pos } }
BITを使って k 番目の要素を取得するテクニック
今回行ったような操作は競技プログラミングにおいては典型テクニックのようで、 例えばけんちょんさんのQiitaの記事などでも 詳しく解説されています（他にも色々わかりやすくまとめている方がたくさんおられました）。
今回は、位置に関してBITで管理するため、要素数の制約から座標圧縮する必要はありませんでした。
BIT上の二分探索とは？
hosさんのBIT解説PDFにおいて最後の方で説明がなされています。
。。が、自分には最初何をやっているのかよくわかりませんでした。
自分なりに議論を補間しつつゆっくりと追っていくと理解できたので、忘れた頃の未来の自分を第一の対象として、理解の道筋を残しておこうと思います。
まず、「BIT上の二分探索ってそもそも何？」となってしまいましたが、これは「元の配列の先頭からの累積和に関する二分探索」となります。
別の表現をすると 「1-basedなインデックス i で、 [1, i] の要素の総和が w 以上となる最小の i を探索する」 といえます。
二分探索自体の計算量が対数オーダーで、BITを使って累積和を求めるのも対数オーダーであるため、
計算量が log の2乗になるというのは納得できます。
しかし、BITの木構造をうまく利用することで、この二分探索も全体で O(logn) に落とすことができる、とのことです。
それとともに与えられたアルゴリズムが以下のものですが、これまた初見時はよくわかりませんでした。
func (b *BinaryIndexedTree) LowerBound(w int) int { if w <= 0 { return 0 } // b.minPow2は、n以下の最小の2べき x := 0 for k := b.minPow2; k > 0; k /= 2 { if x+k <= b.n && b.bit[x+k] < w { w -= b.bit[x+k] x += k } } return x + 1 }
これは要約すると、「先頭からの累積和を、できるだけ長い区間から足して良いかを都度判断する」ということを行っています。
流れとしては、BITの上方の区間が長いノードから順番に見ており、
k というのは現在注目している区間の長さを意味しています。
各区間は、担当する区間の和を持っており、それがkey値 w よりも小さい場合は、足してから右側の次の短い長さの区間を見る必要があります。
逆にkey値よりも大きい場合は、その区間和は足さずに左側の次の短い長さの区間を見る必要があります。
以下は、ある具体例におけるアルゴリズムの様子を図示したものです（あまりわかりやすくできませんでしたが。。）。
結局、木の高さ分下ることで探索が終了するため、計算量は O(logn) となります。
クエリの先読みと、 k 番目に小さい要素の取得、という2つの典型テクニックが要求される問題だったと思います。
引用した記事でも言及されている平衡二分探索木についても、なるべく早く実装してみたいと思います。
次に出会ったときはちゃんと倒したいところです。
Codeforces Round No.594 Div.2 C復習
以前コンテストに参加して解けなかったものの復習です。
公式Editorialがハイコンテクスト過ぎてよくわからなかったのと、 数え上げの方法の典型度合いがものすごく高い気がしたので、別記事として書きました。
C. Ivan the Fool and the Probability Theory
問題
n 行 m 列からなるグリッドを、黒・白の2色で塗り分けることを考える。
ただし、塗り方は「辺に関して隣接しているグリッドについて、同じ色の隣接グリッドがたかだか1つまで」とする。
このような塗り方は何通り存在するか、 10^9 + 7 で割ったあまりで答えよ。
解答
一見複雑だが、「左上から少数のグリッドの色を確定させると、他のグリッドの色は自動的に決まる」というようなことはよくある（と思う）。
とりあえず、1行目を条件に反しないように適当に塗ってみると（同じ色が連続するのは2回までとする）、 以下の図のように、同じ色が連続してしまうと、その列を中心として次の行は一意に定まってしまう。
よって、このようなバターンの総数を数え上げる必要がある（※）。
また、同じ色が連続せずに、黒・白が交互に塗られる場合、 以下の図のように、次の行の1列目の色を決めた時点で、他の列の色が確定してしまう。
よって、このような場合も結局、1列目の色の塗り方の総数を数え上げる必要があり、 これは、（※）の部分と同じようにして数え上げることができる。
黒・白が2つまで連続して良いという条件のもとでの、1次元グリッドの塗り分けの総数を求めることに集中できる。
とりあえず、最初の色を黒として樹形図を書いてみる。
以下の図に示すように、よくよく観察すると、
色に関係なく2つ前と1つ前の通り数の和となるように遷移する（フィボナッチ数列）ため、
dp[i-2] + dp[i-1] = dp[i] のようにまとめられる。
以上をもとにコーディングしていく。
同じ色が隣接することがない塗り方1通りを2重に数えない、 左上を白とした場合も数えるために2倍する、あたりを忘れないように注意する。
var n, m int64 var dp [100000 + 5]int64 func main() { n, m = ReadInt64_2() dp[0], dp[1] = 1, 2 for i := 2; i <= 100000+3; i++ { dp[i] = dp[i-1] + dp[i-2] dp[i] %= MOD } var ans int64 ans = dp[m-1] - 1 ans += dp[n-1] ans %= MOD ans *= 2 ans %= MOD fmt.Println(ans) }
上記のフィボナッチ数を考えるあたりって自明なんでしょうか？ 自分にはあまり自明には感じられないので、説明がかなり冗長かもしれません。
Codeforces Round No.609 Div.2 参加記録 (A〜D解答)
青になれました！やったね！
思ったより長い戦いだった。。
「Codeforcesの青はAtCoderの水色」ぐらいの言説を見た気がするので、 「まぁ青ぐらいなら楽勝だろう」と思ったのですが、想像の3倍ぐらいは難しかったです。
多分青を維持するのは今の自分にはきつくて、 Codeforcesの1600はAtCoderの1400（水色の真ん中）ぐらいなんだろうなぁと感じています。
とはいえ、ミスは減ってきて実装力も向上しているとは思うので、 今後もしばらくはこの調子で頑張りたいところです。
A. Equation
解答
式変形すると a = n + b であるため、小さい方である b が決まれば a も自然と決まる。
そして、 a, b がともに合成数になるようにする。
2 以外の偶数はすべて合成数であることを踏まえると、
nが偶数ならば、bを適当な2以上の偶数とすればn + bも当然2以上の偶数となる。nが奇数ならば、bを適当な合成数である奇数とすればn + bは2以上の偶数となる。
であり、 a, b を選択できる。
var n int func main() { n = ReadInt() if n%2 == 0 { b := 4 a := n + b fmt.Println(a, b) } else { b := 9 a := n + b fmt.Println(a, b) } }
こんな問題に9分もかかってしまいました。
というより、公式Editorialを見ると、「9*n, 8*n でOK」とのこと、たしかに。
こどふぉのDiv2のA問題って、
O(1) 算数をしないといけなかったり、真面目に全探索しないといけなかったりで、
なかなか難しいです。
簡単と思える日が来てほしい。
B. Modulo Equality
解答
A, B それぞれについて、登場する値のカウントをメモしておく。
答えが x のとき、すべての A[i] に対して、
(AにおけるA[i]の個数) == (Bにおける(b = (A[i] + x) % m)の個数) となっている必要がある。
よって、このような x としてあり得るものをすべて列挙し、
それが条件を満たすか確かめれば良い。
ただし、求められている x は条件を満たす最小のものであるため、見つけるたびに小さい方で更新する。
x としてありうるものは、ある適当な A の値（以下のコード中では A[0] としている）を取り出し、
これが B のどの要素に遷移するのか？を考えることで列挙できる。
また、各 x に対して、すべての A の要素の遷移先の個数が、
A の遷移前の個数と一致するかをチェックすれば良い。
以上より、トータルの計算量は O(n^2) となり、十分高速である。
var n, m int var A, B []int func main() { n, m = ReadInt2() A = ReadIntSlice(n) B = ReadIntSlice(n) amemo, bmemo := make(map[int]int), make(map[int]int) for i := 0; i < n; i++ { amemo[A[i]]++ bmemo[B[i]]++ } ans := -1 aval, anum := A[0], amemo[A[0]] for bval, bnum := range bmemo { if anum != bnum { continue } var x int if bval > aval { x = bval - aval } else { x = bval + m - aval } isOK := true for av, an := range amemo { bv := (av + x) % m bn := bmemo[bv] if an == bn { continue } else { isOK = false break } } if isOK { if ans == -1 { ans = x } else { ChMin(&ans, x) } } } if ans == m { ans = 0 } fmt.Println(ans) }
A[i], B[i] の範囲が 10^9 なので固定長配列ではなく辞書を使う必要があるわけですが、
あまり慣れていない操作だったので時間がかかってしまいました。
そろそろこどふぉも100問弱ぐらいACしているはずですが、まだまだ足りてないなぁと感じます。
C. Long Beautiful Integer
解答
自由が効くのは最初の k 桁までであり、以降の桁は k 桁までの設定に従属する。
できるだけ小さいBeautifulな数値を作ろうとすると、
貪欲に上の桁から A の桁をコピーする必要があるため、まずはそのように桁を埋めていく。
このようにして出来る数値が A 以上であるならば、それが答えとなる。
もし A 未満となってしまう場合は、自由が効く桁の一番下の桁、すなわち k 桁目から微調整することを考える。
k 桁目までは A のコピーになっているため、できるだけ下の方の桁で +1 できれば良い
（必ず A よりも大きくなる）。
ただし、注目桁が 9 である場合は繰り上がりを考える必要がある。
その場合は、 9 の桁を 0 にした後、上の桁に移動してその桁の数字を +1 することを再考する。
1桁でも変更ができたらその時点で終了し、出来上がった数を出力すれば良い。
k 桁目までを変更する際は、下の方の桁も合わせて修正する必要があることには注意する。
var n, k int var A []rune func main() { n, k = ReadInt2() A = ReadRuneSlice() isBeau := true for i := 0; i < n; i++ { if i+k < n { if A[i] != A[i+k] { isBeau = false break } } else { break } } if isBeau { fmt.Println(len(A)) fmt.Println(string(A)) return } B := make([]rune, n) for i := 0; i < n; i++ { B[i] = 'x' } // iは起点 for i := 0; i < k; i++ { digit := A[i] // jは飛び飛び for j := i; j < n; j += k { B[j] = digit } } isSmall := false for i := 0; i < n; i++ { if A[i] == B[i] { continue } else if A[i] < B[i] { break } else { isSmall = true break } } if !isSmall { fmt.Println(len(B)) fmt.Println(string(B)) return } // 大きくなるように正しく調整する for i := k - 1; i >= 0; i-- { if B[i] == '9' { // iからk飛びで0に更新 for j := i; j < n; j += k { B[j] = '0' } } else { // iからk飛びで更新 for j := i; j < n; j += k { B[j]++ } break } } fmt.Println(len(B)) fmt.Println(string(B)) }
桁DPでよくやる考え方の基本、という感じがしました。
多分、最初の部分の「A がすでにBeautifulかどうか？」の判定は要らないと思います。
桁数を出力するのを忘れて1WA、 isSmall の判定部分でバグっており2WAしてしまい、
もったいないことをしてしまいました。
実装がちょっと長くなってくるとこういったミスが増えてくるので、 なにか対策を考えます。
D. Domino for Young
解答
わからなかったため、公式Editorialの手法をなぞりました。
与えられたヤング図形を市松模様（チェッカーフラグ）のように塗ります。
その時の黒と白の数を数えて、小さい方が答えです。
小さい方の色を仮に黒とすると、黒は隣接する白とで1つのドミノによって専有され、 また、すべての未使用の黒は未使用の白とペアにすることができるため、とのこと。
賢い（けど、上の説明はちょっと大雑把すぎるかもしれないです）。
var n int var A []int64 var b, w int64 func main() { n = ReadInt() A = ReadInt64Slice(n) b, w = 0, 0 for i := 0; i < n; i++ { l := A[i] if i%2 == 0 { // Bから塗り始める b += (l + (2 - 1)) / 2 w += l / 2 } else { // Wから塗り始める w += (l + (2 - 1)) / 2 b += l / 2 } } fmt.Println(Min(b, w)) }
青になれて嬉しい気持ちはありますが、目標はまだまだ上に持てているので、 引き続き頑張っていく所存です。
Educational Codeforces Round No.78 参加記録 (A〜C解答)
いつもの自分だったらBの算数で詰まって終了だったので、 成長を喜びたいところ。
A. Shuffle Hashing
解答
ハッシュ文字列からパスワード分の長さの分だけ文字列を切り出して調べる、というのを全探索すれば良い。
切り出した部分とパスワードが一致するかどうかの判定は、文字配列をソートして 文字列として一致するかどうかを調べるのが簡単（だと思う）。
var t int var P, H []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { P, H = ReadRuneSlice(), ReadRuneSlice() solve() } } func solve() { if len(P) > len(H) { fmt.Println("NO") return } pL := RuneList{} for i := 0; i < len(P); i++ { pL = append(pL, P[i]) } sort.Sort(pL) plen := len(P) for i := 0; i < len(H); i++ { if i+plen > len(H) { break } tmp := H[i : i+plen] hL := RuneList{} for j := 0; j < len(tmp); j++ { hL = append(hL, tmp[j]) } sort.Sort(hL) if string(pL) == string(hL) { fmt.Println("YES") return } } fmt.Println("NO") } type RuneList []rune func (a RuneList) Len() int { return len(a) } func (a RuneList) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a RuneList) Less(i, j int) bool { return a[i] < a[j] }
ハッシュからパスワードを切り出す全探索の部分がコーディングに時間かかりすぎてしまっていたので、 ちょっと良くないですね。 どうしよう。
B. A and B
解答
2つの数 a, b を等しくするためには、最終的に2数の差 diff = abs(a-b) を埋める必要がある。
必要な操作回数を k 回としたときに、2つの数に加える数値の総和は k*(k+1)/2 である。
よって、この総和を2つの数に分割して、その2つの数の差が diff とすることができるのかを考える。
総和は好きなように分割できる一方で、分割した2つの数の差の偶奇は1種類のみである。
例: sum == 6 のとき (0, 6), (1, 5), (2, 4), (3, 3) が分割の全パターンで、2つの数の差はすべて偶数となる。
以上から、 k を小さいところから全探索して、 diff%2 == sum%2 && diff <= sum を満たすものを見つければ良い。
総和の形から1テストケースあたりの計算量は O(Sqrt(Max(a, b))) なので間に合う。
var t int var a, b int64 func main() { t = ReadInt() for tc := 0; tc < t; tc++ { a, b = ReadInt64_2() solve() } } func solve() { diff := AbsInt(a - b) if diff == 0 { fmt.Println(0) return } for k := int64(1); ; k++ { sum := k * (k + 1) / 2 if diff%2 == sum%2 && diff <= sum { fmt.Println(k) return } } }
総和は好きなように分割できる一方で、分割した2つの数の差の偶奇は1種類のみである。
これって自明ですかね？ 私は紙に色々書いているうちに「それはそうだ」と納得できる、ぐらいなんですが。
C. Berry Jam
解答
以下の図に示すように、いちごとブルーベリーそれぞれを 1, -1 に変換する（RはいちごでBはブルーベリー）。
ここで、与えられた配列の真ん中で分割する。 扱いやすくするため、食べられる順番に従うように、左側については元の配列の内側から並ぶように、配列を構築する。
この2つの配列に対して、累積和を考える。 このようにすると、問題は「左の累積和から1つ、右の累積和から1つ数を選んで、全体の合計と等しくなるようにせよ」 と読み替えることができる。 また、答えは左のインデックス、右のインデックスの和が小さいほど望ましい。
このように考えると、それぞれの配列についてある累積和を取るインデックスは、その最小のもののみに興味があるといえる （同じ数の累積和というのは、食べ残ったRとBの数の差が同じであり、等価であると言えるから（DPっぽい考え方））。
以下の実装では、それぞれの累積和に対する最小のインデックスを、左右の配列分それぞれ辞書で用意した （負数もまとめて入れたかったため）。
あとは、あり得る和のパターンの全探索を、左配列基準および右配列基準で2スキャンして、ベストなものを見つける。
var t int var n int var A []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() A = ReadIntSlice(2 * n) solve() } } func solve() { E := make([]int, len(A)) for i := 0; i < len(A); i++ { if A[i] == 2 { E[i] = -1 } else { E[i] = 1 } } sum := Sum(E...) if sum == 0 { fmt.Println(0) return } if sum < 0 { for i := 0; i < len(E); i++ { E[i] = -E[i] } } sum = Sum(E...) R, L := []int{}, []int{} for i := n - 1; i >= 0; i-- { L = append(L, E[i]) } for i := 1; i < n; i++ { L[i] += L[i-1] } for i := n; i < 2*n; i++ { R = append(R, E[i]) } for i := 1; i < n; i++ { R[i] += R[i-1] } leftMemo, rightMemo := make(map[int]int), make(map[int]int) leftMemo[0], rightMemo[0] = -1, -1 for i := 0; i < n; i++ { a := L[i] if _, ok := leftMemo[a]; ok { continue } else { leftMemo[a] = i } } for i := 0; i < n; i++ { a := R[i] if _, ok := rightMemo[a]; ok { continue } else { rightMemo[a] = i } } ans := INF_BIT30 for lv := 0; lv <= sum; lv++ { rv := sum - lv lidx, lok := leftMemo[lv] ridx, rok := rightMemo[rv] if lok && rok { ChMin(&ans, lidx+ridx+2) } } for rv := 0; rv <= sum; rv++ { lv := sum - rv lidx, lok := leftMemo[lv] ridx, rok := rightMemo[rv] if lok && rok { ChMin(&ans, lidx+ridx+2) } } fmt.Println(ans) }
コンテスト後に時間を使って自分で考えた方法ですが、良い解法なのかはわかりません。 正直変換手数も多くてなんかまどろっこしい気がします。 editorialが公開された上で、模範解答が面白ければ、そちらも追記するかもしれません。
今回はなんとかイーブンに持ち込めました。
なんとか粘って今年の残りあと3回のこどふぉで青に持ち込みたいところです。
Codeforces Round No.608 (Div.2) 参加記録 (A〜C解答)
※Dはちょっと難しそうなので手を付けるのは当分先になりそうですが、 Eがシンプルな見た目で面白そうだったため、近々追記するかもしれません。
A. Suits
解答
2つのセットでジャケットが共通しており、ほかは独立している。 セットに組み込まれるアイテムはすべて1つずつであるため、 ジャケットはできるだけ高いセットで先に使ってしまい、 作れなくなったら、他方の安い方をできる限り作れば良い。
var a, b, c, d, e, f int func main() { a, b, c, d = ReadInt4() e, f = ReadInt2() bc := Min(b, c) ans := 0 if e > f { // aの方を使う m := Min(a, d) ans += e * m d -= m if d > 0 { mm := Min(bc, d) ans += f * mm } } else { // bcの方を使う m := Min(bc, d) ans += f * m d -= m if d > 0 { mm := Min(a, d) ans += e * mm } } fmt.Println(ans) }
これもDiv.2のAの中では大分簡単な方な気がします。
B. Blocks
解答
初期の個数が偶数のものを反転させれば良い。
なぜなら、2つのブロックを反転させるとき、反転させて個数をゼロにしたい方の色のブロックの個数は、
- 2個減る
- 変わらない（1個減って1個増える）
のいずれかであることから、依然として偶数のままとなる。
最終的に選んだ色を0個にしなければならないことを考えると、 初期の個数が偶数の方しか選ぶことが出来ない。
具体的な反転回数については、左から愚直に選んだ色を反転させるようにすればよく、
高々 n 回で十分である。
var n int var S []rune func main() { n = ReadInt() S = ReadRuneSlice() // 最初から全部いっしょならOK memo := make(map[rune]int) memo['B'] = 0 memo['W'] = 0 for i := 0; i < n; i++ { memo[S[i]]++ } if memo['B'] == n || memo['W'] == n { fmt.Println(0) return } // BもWも奇数なら無理 if memo['B']%2 == 1 && memo['W']%2 == 1 { fmt.Println(-1) return } answers := []int{} if memo['B']%2 == 0 { // BをWにする for i := 0; i < n-1; i++ { if S[i] == 'B' { answers = append(answers, i+1) S[i] = 'W' S[i+1] = rev(S[i+1]) } } } else { // WをBにする for i := 0; i < n-1; i++ { if S[i] == 'W' { answers = append(answers, i+1) S[i] = 'B' S[i+1] = rev(S[i+1]) } } } fmt.Println(len(answers)) fmt.Println(PrintIntsLine(answers...)) } func rev(r rune) rune { if r == 'B' { return 'W' } else { return 'B' } }
結構似たような問題は解いた気がするのに、かなり時間がかかってしまいました。
精進不足。
C. Shawarma Tent
解答
よくよく考えると、学校の1マス左・右・下・上のいずれかにテントを配置するのが最適です。
それぞれに配置した場合の、買い食いを行う可能性のある生徒の数を数え、 最大となるものを選べばよいです。
var n int var sx, sy int var X, Y []int func main() { n = ReadInt() sx, sy = ReadInt2() X, Y = make([]int, n), make([]int, n) for i := 0; i < n; i++ { x, y := ReadInt2() X[i], Y[i] = x, y } l, r, u, d := 0, 0, 0, 0 for i := 0; i < n; i++ { x, y := X[i], Y[i] if x <= sx-1 { l++ } if x >= sx+1 { r++ } if y <= sy-1 { d++ } if y >= sy+1 { u++ } } maxi := Max(l, r, u, d) fmt.Println(maxi) if l == maxi { fmt.Println(sx-1, sy) } else if r == maxi { fmt.Println(sx+1, sy) } else if d == maxi { fmt.Println(sx, sy-1) } else { fmt.Println(sx, sy+1) } }
コンテスト中に通した解法では、片方の軸を学校に合わせれば良いということしか気づけず、 素直に区間で一番重なりが多い部分を求めるべく、家の位置のソート・ランレングス圧縮・累積和とかいう、 闇の深いコードを書いてしまいました（なぜ通ったのか）。
問題文がいかついと複雑に考えてしまうような気がするので、もうちょっと冷静に問題を俯瞰したいところです。
Codeforces Round No.607 (Div.2) 参加記録 (A〜D解答)
A. Suffix Three
解答
よくよく見ると末尾の2文字だけを見れば判定できるので、そこだけを見れば良い。
var t int var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { S = ReadRuneSlice() solve() } } func solve() { n := len(S) str := S[n-2:] if string(str) == "po" { fmt.Println("FILIPINO") } else if string(str) == "su" { fmt.Println("JAPANESE") } else { fmt.Println("KOREAN") } }
ここまで簡単なAはDiv.3でも見たことがないので新鮮でした。
B. Azamon Web Services
解答
1回までの入れ替えを許可されている文字列 S について、辞書順最小のものを求める。
それが C よりも辞書順で小さければ、それを出力すれば良い。
それが C よりも辞書順で大きいのならば、impossibleである。
O(n^2) が許される制約なので、愚直に考える。
できるだけ小さい文字をできるだけ前方に配置するのが良いので、 探索開始位置を先頭から末尾に1ずつ移動させていき、チェック位置の文字よりも小さいものが、 末尾までに存在すればそれと入れ替えるようにする。
ただし、最小のものが複数ある場合は、できる限り後の物を選ぶ必要があることに注意する。
var t int var S, C []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { S = ReadRuneSlice() C = ReadRuneSlice() solve() } } const impossible = "---" func solve() { n := len(S) lidx, ridx := -1, -1 for i := 0; i < n; i++ { midx, minc := 5005, rune(100) // できるだけ後方から最小の文字を見つける for j := n - 1; j >= i+1; j-- { if minc > S[j] { midx, minc = j, S[j] } } if minc < S[i] { lidx, ridx = i, midx break } } if lidx == -1 && ridx == -1 { if string(S) < string(C) { fmt.Println(string(S)) } else { fmt.Println(impossible) } return } S[lidx], S[ridx] = S[ridx], S[lidx] if string(S) < string(C) { fmt.Println(string(S)) } else { fmt.Println(impossible) } }
最初、最小のものを前から選ぶようなコードを書いてしまい、pretest2でWAしてしまって頭を抱えてしまいました。
何気なく WAWA という文字列を考えてたら（某プロゲーマーが浮かんだのかWAに怯えたのかは不明）
間違いに気づけたので良かったですが、
偶然以外何者でもないので、もう少し簡単なものでもいいから文字列問題に取り組むべきだなぁと思いました。
C. Cut and Paste
解答
x の値が初期状態の S の長さ以下であるときは素直にシミュレーションができる。
なぜなら、カットのあとすぐ行われるペーストは、切り出したものを少なくとも1回はペーストすることになるため、
x 文字目までは連続部分文字列が変わらず、長さだけに集中すれば良いからである。
ここで、 x の制約が 10^6 までであることを踏まえると、
S の長さが x に達するまでは文字列連結が必要だが、それ以降は不要となる。
後は実装を頑張るだけである。
var t int var x int64 var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { x = ReadInt64() S = ReadRuneSlice() solve() } } var ans int64 var clip int64 func solve() { ans = int64(len(S)) clip = 0 for i := int64(0); i < x; i++ { c := int64(S[i] - '0') cut := S[i+1:] clip = NegativeMod(ans-(i+1), MOD) clip %= MOD ans += (c - 1) * (clip) ans %= MOD // 長さが十分だったらそれ以上は連結しない if int64(len(S)) < x { // 最大c-1回分追加で連結する OUTER: for j := int64(0); j < c-1; j++ { for k := 0; k < len(cut); k++ { S = append(S, cut[k]) // x以上になったら連結しない if int64(len(S)) >= x { break OUTER } } } } } fmt.Println(ans) } // NegativeMod can calculate a right residual whether value is positive or negative. func NegativeMod(val, m int64) int64 { res := val % m if res < 0 { res += m } return res }
添字が読みづらくて題意を把握するのに時間がかかってしまいました。
最近活用し始めましたが、Goのラベル付きfor文は競技プログラミングでは結構便利ですね （実開発では闇雲に使うと怒られそうですが）。
D. Beingawesomeism
解答
問題文がえげつないが、要はサンプル等で示された動きで A で塗りつぶしたい、ということ。
以下の図のように、1マスでも A が存在すればせいぜい4回の動作で塗りつぶしが可能となることを踏まえる。
少ない回数ほど条件は厳しいと考えられるので、 0, 1, 2, 3, 4回それぞれを図示して考えていく。
まず、図示していないが、全てが P の場合はimpossibleである。
また、すべてが A の場合は当然0回である。
次に、1回で済む場合を考えると、これは端っこの列もしくは行がすべて A のときである。
反対側へ向かう1回の移動で塗りつぶしが可能となる。
次に、2回で済む場合は、四隅のいずれかが A である場合と、
ある行もしくはある列についてすべてが A の場合である。
図に示す矢印の方向に移動を行えば、塗りつぶしが可能であることがわかる。
最後に、四隅を除いた端っこの行もしくは列に A が1文字でも存在すれば、3回の移動で済む。
いずれにも当てはまらない場合は、はじめの図に示したような4回の移動が必要となる。
var t int var r, c int var S [][]rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { r, c = ReadInt2() S = [][]rune{} for i := 0; i < r; i++ { row := ReadRuneSlice() S = append(S, row) } solve() } } func solve() { anum := 0 for i := 0; i < r; i++ { for j := 0; j < c; j++ { if S[i][j] == 'A' { anum++ } } } if anum == 0 { fmt.Println("MORTAL") return } if anum == r*c { fmt.Println(0) return } if subRow(0) || subRow(r-1) || subCol(0) || subCol(c-1) { fmt.Println(1) return } b := false for i := 1; i < r-1; i++ { b = b || subRow(i) } for i := 1; i < c-1; i++ { b = b || subCol(i) } if b { fmt.Println(2) return } if S[0][0] == 'A' || S[0][c-1] == 'A' || S[r-1][0] == 'A' || S[r-1][c-1] == 'A' { fmt.Println(2) return } b = false for i := 1; i < c-1; i++ { b = b || (S[0][i] == 'A') b = b || (S[r-1][i] == 'A') } for i := 1; i < r-1; i++ { b = b || (S[i][0] == 'A') b = b || (S[i][c-1] == 'A') } if b { fmt.Println(3) return } fmt.Println(4) } func subRow(rowId int) bool { for i := 0; i < c; i++ { if S[rowId][i] != 'A' { return false } } return true } func subCol(colId int) bool { for i := 0; i < r; i++ { if S[i][colId] != 'A' { return false } } return true }
pretestが弱くてなかなかの地獄だったようですが、 コンテスト外とはいえ1発で通ったので良かったです（残業後だったので通らなかったらやはり地獄だった）。
Cを解き終わった時点で満身創痍だったのでコンテスト中は触れられませんでしたが、 やっておくべきでした。
Codeforces Round No.605 (Div.3) 参加記録 (A〜E解答)
- A. Three Friends
- B. Snow Walking Robot
- C. Yet Another Broken Keyboard
- D. Remove One Element
- E. Nearest Opposite Parity
A. Three Friends
問題の概要
数直線上に3人がそれぞれ座標 a, b, c にいる。
それぞれは、自身の座標を +1, -1, 0 変位させることができる。
ここで、総合距離を |a-b| + |a-c| + |b-c| とする。
ありうる総合距離の最小値を求めよ、という問題。
解答
まず、一般性を失わずに a <= b <= c となるようにする。
この状態では、総合距離は (b-a) + (c-b) + (c-a) = 2*(c-a) と表すことができる。
よって、移動後もこの関係が保たれているのであれば b はないものとして考えることができる。
よって、 a, c の位置関係に注意しながら、それぞれを右に動かすか、左に動かすか判断すれば良い。
オーバーフローには注意する。
var q int var a, b, c int64 func main() { q = ReadInt() for tc := 0; tc < q; tc++ { a, b, c = ReadInt64_3() solve() } } func solve() { A := LongInt{a, b, c} sort.Sort(A) aa, _, cc := A[0], A[1], A[2] if aa < cc { aa++ } if aa < cc { cc-- } ans := 2 * (cc - aa) fmt.Println(ans) } // AbsInt is integer version of math.Abs func AbsInt(a int64) int64 { if a < 0 { return -a } return a } type LongInt []int64 func (a LongInt) Len() int { return len(a) } func (a LongInt) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a LongInt) Less(i, j int) bool { return a[i] < a[j] }
。。こんな考え込まなくても、素直に全探索するべきですね（27通りしか無いので）。
通ってみればなんてことはないですが、こういった算数はpretestではびびりながら出しているので、 提出に14分かかっています。
今回のコンテストで一番反省すべき点だと思います。
B. Snow Walking Robot
問題の概要
L, R, U, D の命令を与えると、それぞれ左、右、上、下に1マス進むロボットがある。
ただし、このロボットは一度通ったマスを通ると壊れてしまう。
ロボットを壊さずに、自分の家から出発させて、命令の最後には自分の家に戻ってくるようにしたい。
今、命令列が与えられるので、この列のいくつかの命令を消去することで、上記の操作を成立させたい。
最大で何個の命令を残すことができるか、またその時の命令列を出力せよ、という問題。
解答
基本的には、上下と左右に分けて考えて、例えば UU..URR..RDD..DLL..L のように
長方形を描くように移動させることを考えればよい。
このように移動させるためには、上への移動回数と下への移動回数が釣り合う必要があるため、 それぞれのカウントの最小値を採用すれば良い。 左右に関しても一緒である。
ただし、上下の移動ができない場合、あるいは左右の移動ができない場合は、 長方形ではなく線分となってしまい、同じ道を通ってしまうことをケアする必要がある。
この場合はコーナーケースとして別に扱う。
var q int var S []rune func main() { q = ReadInt() for tc := 0; tc < q; tc++ { S = ReadRuneSlice() solve() } } func solve() { memo := make(map[rune]int) memo['L'], memo['R'], memo['U'], memo['D'] = 0, 0, 0, 0 for _, r := range S { memo[r]++ } lrTime := Min(memo['R'], memo['L']) udTime := Min(memo['U'], memo['D']) if lrTime == 0 && udTime == 0 { fmt.Println(0) fmt.Println("") return } if lrTime == 0 { // UDを1回ずつ fmt.Println(2) fmt.Println("UD") return } if udTime == 0 { // LRを1回ずつ fmt.Println(2) fmt.Println("LR") return } fmt.Println(lrTime*2 + udTime*2) answers := []rune{} for i := 0; i < lrTime; i++ { answers = append(answers, 'R') } for i := 0; i < udTime; i++ { answers = append(answers, 'D') } for i := 0; i < lrTime; i++ { answers = append(answers, 'L') } for i := 0; i < udTime; i++ { answers = append(answers, 'U') } fmt.Println(string(answers)) }
C. Yet Another Broken Keyboard
問題の概要
ある長さが n の文字列が与えられたため、タイピングの練習のため、この文字列のすべての連続部分文字列をタイプしようとした。
しかし、いくつかのキーが壊れているため、いくつかの連続部分文字列は不完全な状態で出力されてしまった。
n*(n+1)/2 個の全連続部分文字列のうち、正しくタイピングできたものはいくつか求めよ、という問題。
解答
まず、与えられた文字列に対して、壊れているキーのインデックスに目印をつける。
左から文字列をスキャンしたとき、今見ている文字を右端とする部分文字列でタイピングできるものの数は、 以下の図に示すように、タイプ出来ない文字から数えた文字の長さ分だけである。
タイプ不可の文字に出会うたびにカウンターをリセットすることで、これらの数値はすべて記録できるため、 最後に総和を計算すれば良い。
オーバーフローには注意する。
var n, k int var S []rune var Avail []rune func main() { n, k = ReadInt2() S = ReadRuneSlice() for i := 0; i < k; i++ { tmp := ReadRuneSlice() Avail = append(Avail, tmp[0]) } memo := make([]int, n) for i := 0; i < n; i++ { if !isAvail(S[i]) { memo[i] = -1 } } cur := int64(0) sums := make([]int64, n) for i := 0; i < n; i++ { if memo[i] == -1 { // アウトなのでリセット cur = 0 } else { // 継続 cur++ } sums[i] = cur } ans := int64(0) for i := 0; i < n; i++ { ans += sums[i] } fmt.Println(ans) } func isAvail(r rune) bool { for i := 0; i < len(Avail); i++ { if Avail[i] == r { return true } } return false }
。。こんなにめんどくさいことしなくても、タイプ不可能のものとそうでないものを2値化して、 ランレングス圧縮したものを使ったほうが簡単でした。
そこそこ時間をロスしてしまったので、これも結構な失敗でした。
D. Remove One Element
問題の概要
長さ n の整数配列 A が与えられる。
この整数配列の好きな要素を1個削除するか、もしくはそのままでも良い。
この状態の配列に対し、狭義単調増加である連続部分列を考える。
ありうる最も長い連続部分列の長さを求めよ、という問題。
解答
配列 A の要素に関して、消す要素を全探索することを考える。
すなわち、ある要素を削除したとき、影響を受けるのはその前後だけであり、
その際に作られる連続部分列がより大きいものとなるのなら更新していく、ということを考える。
まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。
更に、数列間の階差を計算しておく。
以下の図に示すように、ある要素を削除したとき、新たに比較すべき階差は元の階差の和で表される。
よって、階差の和が正となる場合にのみ、削除される要素の前後の連続部分列の長さを足し合わせる形で、新たに出来上がる連続部分列の長さを計算する。
var n int var A []int func main() { n = ReadInt() A = ReadIntSlice(n) // 階差 diff := []int{} // len(diff) == n-1 for i := 1; i < n; i++ { diff = append(diff, A[i]-A[i-1]) } // 自身が含まれる増加列の長さ L := make([]int, n) for i := 0; i < n; i++ { if i == 0 { L[i] = 1 continue } if A[i] > A[i-1] { L[i] = L[i-1] + 1 } else { L[i] = 1 } } cur, l := 0, 0 for i := n - 1; i >= 0; i-- { if cur == 0 { cur, l = L[i], L[i] } L[i] = l cur-- } ans := 0 // 何もしない場合の最大値で初期化 for i := 0; i < n; i++ { ChMax(&ans, L[i]) } // すべて試す for i := 1; i < len(diff); i++ { if diff[i] > 0 && diff[i-1] > 0 { continue } if diff[i] <= 0 && diff[i-1] <= 0 { continue } if diff[i]+diff[i-1] > 0 { // この場合のみ意味がある ChMax(&ans, L[i-1]+L[i+1]-1) } } fmt.Println(ans) } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false }
本番では階差数列のみをうまく扱って答えを出そうとしたらぐちゃぐちゃになってしまい、 結果バグったコードによりpretestで撃沈してしまいました。 また、そうでなくとも、階差のインデックスと元の配列のインデックスの調整で身長になる必要があり、あまりいい実装が出来ませんでした（というかよくよく見るといろいろな部分が省ける）。
まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。
この部分も結構面倒なのですが、「Union Findを使って増加列を同じグループとし、 それぞれが属するグループのサイズを見れば良い」という方法を くるさんにご教示いただきました。
あまりUnion Findを活用できていなかったと思うので、これからはもう少し視野を広げてみようと思います （というよりは問題にたくさん触れるべきなのですが）。
DPによる別解
こちらも同じくくるさんの解法を参考にしました。
dp1[i]: i番目の数値が属する連続部分列に関して、何個目かを記録する
dp2[i]: i番目以前の数値を1つ削除したときの、i番目の数値が属する連続部分列に関して、何個目かの最大値を記録する
以下のコードに示すように、 dp2 -> dp1 のような遷移がないため、正しく動作します。
var n int var A []int var dp1, dp2 [200000 + 5]int func main() { n = ReadInt() A = ReadIntSlice(n) for i := 0; i < n; i++ { dp1[i] = 1 } for i := 0; i < n; i++ { if i-1 >= 0 && A[i] > A[i-1] { ChMax(&dp1[i], dp1[i-1]+1) ChMax(&dp2[i], dp2[i-1]+1) } if i-2 >= 0 && A[i] > A[i-2] { ChMax(&dp2[i], dp1[i-2]+1) } } ans := 0 for i := 0; i < n; i++ { ChMax(&ans, dp1[i]) ChMax(&ans, dp2[i]) } fmt.Println(ans) }
なんと呼ぶべきかはわからないですが、 こういった片方向の遷移を行うものは過去のABCあたりでも解いたことがあるような気がします。
いずれにせよ、頻出パターンの1つではあると思うので、定着させていきたいところです。
E. Nearest Opposite Parity
問題の概要
長さ n の整数配列 A が与えられる。
ある位置 i からは、1回の移動で i - A[i] もしくは i + A[i] へと移動できる。
ある開始位置から移動をはじめて、開始位置の A[i] とは偶奇が反対のところへたどり着くためには、
最小で何回の移動が必要か、すべての位置に関して答えよ。
また、到達不可能であるならば -1 を出力せよ、という問題。
解答
公式Editorialをなぞったものです。
まず、ある位置 i から j まで移動できるとき、これを逆向きに考えて j -> i とエッジを張ります。
このようにして出来上がるグラフの辺の数は、最大でも 2*n であるため、全探索が間に合います。
そこで、偶数の要素をスタート地点とした多点BFSを考え、到達位置へのステップ数を記録します。 探索が完了したら、奇数の要素のステップ数を確認すれば、それが答えとなっています。
今度はこれを偶数と奇数を入れ替えて行うことで、すべての位置について答えを求めることが出来ます。
var n int var A []int var G [200000 + 5][]int var answers []int func main() { n = ReadInt() A = ReadIntSlice(n) for i := 0; i < n; i++ { lid, rid := i-A[i], i+A[i] if lid >= 0 { G[lid] = append(G[lid], i) } if rid < n { G[rid] = append(G[rid], i) } } oddIdxs, evenIdxs := []int{}, []int{} for i := 0; i < n; i++ { if A[i]%2 == 0 { evenIdxs = append(evenIdxs, i) } else { oddIdxs = append(oddIdxs, i) } } answers = make([]int, n) for i := 0; i < n; i++ { answers[i] = -1 } bfs(oddIdxs, evenIdxs) bfs(evenIdxs, oddIdxs) fmt.Println(PrintIntsLine(answers...)) } func bfs(starts, ends []int) { dist := make([]int, n) for i := 0; i < n; i++ { dist[i] = INF_BIT30 } queue := []int{} for _, sidx := range starts { dist[sidx] = 0 queue = append(queue, sidx) } for len(queue) > 0 { cid := queue[0] queue = queue[1:] for _, nid := range G[cid] { if dist[nid] == INF_BIT30 { dist[nid] = dist[cid] + 1 queue = append(queue, nid) } } } for _, eidx := range ends { if dist[eidx] != INF_BIT30 { answers[eidx] = dist[eidx] } } }
ICPC形式？のため、Dが解けずにコンテスト中は見ることすらできませんでしたが、 復習の際にDFSから考え始めたので論外でした。
Dijkstraしかり、「最短経路」が効かれているのだからBFSを検討しないと土俵にも立てていませんでした。
また、別に逆向きのグラフじゃなくても順方向のグラフで同じことをすればいけるのでは？とか考えましたが、 探索済みの箇所で衝突してしまうため無理でした。
確かAtCoderのうほょじごという問題が、 想定解法がこれと似たようなコンセプトだったような気がします（違ったらすみません）。 「逆から考える」っていう典型と見るべきなのでしょうか？
そろそろ過去に解けなかった問題もとき直したいところなのですが、時間が。。
