Codeforces Round No.600 (Div.2) 参加記録(A〜D解答)
A. Single Push
問題の概要
与えられた配列 A
に対して、1度だけ任意の連続区間に対してある正の整数加算することが許される。
操作は行わなくても良い。
これによって、もう一方の与えられた配列 B
に等しくすることができるか判定する問題。
解答
すべての要素に関して diff[i] = B[i] - A[i]
を計算しておく。
この diff
配列が [0, ..., 0, k, ..., k, 0, ..., 0], k >= 0
のようになっていればよい。
判定を簡単にするために、 diff
配列に対してランレングス圧縮を施す。
圧縮後の配列に対して、
- 負の整数が検出されたらアウト
- 正の整数が2つ以上検出されたらアウト
- そうでないならセーフ
のように判定すればよい。
var t int var n int var A, B []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() A, B = ReadIntSlice(n), ReadIntSlice(n) solve() } } func solve() { diff := make([]int, n) for i := 0; i < n; i++ { diff[i] = B[i] - A[i] } pressed, _ := RunLengthEncoding(diff) positive := 0 for i := 0; i < len(pressed); i++ { if pressed[i] < 0 { fmt.Println("NO") return } if pressed[i] > 0 { positive++ } } if positive == 0 || positive == 1 { fmt.Println("YES") } else { fmt.Println("NO") } } // RunLengthEncoding returns encoded slice of an input. func RunLengthEncoding(S []int) ([]int, []int) { runes := []int{} lengths := []int{} l := 0 for i := 0; i < len(S); i++ { // 1文字目の場合保持 if i == 0 { l = 1 continue } if S[i-1] == S[i] { // 直前の文字と一致していればインクリメント l++ } else { // 不一致のタイミングで追加し、長さをリセットする runes = append(runes, S[i-1]) lengths = append(lengths, l) l = 1 } } runes = append(runes, S[len(S)-1]) lengths = append(lengths, l) return runes, lengths } // RunLengthDecoding decodes RLE results. func RunLengthDecoding(S []int, L []int) []int { if len(S) != len(L) { panic("S, L are not RunLengthEncoding results") } res := []int{} for i := 0; i < len(S); i++ { for j := 0; j < L[i]; j++ { res = append(res, S[i]) } } return res }
B. Silly Mistake
問題の概要
あるオフィスの入退場記録が配列で表されている。 正の整数が入場、負の整数が退場を表している。
この記録には満たすべき性質があり、以下の3つがある。
- 各メンバは入場の前に退場することはない。
- 各メンバは1日に複数回入退場してはならない。
- 各メンバは入場したら必ずその日のうちに退場しなければならない。
このような性質を満たすように、入退場記録を1日ごとに正しく分割せよ、という問題。
解答
特に日数を小さくしたり大きくしたり、という制約はないので、 「オフィスが空になったら、すぐさま一日をリセットする」というふうにシミュレーションするのが良い。 (リセットしたほうが、あるメンバの複数回入場のチェックが楽になるので、このほうが簡単。)
各入退場イベントを処理・管理するにあたり、オフィスに現在いる人、およびその日の各メンバの入退場記録を map
で管理する。
(メンバは固定で 10^6
なので、固定長配列だと空室判定や一日のリセットに時間がかかり間に合わない。)
処理する中で問題の3つの制約に抵触したらその時点で -1
を出力すれば良い。
var n int var A []int func main() { n = ReadInt() A = ReadIntSlice(n) if n%2 == 1 { fmt.Println(-1) return } memo := make(map[int]int) // オフィス times := make(map[int]int) // ある一日の入場回数 answers := []int{} count := 0 for i := 0; i < n; i++ { a := A[i] if a < 0 { a = -a // 退出 if _, ok := memo[a]; ok { delete(memo, a) } else { // 入場前退出のためアウト fmt.Println(-1) return } } else { // 入場 if times[a] == 0 { memo[a] = 1 times[a] = 1 } else { // 一日に2回登場したのでアウト fmt.Println(-1) return } } count++ // 空室判定 if len(memo) == 0 { // 空室なので次の日へリセット answers = append(answers, count) count = 0 memo = make(map[int]int) times = make(map[int]int) } } if len(memo) != 0 { fmt.Println(-1) return } fmt.Println(len(answers)) fmt.Println(PrintIntsLine(answers...)) }
一番最後の空室判定を忘れて1WA出してしまったのが大反省。
競技プログラミングでGolangの map
の delete
を行ったのは何気に初めてな気がする。
C. Sweets Eating
問題の概要
解答
食べるケーキ k
個は、ケーキ列を昇順ソートした上でその前 k
個でよい、というのはすぐに分かる。
また、食べる順番についても、カロリーが大きい方から小さい方を選ぶ形でよい、というのもすぐに分かる。
これを愚直に各 k
について線形スキャンする形で行うと、トータルの計算量が O(n^2)
になって間に合わない。
そこで、直前の結果を利用して高速に計算できないかを考える。
図のように( m = 2
のケース)、 k
が1増えるごとに、追加して食べるケーキの番号から m
飛びのケーキについても砂糖を加算する必要があるとわかる。
この m
飛びの累積和を事前に O(n)
で計算しておけば、 k
のときの答えを利用して k+1
が計算できる。
結局、ソートがネックになるため、計算量は O(nlogn)
。
var n, m int var A []int var answers []int64 func main() { n, m = ReadInt2() A = ReadIntSlice(n) answers = make([]int64, n) sort.Sort(sort.IntSlice(A)) memo := make([]int64, n) for i := 0; i < m; i++ { memo[i] = int64(A[i]) } for i := m; i < n; i++ { memo[i] = memo[i-m] + int64(A[i]) } answers[0] = int64(A[0]) for i := 1; i < n; i++ { answers[i] = answers[i-1] + memo[i] } fmt.Println(PrintIntsLine(answers...)) }
m
飛びの累積和の計算というのを初めてやったので、最初やり方が分からずに時間を食ってしまった。
ちょっと筋の悪い手法だった気がする。
公式editorialの解法
直前の結果ではなく、 m
個前の結果を利用しましょうという方法。
m
個前の結果を基準として考えると、新たに追加して食べるケーキを含めて、
それまでのケーキすべての累積和をそのまま加算することで、
k
個の場合の答えが得られる。
var n, m int var A []int var answers []int64 func main() { n, m = ReadInt2() A = ReadIntSlice(n) answers = make([]int64, n) sort.Sort(sort.IntSlice(A)) sums := make([]int64, n+1) for i := 0; i < n; i++ { sums[i+1] = sums[i] + int64(A[i]) } for i := 0; i < n; i++ { if i < m { answers[i] = sums[i+1] continue } answers[i] = answers[i-m] + sums[i+1] } for i := 0; i < n; i++ { if i == n { fmt.Printf("%d\n", answers[i]) } else { fmt.Printf("%d ", answers[i]) } } }
すでに解いた部分問題を可能な限り利用とするのはDP考える上でも重要だと思うので、 こういった視点が他の問題でも持てるようになりたい。
D. Harmonious Graph
問題の概要
n
頂点 m
辺からなる無向グラフが与えられる。
また、すべての (l, m, r), 1 <= l < m < r <= n
について、 l, r
間にパスが存在するときには l, m
にもパスが存在する場合、
そのグラフは harmonious であるという。
与えられた無向グラフに対して辺を追加して harmonious にするためには、最小で何本の辺を足す必要があるか求めよ、という問題。
解答
与えられたグラフに対し、DFSなりUnion Find木を使うなりして連結成分を計算する。
さらに、各連結成分を構成するノードのIDについて、最小のものと最大のもの(それぞれ l, r
とする)を調べておく。
すると、 harmonious である状態とは、各連結成分を [l, r]
の区間とみなすと、
区間の交差がない状態であると言える。
よって、交差している区間同士をマージすればよく、そのためには連結成分を構成する適当な2点間に1本辺を足すだけで良い。
結局、区間をマージするたびに答えをインクリメントする、という処理を高速に行えば良い。
このためには、 [l, r]
を l
基準で昇順ソート(※ノード番号の小さい順にDFSすれば、自然とソートされる)し、その順に区間をスキャンしていけば良い。
具体的には、暫定の r
の最大値を保持しながら、次の l
がその最大値以下であれば交差していると判定できる。
var n, m int var G [200000 + 5][]int var colors [200000 + 5]int var left, right int func main() { n, m = ReadInt2() for i := 0; i < m; i++ { x, y := ReadInt2() x-- y-- G[x] = append(G[x], y) G[y] = append(G[y], x) } L := make(ComponentList, 0) for i := 0; i < n; i++ { colors[i] = -1 } for i := 0; i < n; i++ { if colors[i] == -1 { left, right = i, i dfs(i, i) L = append(L, &Component{key: left, l: left, r: right}) } } ans := 0 biggest := L[0].r for i := 1; i < len(L); i++ { if L[i].l <= biggest { ans++ ChMax(&biggest, L[i].r) } else { biggest = L[i].r } } fmt.Println(ans) } func dfs(i, c int) { colors[i] = c for _, nid := range G[i] { if colors[nid] == -1 { ChMin(&left, nid) ChMax(&right, nid) dfs(nid, c) } } } type Component struct { key int l, r int } type ComponentList []*Component
「交差する区間をマージする」という読み替えが出来なかったので反省。
加えて、区間を効率的にマージしていく方法も、簡単だけど意外と自分で考えるのは難しかったので、 ちゃんと覚えておきたいところです。
実装については、Union Find木を使うとちょっとだけ遅くなるけど、 人によってはそちらのほうが簡単に実装できるかも(自分は両方試したところDFSのほうがスッキリしました)。
こどふぉをやっていると、特に有名な名前はついていないけど時々必要になる実装手法(?)のようなものがよく出る気がするので、 このあたりもちゃんと定着させていきたいところ。
Educational Codeforces Round No.76 参加記録(A〜D解答)
こどふぉの算数が苦手とかそういうレベルじゃなく。
A. Two Rival Students
問題の概要
n
人の横一列に並んだ生徒の中に2人のライバルが居るので、それらの学生をできるだけ互いに引き離したい。
一回の操作で隣り合う2人の生徒の位置を入れ替えることができる、とする場合に、
最大 x
回の操作でどれだけ引き離すことができるか求める問題。
解答
n
も x
もテストケースの数も高々100なので、シミュレーションが十分間に合う。
頑張れば O(1)
でも求まると思うが、バグらせたくないのでシミュレーションを書いた。
var t int var n, x, a, b int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n, x, a, b = ReadInt4() solve() } } func solve() { if a > b { a, b = b, a } for { if x == 0 || a == 1 { break } a-- x-- } for { if x == 0 || b == n { break } b++ x-- } fmt.Println(AbsInt(b - a)) }
B. Magic Stick
問題の概要
ある正の整数について、2種類の魔法をかけることができる。 それぞれの魔法の結果、正の整数は以下のように変化する。
a
が偶数ならば、a -> a/2*3
とできる。a
が1より大きいならば、a -> a-1
とできる。
ある2つの正の整数 x, y
が与えられるので、魔法を好きな順番で何回でも使っても良いので、
x
から y
を生み出せるか、を判定する問題。
解答
ゴールは x
を y
よりも大きくすること、というのはすぐに分かる。
よくよく考えると(残念ながら自分はよくよく考えないと気づけなかった)、
a
が4以上であるならば、2種類の魔法を適当に繰り返し用いれば(偶数なら 1
、奇数なら 2
)、
いくらでも数を大きくできることに気づく。
特殊なのは 1, 2, 3
の3つだけで、 1
は魔法をかけることができず、 2, 3
はそれぞれループしてしまう。
このことに注意して場合分けを行えば良い。
var t int var x, y int64 func main() { t = ReadInt() for tc := 0; tc < t; tc++ { x, y = ReadInt64_2() solve() } } func solve() { if x >= y { fmt.Println("YES") return } if x == 1 { if x >= y { fmt.Println("YES") } else { fmt.Println("NO") } return } if x == 2 || x == 3 { if y <= 3 { fmt.Println("YES") } else { fmt.Println("NO") } return } fmt.Println("YES") }
問題を考えているうちに、勘違いして別の問題を解き始めてしまい、死ぬほど時間を取られてしまいました。
C. Dominated Subarray
問題の概要
2要素以上の長さをもつ配列に対して、その配列の中である1つの整数の頻度が狭義で1位(同率1位ではない)となる場合、 その配列を dominated subarray と呼ぶ。
ある配列 A
が与えられるので、最小の長さを持つ dominated subarray の配列長を答えよ。
また、 dominated subarray が存在しない場合は -1
を出力せよ。
解答
制約的に O(nlogn)
が間に合うと考え、長さを決め打ちし、その長さ以下の dominated subarray が存在するかどうかを、二分探索で探索することを考えた。
ある長さについて、その長さ(以下)の dominated subarray が存在するかどうかの判定に関しては O(n)
かかってもよい(配列の全探索のようなことが許容される)。
ある長さ m
を決めたとき、配列 A
に対して長さ m
の固定長のスライディングウィンドウを考える。
このスライディングウィンドウを subarray と考え、この subarray 中の各整数値の頻度をカウントする。
すると、いずれかのカウントが2以上となった時点で、長さ m
以下の dominated subarray が存在することを主張できる。
なぜなら、カウントが2回の整数を a
としたとき、 [a, ..., a]
のように両端が a
のような subarray が dominated subarray となるためである。
var t int var n int var A []int var cnt []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() A = ReadIntSlice(n) solve() } } func solve() { if n == 1 { fmt.Println(-1) return } cnt = make([]int, n+1) flag := true for i := 0; i < n; i++ { a := A[i] if cnt[a] > 0 { // 2回登場するものがあれば答えはある flag = false break } cnt[a]++ } if flag { // すべて異なる数ならNO fmt.Println(-1) return } // m は中央を意味する何らかの値 isOK := func(m int) bool { // リセット cnt = make([]int, n+1) // 初期化 for i := 0; i < m; i++ { a := A[i] if cnt[a] > 0 { return true } cnt[a]++ } // スライド for i := m; i < n; i++ { j := i - m cnt[A[j]]-- a := A[i] if cnt[a] > 0 { return true } cnt[a]++ } return false } ng, ok := 1, n for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } fmt.Println(ok) }
dominated subarray の性質にもっと早い段階で気づけたら、こんな面倒なことやらずに、もっと楽な方法が取れたと思う。
D. Yet Another Monster Killing Problem
問題の概要
あるゲームにおいて、 m
体のヒーローが、ある1つのダンジョンを攻略しようとしている。
各ヒーローは、力とスタミナの2つのパラメータを有している。
また、ダンジョンには n
体のモンスターがおり、各モンスターは力のパラメータのみを有している。
モンスターは決まった順番に並んでおり、ヒーロー達はこの順番にモンスターと出会い、討伐していく。
このゲームは一日単位のターン制で、一日にある1体のヒーローのみがダンジョンに潜入できる。 ダンジョンではモンスターと一体ずつ戦い、ヒーローの力がモンスターの力以上だった場合、 ヒーローはそのモンスターを討伐できる。 ただし、1日に連続して討伐できるモンスターは、潜入したヒーローのスタミナの値までである。 また、ヒーローの力が出会ったモンスターの力未満だった場合、ヒーローは帰還し一日は終了する。
このような設定のもとで、ダンジョンを攻略するのに要する最短の日数はいくらか。
解答
素直に考えて、生き残っているモンスターは先頭からもれなく倒していく必要があるため、 その日のダンジョンの状況において、できるだけたくさんのモンスターを倒せるようなヒーローを、都度選択するのが最善となる。
一日ごとにすべてのヒーローを全探索して、最もモンスターを多く倒せるヒーローを選択できればよいが、
最悪のケースでは、1日にモンスター1体しか倒すことができず、このようなヒーロー列の全探索をモンスターの数だけ行う事になってしまう。
計算量は O(n*m)
となるため、今回の制約では間に合わない。
そこで、モンスターの列に対して起点を設定し、さらに1つずつ目標ラインを上げていき、その区間のモンスターをすべて倒せるヒーローが居るかどうかを、
O(logn)
で求められないか?と考えてみる。
この区間のモンスターを倒す条件は、
1については、ヒーローを予めスタミナでソートしておけば、条件を満たすヒーローたちは二分探索で高速に検索できる。
2については、選択対象のヒーローは前述の二分探索で求めたヒーローよりスタミナが大きいヒーロー群なので、
ヒーロー列の後半部分に対して、予め力の「累積Max」とでも言うべきものを前計算しておけば、 O(1)
で取得できる。
また、区間内のモンスターの力の最大値については、目標ラインを上げる際に最大値を更新することで、 O(1)
で取得できる。
以上より、必要なパーツは揃ったので、手順に従って実装していく。 (個人的には)目標ラインを上げたり、1日後のモンスター列の起点を更新する部分がバグりやすいと感じたので、 適宜別の関数として切り分けるなど、工夫をする。
計算量はヒーロー列のソートと最大 n
回ヒーローの選択が行われることから O((m+n)*log(m))
。
type Hero struct { key int p, s int } type HeroList []*Hero type byKey struct { HeroList } func (l HeroList) Len() int { return len(l) } func (l HeroList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l byKey) Less(i, j int) bool { return l.HeroList[i].key < l.HeroList[j].key } // how to use // L := make(HeroList, 0, 200000+5) // L = append(L, &Hero{key: intValue}) // sort.Stable(byKey{ L }) // Stable ASC // sort.Stable(sort.Reverse(byKey{ L })) // Stable DESC var t int var n, m int var A, P, S []int var L HeroList // ヒーロー構造体の配列 var M []int // [idx, m-1] のヒーロー区間におけるpowerの最大値を記憶 func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() A = ReadIntSlice(n) m = ReadInt() P, S = make([]int, m), make([]int, m) for i := 0; i < m; i++ { p, s := ReadInt2() P[i], S[i] = p, s } solve() } } func solve() { L = make(HeroList, 0) for i := 0; i < m; i++ { p, s := P[i], S[i] L = append(L, &Hero{key: s, p: p, s: s}) } sort.Stable(byKey{L}) // endurance順に昇順ソートする // 後半部分のpowerに関する累積Maxを計算しておく M = make([]int, m) M[m-1] = L[m-1].p for i := m - 2; i >= 0; i-- { M[i] = Max(M[i+1], L[i].p) } l := 0 ans := 0 for l < n { length := sub(l) if length == -1 { fmt.Println(-1) return } else { l += length ans++ } } fmt.Println(ans) } // モンスターの配列に対して、A[s]から数えて何体倒せるかを計算する関数 // -1を返したら1体も倒せない(=失敗) func sub(s int) int { maxMP := A[s] length := -1 for l := 0; s+l < n; l++ { maxMP = Max(maxMP, A[s+l]) // A[s]から現在見ているところまでのモンスターのpowerの最大値 idx := sub2(l + 1) if idx == m { break } maxHP := M[idx] // l+1以上のenduranceを持つヒーローの中のpowerの最大値 if maxHP >= maxMP { length = l + 1 } else { break } } return length } // enduranceがl以上となるギリギリのインデックスを二分探索で計算 // mを返したらそのようなヒーローは存在しない func sub2(l int) int { // m は中央を意味する何らかの値 isOK := func(mid int) bool { if L[mid].s >= l { return true } return false } ng, ok := -1, m for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } return ok }
コンテスト中は日数について二分探索する、という方法がまっさきに思い浮かび、 時間がなかったことも合って固執してしまったのが失敗でした。 まずは基本に従って「素直に愚直に考えてから計算量を落とす」という思考もちゃんと視野に入れないとダメですね。
また、コンテスト後に「セグ木を使った」とか「セグ木2本使って判定した」とかのツイートが見られましたが、 活用方法がちょっとわかりませんでした。 コードが劇的に書きやすくなるとかだったら活用したいところですが、ライブラリ整理もしっかりできていないと難しそう。
Dみたいな問題の安定感を高めていきたいところ。
Codeforces Round No.599 (Div.2) 参加記録(A〜C解答)
B2が本当にわからなかった。
Cは解けたけど、この手の問題はつい最近もこどふぉで出会ったので、もう少し筋よく考えてさっと答えたいところ。
- A. Maximum Square
- B1. Character Swap (Easy Version)
- B2. Character Swap (Hard Version)
- C. Tile Painting
A. Maximum Square
問題の要約
(問題ページの図が詳しいのでそちらをご参照ください。)
n
個の a[i] * 1
の縦長の板が与えられるので、それらの好きな組み合わせを好きな順番で横にくっつける。
上の出っ張ったところを切ってできるだけ大きい正方形を作りたい。
最大で一辺の長さはいくらにできるか、という問題。
解答
一辺の長さを x
にしようと思うと、縦の長さが x
以上の板が x
枚以上必要となる。
板の縦の長さの最大値が 1000
であることを踏まえ、配列を使って各板の長さについて枚数を数えて記憶しておく。
この配列に対して、反対側から累積和を計算することで、ある長さ以上の板の枚数を O(1)
で取得できる。
最大の値を答えることが目的なので、大きいところからチェックしていけば良い。
全体で O(n)
で解ける。
var k int var n int var A []int func main() { k = ReadInt() for tc := 0; tc < k; tc++ { n = ReadInt() A = ReadIntSlice(n) solve() } } func solve() { cnt := [1005]int{} for i := 0; i < n; i++ { cnt[A[i]]++ } sums := make([]int, 1005) for i := 1000; i >= 0; i-- { sums[i] = sums[i+1] + cnt[i] } for i := 1000; i >= 0; i-- { if sums[i] >= i { fmt.Println(i) return } } }
テストケースも少ないのでもっと愚直にやってもいいと思うけど、 特に思いつきませんでした。
B1. Character Swap (Easy Version)
問題の要約
長さ n
の文字列 S, T
が与えられる。
S, T
は異なることが保証される。
この文字列に対して、ある 1 <= i, j <= n
について S
の i
文字目と T
の j
文字目を交換して良い。
i, j
は同じでも異なってもどちらでも良いが、必ず一度交換する必要がある。
文字列 S, T
を等しくできるかどうか判定する問題。
解答
S, T
について、同じ位置の文字を比較したときの異なる個数を考える。
これが 1
個の場合や、 3
個以上の場合は1回のみの交換ではどのようにしても等しくすることはできない。
よって、文字列を等しくできる可能性があるのは、異なる個数がちょうど 2
個の場合である。
そしてこのような状況で考えられる交換は、異なる位置の番号を小さい順に i, j
とすると、
S
のi
文字目とT
のj
文字目の交換S
のj
文字目とT
のi
文字目の交換
のいずれかである。
この交換の後に S, T
が等しくなるための条件はそれぞれ、
T[i]
とT[j]
を比較することになるためT[i] == T[j]
かつ、S[j]
とS[i]
を比較することになるためS[j] == S[i]
S[i]
とS[j]
を比較することになるためS[i] == S[j]
かつ、T[i]
とT[j]
を比較することになるためT[i] == T[j]
結局条件はどちらも同じなので、この条件をチェックすれば良い。
var k int var n int var S, T []rune func main() { k = ReadInt() for tc := 0; tc < k; tc++ { n = ReadInt() S = ReadRuneSlice() T = ReadRuneSlice() solve() } } func solve() { diff := 0 for i := 0; i < n; i++ { if S[i] != T[i] { diff++ } } if diff == 0 { fmt.Println("Yes") return } if diff != 2 { fmt.Println("No") return } pos := [2]int{} j := 0 for i := 0; i < n; i++ { if S[i] != T[i] { pos[j] = i j++ } } i, j := pos[0], pos[1] if S[i] == S[j] && T[i] == T[j] { fmt.Println("Yes") } else { fmt.Println("No") } }
B2. Character Swap (Hard Version)
問題の要約
設定はEasyと似ているが、制約がまず全く異なる。
- テストケース
1 <= k <= 1000
- 文字列長
2 <= n <= 50
また、操作回数は 2*n
回までなら何回でもよい。
さらに、判定結果だけではなく、等しくできるのであればその構築手順まで出力する必要がある。
解答
※コンテスト中全くわからなかったので、公式editorialの内容そのままです。
まず、等しくできるための必要条件として「すべてのアルファベットについて、 S, T
に渡って登場回数が偶数であること」が挙げられる
(あるアルファベットが奇数個である場合、 S, T
のいずれかで、どこかの位置で最終的に余ってしまう)。
また、必要条件が満たされる場合、以下のような手順で文字列を等しくすることができる。
i = 1...n
のi
について、S[i] != T[i]
である場合、以下のいずれかが必ず成り立つので、それに応じた操作を行う。j > i
のj
について、S[i] == S[j]
となる場合、S[j], T[i]
を交換する。 あるいは、j > i
のj
について、S[i] == T[j]
となる場合、まずS[j], T[j]
を交換し、その後S[j], T[i]
を交換する。 それぞれの操作を行うことで、i
番目の文字を揃えることができる。 これをn
まで行えば文字列を互いに等しくできる。
それぞれの操作について最大で 2
回までで住むため、 2*n
という操作回数はこれを行うために十分である。
const ALPHABET_NUM = 26 var k int var n int var S, T []rune func main() { k = ReadInt() for tc := 0; tc < k; tc++ { n = ReadInt() S = ReadRuneSlice() T = ReadRuneSlice() solve() } } func solve() { memo := make([]rune, ALPHABET_NUM) for i := 0; i < n; i++ { s, t := S[i], T[i] memo[s-'a']++ memo[t-'a']++ } for i := 0; i < len(memo); i++ { if memo[i]%2 == 1 { fmt.Println("No") return } } answers := [][]int{} for i := 0; i < n; i++ { if S[i] == T[i] { continue } for j := i + 1; j < n; j++ { if S[i] == S[j] { S[j], T[i] = T[i], S[j] answers = append(answers, []int{j, i}) break } else if S[i] == T[j] { S[j], T[j] = T[j], S[j] S[j], T[i] = T[i], S[j] answers = append(answers, []int{j, j}) answers = append(answers, []int{j, i}) break } } } fmt.Println("Yes") fmt.Println(len(answers)) for i := 0; i < len(answers); i++ { fmt.Printf("%d %d\n", answers[i][0]+1, answers[i][1]+1) } }
Easyバージョンの解法に囚われすぎて、一歩引いて考えることができませんでした(異なった位置だけ考えると構築がエグい。。とか考えてしまいました)。
- 明らかな必要条件を整理してみる
- 操作回数が固定だったことをもう少し考えてみる
落ち着いてこのあたりができればもう少し違った結果だったかもしれません。
Easyバージョンに引っ張られすぎてHardの思考の幅が狭くなる、というのは以前にも合ったので、もう少し意識的に取り組んだほうが良さそうです。
C. Tile Painting
問題の要約
n
枚の連続するタイルがあり、左から 1, 2, ..., n
と採番されている。
これらのタイルを複数の色で塗り分けることを考える。
任意のタイル i, j
について、 |j - i|
が n
の 1
以外の約数である場合、タイル i, j
は互いに同じ色である場合に、
n
枚のタイルは「芸術的」であるとする。
「芸術的」な塗り方を考えたときに、最大で何色の色で塗り分けることができるか求めよ、という問題。
制約: 1 <= n <= 10^12
解答
※コンテスト中に確信を持って解けたわけではなく、本節の内容は思考過程の整理と反省という意味合いが強いです。
問題文を理解するのがちょっと大変だった。
サンプルを見ると、素数 5
に関しては n
がそのまま答えとなっている。
実際に、あるタイル i
に素数を加算すると存在しないタイルの番号になるため、すべてのタイルを異なる色で塗ることが可能だとわかる。
制約的にも素数判定が O(sqrt(n))
で許されるため、とりあえず早期returnで書き出しておく。
他の場合はどうなるか?
1つ目のサンプル 4
について考えると、2色で塗り分けることが可能となっている。
なんとなく、平方数だと同じようなことが言えそうだとわかり、適当に実験してみると、そもそも素因数分解したときに1つの素数で分解できるならば、
同じように n = p^q
であれば p
が答えとなる、とわかる。
では、素因数分解した結果がそれ以外の場合(複数の素数からなる場合)はどうか?
まず、 1
が答えになりそうだと予想が立てられる。
感覚的には、素数同士は互いに素であるため、例えばタイル 1, 2
を考えたとき、その素数を適当に加算した組み合わせはどこかで衝突しそう、というもの。
実際にいくつか試して衝突は確認した。
上述の衝突が n
以下で必ず起こると主張できれば確信を持って提出できるが、正直コンテスト中はこれ以上詰めきれなかった。
やたらとAC者数が多かったので思い切って投げたら、そのコードが最終的にsystem testもACとなった。
素数判定や素因数分解(試し割り法)は、ともに O(sqrt(n))
であるため、計算量は問題ない。
var n int64 func main() { n = ReadInt64() if n == 1 { fmt.Println(n) return } if IsPrime(n) { fmt.Println(n) return } memo := TrialDivision(n) if len(memo) == 1 { for k := range memo { fmt.Println(k) return } } fmt.Println(1) } // TrialDivision returns the result of prime factorization of integer N. func TrialDivision(n int64) map[int64]int { if n <= 1 { panic(errors.New("[argument error]: TrialDivision only accepts a NATURAL number")) } p := map[int64]int{} for i := int64(2); i*i <= n; i++ { exp := 0 for n%i == 0 { exp++ n /= i } if exp == 0 { continue } p[i] = exp } if n > 1 { p[n] = 1 } return p } // IsPrime judges whether an argument integer is a prime number or not. func IsPrime(n int64) bool { if n == 1 { return false } for i := int64(2); i*i <= n; i++ { if n%i == 0 { return false } } return true }
O(sqrt(n))
が許される場合は、素数判定・約数列挙、素因数分解も同時に手段として考慮すべきなのかもしれません。
公式editorialの証明
まず、 n = p^q
と表せる場合は、 i, j <= n
の異なるタイル i, j
について、
i
と同じ色で塗るべきタイルの番号は i + k*p
、また j
と同じ色で塗るべきタイルの番号は j + k'*p
と表すことができる。
それぞれを p
で割ったあまりは i, j
となるため、 |(i+k*p) - (j+k'*p)|
は p
の倍数とはならず、よって n
の約数とはなりえない。
そのため、 タイル i, j
から好きな n
の約数分番号を進めても決して衝突することはないので、すべて異なる色で塗り分けられる。
また、 n
が2つ以上の異なる素数からなる場合、中国の剰余定理によって、
i, j <= n
の異なるタイル i, j
が n
の約数分番号を進めたときに、 n
以下で必ず衝突すると主張できる。
以下は2元の場合の中国の剰余定理。
gcd(n1, n2) = 1
のとき、連立合同式合同式x = a (mod n1), x = b (mod n2)
を満たすx
が、[0, n1*n2)
の範囲にただ1つ存在する。
ここで、 gcd(p, q) == 1
を満たす p, q >= 2
を用いて、 n = p*q
と表す( n
を素因数分解したときに2つ以上の異なる素数からなる場合には、必ずこのような表現が可能である)。
また、適当なタイルの番号 a, b <= n
について考えると、上記の連立合同式を満たす x
が n
以下(実際にはもっと狭い範囲)に必ず存在すると言える。
よって、タイル a, b
からそれぞれに対して固有の適当な回数分 n1, n2
すすめると、あるタイル x <= n
で衝突することとなる。
そのため、すべてのタイルは同じ色で塗る必要がある。□
中国の剰余定理は今回はじめて触れましたが、2元の場合だけでも覚えておくと、思考のツールとして便利そうです。
整数問題が得意になる気配が感じられません。
Codeforces Round No.598 (Div.3) 参加記録(A〜D解答)
「軽量サイトが動いてさえいればこどふぉはrated」ということを学びました。
- A. Payment Without Change
- B. Minimize the Permutation
- C. Platforms Jumping
- D. Binary String Minimizing
A. Payment Without Change
問題の要約
n
円の硬貨 a
枚と 1
円の硬貨 b
枚でちょうど S
円払えるか判定する問題。
解答
貪欲的に、 n
円で払えるだけ払って差額は1円で払う方法を考える。
x = Floor(S/n)
が S
円に対してできるだけ多くの n
円硬貨で払う場合の n
円硬貨の枚数。
x <= a
ならば n
円硬貨の手持ちの枚数は十分なので、差額の分 1
円硬貨があるかどうかを判定すれば良い。
var q int func main() { q = ReadInt() for tc := 0; tc < q; tc++ { a, b, n, s := ReadInt64_4() x := s / n if x <= a && (s-x*n) <= b { fmt.Println("YES") } else if x > a && (s-a*n) <= b { fmt.Println("YES") } else { fmt.Println("NO") } } }
公式editorialのほうがシンプルでいいですね。
B. Minimize the Permutation
問題の要約
1
から n
までの順列が与えられる。
1
から n-1
までの値を取る i
を考え、各 i
は最大1回まで選べるとする。
選んだ i
に対して i+1
と要素を交換できる。
このような操作は、 i
を選ぶ順番については自由に選んで良いものとする。
このような操作を行ったとき、できるだけ辞書式順序を小さくしようとした場合、最小はどの様になるか求める問題。
解答
選べる範囲の中から最小のものを見つけ、それを移動できる限り前まで運ぶようなシミュレーションを行えば良い。
そうすると、最初は必ず 1
を選ぶ事になり、これを一番前まで運ぶことにより、
i
として 1
から (1の初期位置)
までを1回使ったことになる。
あるいは、最初から 1
が1番目にいる場合は、 i
として 1
を選ぶ必要はないが、
その後、その位置と別の数字がスワップされることはない。
1
の初期位置を idx
とすると、次は [idx, n]
の中から最小のものを選んで、
それを可能な限り前に運べば良い(ただし、 1
の初期位置が最初から 1
だった場合は、 [idx+1, n]
から探索する必要がある)。
正直、思いつくのは簡単で実装がちょっと大変という感じだと思う。
var q int func main() { q = ReadInt() for tc := 0; tc < q; tc++ { n := ReadInt() A := ReadIntSlice(n) s, t := 0, n for s < n-1 { idx := findMinimum(A, s, t) for i := idx - 1; i >= s; i-- { A[i], A[i+1] = A[i+1], A[i] } if idx == s { s++ } else { s = idx } } fmt.Println(PrintIntsLine(A...)) } } func findMinimum(A []int, s, t int) int { mini := 1000 res := -1 for i := s; i < t; i++ { if mini > A[i] { mini = A[i] res = i } } return res }
コンテスト中はバブルソートの転倒数とかそれらしい問題かと思ったら全然違ってWA連発していました。 (誤読に気づいたときには既にこどふぉが落ちていてとてもつらかった。)
C. Platforms Jumping
問題の要約
[1, n]
が水たまりの道に対して、 m
枚の板を使って、
ジャンプ力 [1, d]
の人が水たまりに足をつけずに足場 0
から 足場 n+1
まで到達できるか判定し、
到達できるのなら板の置き方まで構築する問題。
解答
板の情報がランレングス圧縮っぽいと考えた。
すると、最終的に求められる結果が、板の配列の情報を解凍し、さらに m+1
箇所に 0
を複数個挿入する形であると捉えた。
板をすべて使い切ることを考えると、挿入する 0
の数は n - (板の長さの総和)
で計算できる。
また、 m+1
個の複数個の 0
が挿入される区間は、ジャンプで飛び越える必要がある区間である。
そのため、最大で d-1
個までの 0
しか挿入できない。
一方で、 m+1
箇所に均等に 0
を挿入したとしても、
少なくともある1箇所で最大 Ceil((0の個数) / (m+1))
個の 0
を挿入する必要がある。
よって、この値が d-1
以下であれば対岸まで到達可能と判定できる。
構築方法としては、 m+1
箇所に対してジャンプで飛び越えられるギリギリまで 0
を挿入し、
挿入すべき 0
が尽きたならば、あとは板の番号だけをプッシュしていけばよい。
var n, m, d int var C []int func main() { n, m, d = ReadInt3() C = ReadIntSlice(m) csum := Sum(C...) zeroNum := n - csum avg := (zeroNum + ((m + 1) - 1)) / (m + 1) id := 1 if avg <= (d - 1) { fmt.Println("YES") answers := []int{} for i := 0; i < m; i++ { // 0を埋める for j := 0; j < d-1; j++ { if zeroNum == 0 { break } answers = append(answers, 0) zeroNum-- } // C[i]個埋める for j := 0; j < C[i]; j++ { answers = append(answers, id) } id++ } for zeroNum > 0 { answers = append(answers, 0) zeroNum-- } fmt.Println(PrintIntsLine(answers...)) } else { fmt.Println("NO") } }
解けてたんだから諦めずに軽量サイトに投げればよかった。
D. Binary String Minimizing
問題の要約
2進数の文字列が与えられるので、隣同士のスワップ操作を最大 k
回まで行えるとき、
構築可能な辞書順最小の文字列を答える問題。
解答
素直にスワップをシミュレーションするとTLEするので工夫する。
左から文字列を走査したときに出会った 0
に関して、
その 0
を優先的にできるだけ左に移動させるように、貪欲的に考えれば良い。
文字列を走査する過程で暫定で見つけた 0
の数をカウントして保持しておくことで、
0
を見つけるたびにその 0
を一番前に持ってくるのに必要なステップ数が (0の初期位置) - (0の暫定登場回数)
で求まるので、
これを前処理して記憶しておく。
さらに、このステップ数に関して累積和を計算しておくと、
k
と比較することで、確実に前に寄せることのできる 0
の個数がわかる。
一旦、左に寄せ切ることのできる 0
だけを左に寄せて、あとは余分なスワップ操作を行わないで手に入る配列を構築する。
この配列に対して、残った手数で、左に寄せられなかった中で一番左に残存する 0
を、できる限りスワップして左に寄せてやれば良い。
これらは O(n)
で可能なので間に合う。
var q int var n, k int64 var S []rune func main() { q = ReadInt() for tc := 0; tc < q; tc++ { n, k = ReadInt64_2() S = ReadRuneSlice() solve() } } func solve() { zeroNum := 0 for i := int64(0); i < n; i++ { if S[i] == '0' { zeroNum++ } } zeros := make([]int64, zeroNum) j := int64(0) for i := int64(0); i < n; i++ { if S[i] == '0' { zeros[j] = i - j j++ } } zeroSums := make([]int64, zeroNum+1) for i := 0; i < zeroNum; i++ { zeroSums[i+1] = zeroSums[i] + zeros[i] } // c: 確実に先頭に持ってくることができる0の数 c := 0 for i := 0; i < len(zeroSums); i++ { if zeroSums[i] > k { break } else { c = i } } answers := []rune{} for i := 0; i < c; i++ { answers = append(answers, '0') } skipped := 0 for i := int64(0); i < n; i++ { if S[i] == '0' && skipped < c { skipped++ } else { answers = append(answers, S[i]) } } if c == zeroNum { fmt.Println(string(answers)) return } k -= zeroSums[c] for i := int64(c); i < n; i++ { if answers[i] == '0' { for j := i; j > 0; j-- { if k == 0 { break } if answers[j-1] > answers[j] { answers[j], answers[j-1] = answers[j-1], answers[j] k-- } } fmt.Println(string(answers)) return } } }
実装方法は色々ありそうですが、自分としては一番しっくり来るものを選んだつもりです。
色々文句をつけたいコンテストだったけど、 このレベルをサイトが落ちるまでに早解きできない自分が悪いと思って修行します。
Codeforces Round No.597 (Div.2) 参加記録(A〜C解答)
最近関数型プログラミングの勉強ばかりしていて、競技の方が疎かになっていました。
ところどころ脳が停止していたり、不要なWA出してしまったりは避けられなかったのかなと。
※Dは自分にとって貴重なMSTの典型問題なので、どこかで復習し次第追記いたします。
A. Good ol' Numbers Coloring
問題の要約
非負整数に対して黒か白か色を付与していく。
付与の仕方は、
- 0は必ず白
i-a
,i-b
が負数ならi
は黒i-a
が白ならi
は白i-b
が白ならi
は白- いずれでもないなら
i
は黒
という風にすべての非負整数を塗るとき、黒の数は無限か有限かを判定する問題。
解答
全然頭が働かず、なんとなく a, b
が互いに素ならいずれ全部白くなりそう、と直感的に判断し無証明でsubmitしてしまいました。
var t int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { a, b := ReadInt2() if Gcd(a, b) == 1 { fmt.Println("Finite") } else { fmt.Println("Infinite") } } }
これでは良くないので、公式editorialの内容を自分なりに噛み砕いて和訳したものを置いておきます(手書き・悪筆ですみません)。
a, b
が互いに素な場合の証明の要約は、
「ある程度大きな数に関して a
飛びの小さい数を見ると、その中に b
の倍数が必ず1つは含まれている」
というものです。
コンテスト中にここまできっちり証明するのは流石にナンセンスなはずで、 類題をたくさん解いて早く確信に至ることができる、というのがあるべき姿な気がします。
B. Restricted RPS
問題の要約
限定じゃんけんで 相手の出す手の順番がわかっているので、勝負回数の過半数に勝利できるようにする。 勝利できるのであれば、その時の手順を構築して出力する問題。
解答
貪欲に相手の手に対して勝てる手を出していく方針で良い。
事前に相手の手をそれぞれカウントしておいて全体で勝利できるかを判断する。
手の構築については、貪欲に勝利手を割り振る部分と、余った手を適当に割り振る部分に分けるのが楽だと思う。
var t int var n int var a, b, c int var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() a, b, c = ReadInt3() S = ReadRuneSlice() need := (n + (2 - 1)) / 2 r, p, s := 0, 0, 0 for i := 0; i < len(S); i++ { if S[i] == 'R' { r++ } else if S[i] == 'P' { p++ } else { s++ } } wins := 0 wins += Min(a, s) wins += Min(b, r) wins += Min(c, p) if wins >= need { fmt.Println("YES") answers := make([]rune, n) for i := 0; i < n; i++ { answers[i] = 'x' } // 勝てるやつを割り振る for i := 0; i < len(S); i++ { if S[i] == 'R' && b > 0 { answers[i] = 'P' b-- } else if S[i] == 'P' && c > 0 { answers[i] = 'S' c-- } else if S[i] == 'S' && a > 0 { answers[i] = 'R' a-- } } // あまりを割り振る for i := 0; i < n; i++ { if answers[i] == 'x' { if a > 0 { answers[i] = 'R' a-- } else if b > 0 { answers[i] = 'P' b-- } else if c > 0 { answers[i] = 'S' c-- } } } fmt.Println(string(answers)) } else { fmt.Println("NO") } } }
20分は時間かかり過ぎだし、条件式で横着したせいでWAするし、ひどかった。
C. Constanze's Machine
問題の要約
音声入力によって得られた文字列が与えられるが、
機器が細工されてしまったため w
は uu
と、 m
は nn
と入力されるようになってしまっている。
本来入力されたと考えられる文字列の通り数を 10^9 + 7
で割ったあまりを答える問題。
解答
i
文字目まで見たときの通り数がわかっていれば、それをヒントに i+1
文字目まで見たときの通り数もわかりそう、
ということでDPを考える。
問題のポイントとして uuu
や nnn
については uw, wu
や nm, mn
のように、連結させる方法によって複数の解釈が可能なところなので、
これをフラグ管理して考えた。
すなわち、
dp[i+1][0]: i文字目までみて直前の文字が連結されてできたものではない(直前の文字がw, mではない)場合の数
dp[i+1][1]: i文字目までみて直前の文字が連結されてできたもの(直前の文字がw, mのいずれか)の場合の数
とDPテーブルを定義する。
すると、 dp[i+1][0]
については、現在注目している i
番目の文字がいかなる文字であったとしても、考慮される必要がある
(注目中の文字が u, n
のいずれかであっても、それらをそのまま使うという選択肢が取れる)ため、
dp[i+1][0] += dp[i][0] + dp[i][1]
という遷移が行われる。
また、直前の i-1
番目の文字と注目中の i
番目の文字がともに u, n
である場合は、連結を考慮する必要がある。
連結が可能なのは、直前の i-1
番目の文字が連結に使われずに u, n
として単体で残っていることなので、
dp[i+1][1] += dp[i][0]
という遷移でよい。
問題の設定上、 w, m
のいずれかが登場したら0通りとすることに注意。
また、最後に答えを出力するときに dp[n][0] + dp[n][1]
と直接出力してしまわないように注意(1敗、本コンテストで一番反省すべきところ)。
var S []rune var dp [100000 + 5][2]int64 func main() { S = ReadRuneSlice() n := len(S) for i := 0; i < n; i++ { if S[i] == 'm' || S[i] == 'w' { fmt.Println(0) return } } dp[0][0] = 1 for i := 0; i < n; i++ { dp[i+1][0] += dp[i][0] + dp[i][1] dp[i+1][0] %= MOD if i == 0 { continue } if S[i] == 'u' && S[i-1] == 'u' { dp[i+1][1] += dp[i][0] dp[i+1][1] %= MOD } else if S[i] == 'n' && S[i-1] == 'n' { dp[i+1][1] += dp[i][0] dp[i+1][1] %= MOD } } ans := dp[n][0] + dp[n][1] ans %= MOD fmt.Println(ans) }
editorialを見ると、たしかに連結を考慮するパターンは前2つを見る形でよくて、 全体的にスマートですね。
競技プログラミングもたくさんやりたいが、最近業務開発指向の学習も楽しくて時間の使い方が悩ましい。
Codeforces Round No.596 (Div.2) 参加記録(A〜C解答)
Cはちょっと今の自分には難しかった気がするので、せめてBをスムーズに通したかった。
AtCoderの水色帯の人も(詰めが甘くなってしまいsystem testで落としてしまった人は多そうですが、) 本質的な部分は捉えられていてすごいなぁと思いました。
A. Forgetting Things
問題の要約
a + 1 = b
という数式に関して、10進数表記の最上位桁のみがわかっているので、
適当な a, b
を答えよ、という問題。
解答
最上位桁の桁上りが起こるか起こらないか、をベースに考えれば良い。
桁上りが起こる場合は a = x9
などとすればよく、桁上りが起こらない場合は a = x0
などとすればよい。
a
が決まれば b
も自動的に決まる。
b
の最上位桁が a
よりも小さかったり、最上位桁が b
のほうが2以上大きかったりしたら、impossibleとする。
ただし、9からの桁上りのみ例外的に扱わなければならないので注意。
※pretestが優しくて教えてくれましたが、これは入っていなくても文句が言えない初歩的なものな気がするので、要反省案件ですね。。
var da, db int func main() { da, db = ReadInt2() if da == 9 && db == 1 { fmt.Println(9, 10) return } if da > db { fmt.Println(-1) } else if da == db { a := da * 10 b := a + 1 fmt.Println(a, b) } else { if db-da == 1 { a := da*10 + 9 b := a + 1 fmt.Println(a, b) } else { fmt.Println(-1) } } }
B. TV Subscriptions
問題の要約
n
日分のTV番組情報が与えられるので、ある数のショーのみ購読し、
連続 d
日間TVを視聴できるようにしたい。
できるだけ少ない数のショーのみを購読しようとした場合、どれだけ購読すればよいか、という問題。
解答
easyバージョンは、番組情報配列を素直に d
個分切り出して、都度その中に含まれるショーの種類数をカウントすれば良い。
hardバージョンは制約的にそれは許されないため、スライディングウィンドウを考える。
すなわち、毎回注目区間に含まれるショーの種類数を数え直すのではなく、 区間を1つずらした分の差分のみを着目し、端点のみ観て種類数の情報を更新すれば良い。
var t int var n, k, d int var A []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n, k, d = ReadInt3() A = ReadIntSlice(n) subsc := [1000000 + 5]int{} /* ここ危ない! */ ans := 0 for i := 0; i < d; i++ { ch := A[i] if subsc[ch] == 0 { ans++ } subsc[ch]++ } l := 0 tmpAns := ans for r := d; r < n; r++ { subsc[A[l]]-- if subsc[A[l]] == 0 { tmpAns-- } l++ if subsc[A[r]] == 0 { tmpAns++ } subsc[A[r]]++ ChMin(&ans, tmpAns) } fmt.Println(ans) } }
コンテスト中に提出したコードは、各テストケースごとに巨大な固定長配列を取得し直しているため、
1900msec程度かかってしまい、危ないところでした。
固定長配列の部分を make(map[int]int)
と辞書にするだけで150msec程度になりました。
AtCoderではなかなか気にしない部分だったので、これからはメモリ確保にも気を使いたいと思います。
また、尺取法が苦手すぎて、なにか複雑なことをやらなければいけない、と思いこんでしまい、徒に時間を消耗してしまいました。
今回のはウィンドウが固定長で尺取虫の動きをしていないので、しゃくとり法と呼ぶのは良くない気がします。
C. p-binary
問題の要約
2^x + p (x >= 0, -1000 <= p <= 1000)
で表される数をp-binaryと定義したとき、
ある任意の正整数 n
を重複ありのp-binaryの和で表したい。
項の数をできるだけ小さくなるように表したとき、その数はいくらになるか、という問題。
解答
※すぬけさんの解説文を読み解いて考えた内容です。
p-binary x
個を用いて n
を和で表現するとき、 n = n' + x*p (n' は重複ありの2べきの数)
と表すことができる。
式を変形して n - x*p = n'
とすると、 重複を許した2べきの数をちょうど x
個使い、その和で n - x*p
を作れるか? という問題に読み替えることができる。
よって、 n - x*p
が0以下となる場合は、そのような x (>= 1)
は答えとして不適である。
ここで popcount(n - x*p)
を考える。
当然ながら、この数は n - x*p
を2べきの和で表すときの項数の最小値である。
また、 n - x*p
の各bitを分解することで、 n - x*p
は様々な2べきの和で表すことができる。
例えば 2^3
のbitが立っている場合、 2^3 = 8 * 2^0
であり、これらを足し合わせることで項数を 1 ~ 2^3
まで自由に変化させることができる。
これは、任意の立っているbitに対しても同じように分解が可能である。
よって、 n - x*p
を重複を許して2べきの数の和で表すとき、その項数は popcount(n - x*p)
から n - x*p
まで自由に動かすことができる。
以上より、ある x
を決め打つとき、 popcount(n - x*p) <= x <= n - x*p
を満たしていれば、その x
は答えの候補となる。
また、 popcount(n - x*p)
は大きくても高々30程度であるため、 x
を小さいところから調べていけばすぐに停止する。
var n, p int var bits [40]int func main() { n, p = ReadInt2() for x := 0; ; x++ { sum := n - p*x if sum <= 0 { fmt.Println(-1) return } if PopCount(sum) <= x && x <= sum { fmt.Println(x) return } } }
Codeforcesの数学はAtCoderよりも苦手な気がします。
Educational Codeforces Round No.75参加記録(A~C解答)
Bを難しく感じてしまったので、要点を整理して類題に備えたいところ。
あと何故かCでGoの気の利かせたスライス確保をしたら謎のTLE2回出してしまったので、これからはやらないように。
※Bは想定解法がもっとスマートなはずなので、Editorialが公開され次第、追記します。 ※Dは面白そうなので、取り組み次第追記します。
A. Broken Keyboard
問題の要約
26文字のキーボードについていくつかの壊れたキーがあるので、故障していないキーだけを列挙する問題。
壊れたキーを叩くと、その文字について確実に2回タイプされてしまう、というのをヒントに解く。
解答
「確実に故障していない」と断定できるのは、連続で奇数回タイプされた文字だけで、 それを見つけ出して列挙すればいい。
素直に与えられた文字配列を舐めてもいいが、バグが怖いのでランレングス圧縮のスニペットを貼って利用した。
最後の出力についても、同じ文字を2回以上出力してはいけない、ソートして出力する、スペースをいれないなど、 制約が多いので注意。
var t int var S []rune type DirRange []rune func (a DirRange) Len() int { return len(a) } func (a DirRange) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a DirRange) Less(i, j int) bool { return a[i] < a[j] } func main() { t = ReadInt() for i := 0; i < t; i++ { S = ReadRuneSlice() memo := make(map[rune]int) SS, L := RunLengthEncoding(S) for i := 0; i < len(L); i++ { if L[i]%2 == 1 { memo[SS[i]] = 1 } } answers := DirRange{} for key := range memo { answers = append(answers, key) } sort.Sort(answers) fmt.Println(string(answers)) } } // RunLengthEncoding returns encoded slice of an input. func RunLengthEncoding(S []rune) ([]rune, []int) { runes := []rune{} lengths := []int{} l := 0 for i := 0; i < len(S); i++ { // 1文字目の場合保持 if i == 0 { l = 1 continue } if S[i-1] == S[i] { // 直前の文字と一致していればインクリメント l++ } else { // 不一致のタイミングで追加し、長さをリセットする runes = append(runes, S[i-1]) lengths = append(lengths, l) l = 1 } } runes = append(runes, S[len(S)-1]) lengths = append(lengths, l) return runes, lengths } // RunLengthDecoding decodes RLE results. func RunLengthDecoding(S []rune, L []int) []rune { if len(S) != len(L) { panic("S, L are not RunLengthEncoding results") } res := []rune{} for i := 0; i < len(S); i++ { for j := 0; j < L[i]; j++ { res = append(res, S[i]) } } return res }
AGCで太陽したときに作ったスニペットですが、直近のABCでも呼び出したりと、 何かと出番があります。
B. Binary Palindromes
問題の要約
0と1からなる複数の文字列が与えられる。
複数の文字列間、あるいは単一の文字列間でもどちらでも良いので、各文字を交換することが何回でもできる。
できるだけ多くの回文を作ろうとしたとき、最大で何個作れるか、という問題。
解答
まず、全文字列に渡る0、1の数をそれぞれ集計しておく。
回文を作るときは0でも1でも好きな方を2個ずつとり、それを先頭と末尾に配置する形で作っていく。 奇数長の場合は、最後に真ん中の数を0か1のいずれか一方選ぶことになる。
このように考えると、偶数長の回文を考える場合は、1にしろ0にしろ、その総数を2ずつしか減らさないので、 総数の偶奇は変化しない。 よって、必ず偶数長のものはすべて作ることができる。
また、奇数長の回文を作るときは、最後に真ん中の文字を作るために、 残っている数が奇数の文字を選択する。
このような方法をとったときに、最後の奇数長の回文ができるかできないかのいずれかとなるが、 回文が作れるのであれば、全ての文字列が回文となるため、明らかに最適である。
また、回文ができないときは、1と0の残りの数が両方とも奇数個という状態である。 このとき、真ん中の文字として選んだ方を1個減らすとそちらは偶数となる。 もう片方の奇数個ある文字を偶数とするためには、すでに偶数個の文字とすでに出来上がっている回文から、他方を交換して確保するしか無いが、 そうすると偶数個の文字が奇数個となってしまうため、どうあがいても最後の文字列は回文にできない。
以上より、このような方法でできる限りたくさんの回文を作り上げることができる。
var q int var n int var S [][]rune func main() { q = ReadInt() for i := 0; i < q; i++ { n = ReadInt() S = [][]rune{} for j := 0; j < n; j++ { S = append(S, ReadRuneSlice()) } one, zero := 0, 0 for j := 0; j < n; j++ { for k := 0; k < len(S[j]); k++ { if S[j][k] == '1' { one++ } else { zero++ } } } evens := []int{} odds := []int{} for j := 0; j < n; j++ { if len(S[j])%2 == 0 { evens = append(evens, len(S[j])) } else { odds = append(odds, len(S[j])) } } sort.Sort(sort.IntSlice(evens)) sort.Sort(sort.IntSlice(odds)) ans := solve(evens, odds, one, zero) fmt.Println(ans) } } func solve(evens, odds []int, one, zero int) int { ans := 0 // 偶数から for i := 0; i < len(evens); i++ { enum := evens[i] for enum > 0 { if one < 2 && zero < 2 { break } enum -= 2 if one > zero { one -= 2 } else { zero -= 2 } } if enum == 0 { ans++ } } // 次に奇数 for i := 0; i < len(odds); i++ { onum := odds[i] if one == 0 && zero == 0 { break } onum-- if one%2 == 1 { one-- } else { zero-- } // onumは偶数が確定 for onum > 0 { if one < 2 && zero < 2 { break } onum -= 2 if one > zero { one -= 2 } else { zero -= 2 } } if onum == 0 { ans++ } } return ans }
1と0どちらかを使うかの判定で多く残っている方を採用していますが、 おそらくこの部分は意味がないはず。
嘘解法じゃないよね。。?
C. Minimize The Integer
問題の要約
とても大きい桁数の整数値が与えられる。
隣同士の桁の偶奇が異なる場合は、それらを互いに交換してよい。
この操作が何回でもできるとき、与えられた数は最小でいくらになるか、という問題。
解答
交換についてもっと直感的に把握するために、例えば、サンプルの 0709
という数をそれぞれ偶数・奇数というカテゴリでのみ考えると、
EOEO
というような列になる。
OO
や EE
などは交換できないことを考えると、奇数の列だけ考えたとき、それらの相対位置は変えられないことがわかる(偶数列についても同じ)。
なので、まずは奇数と偶数だけを、順番を崩さないようにそれぞれ別にかき集めておく。
あとはこれらを上位桁からどう配置していくかだが、貪欲に上位桁には小さい方を置く方針で良い。 マージソートの要領で、偶数・奇数それぞれを使い尽くすように併合していく。
var t int var S []rune func main() { t = ReadInt() for i := 0; i < t; i++ { S = ReadRuneSlice() // evens := make([]rune, 0, 300000+5) // odds := make([]rune, 0, 300000+5) evens := []rune{} odds := []rune{} for j := 0; j < len(S); j++ { if (S[j]-'0')%2 == 0 { evens = append(evens, S[j]) } else { odds = append(odds, S[j]) } } // answers := make([]rune, 0, 300000+5) answers := []rune{} e, o := 0, 0 for e < len(evens) || o < len(odds) { if e == len(evens) { answers = append(answers, odds[o]) o++ } else if o == len(odds) { answers = append(answers, evens[e]) e++ } else if evens[e] < odds[o] { answers = append(answers, evens[e]) e++ } else { answers = append(answers, odds[o]) o++ } } fmt.Println(string(answers)) } }
コメントアウトした内容で提出したらなぜかTLEしてしまいました。
可変長配列のメモリ再取得がない分早いと思って書いたのですが、裏目に出ました。
少なくともCodeforcesでは、いつもどおり何も考えずに0容量で確保したほうが良さそうです。
Round 596で話題になっていて気づきましたが、 各テストケースでいちいち大きな容量を確保するからTLEしますね。 (あちらのコンテストでは自分のコードは幸いsystem testでも通ったけど、 結構な人が同様のミスで落ちたらしく、話題になっていたため気づきました。) AtCoderでは起こりにくいミスだと思うので、これからはメモリ確保にも気を使わないといけないと感じました。
絶対にBよりこっちのほうが簡単だと思うけど、同じようにBにこだわってC以降見れなかった人が多いのかも。
Div.2は数こなせば4完ぐらいならいけるかな、とか当初は思ってましたが、 最初の3問のどこかで詰まるのが定例化してきたので、どこかで殻を破りたいところ。
といっても、引き続き問題を解いていくしか無いですね。