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問のどこかで詰まるのが定例化してきたので、どこかで殻を破りたいところ。
といっても、引き続き問題を解いていくしか無いですね。
Codeforces Round No.595 (Div.3) 参加記録（A〜C解答）
方針は悪くはなかったけど、C2で慣れないことをしてしまってバグらせて破滅してしまいました（pretestでは露呈せず、system testでREして発覚）。
悲劇を繰り返さないように、ちゃんと記録を残しておきます。
※D, Eともに面白そう、かつ勉強にもなりそうなので、取り組み次第追記します。
A. Yet Another Dividing into Teams
問題の要約
整数からなる数列が与えられるので、2つのできるだけ少ない数のチームに分けたい。
ただし、同じチーム内に整数同士の差の絶対値が1となるようなペアが存在してはいけない。
解答
数列をソートしたときに、隣同士の差がすべて2以上ならば、全員同じチームに入れて問題ないので答えは 1 。
隣同士以外の差の絶対値は確実に2以上になるので、これで問題は起きない。
一方で、隣同士で差が1となるペアが一組でも存在したら、それらは別々のチームに分けなければならない。
また、2組以上存在しても、それらが別のチームに分かれるように配分すれば問題ないので、この場合は 2 とすればよい。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n := ReadInt() A := ReadIntSlice(n) sort.Sort(sort.IntSlice(A)) diffNum := 0 for i := 0; i < n-1; i++ { if AbsInt(A[i]-A[i+1]) == 1 { diffNum++ } } if diffNum > 0 { fmt.Println(2) } else { fmt.Println(1) } } }
B. Books Exchange (hard version)
問題の要約
「1からN番まで採番された子どもたちが、次の日自分が持っている本を上げる相手が記された配列」が与えられる。
もともと自分が持っている本がいずれまた自分に帰ってくるが、その日数を答えよ、という問題。
解答
どの子供たちもなんらかのループに組み込まれるので、そのループの長さを答えれば良い。
easy, hardともに再帰関数を使う同じコードを提出した。
easyの方は制約的に、一度調べたループももう一度調べるような効率の悪いコードを書いても通りそうだが、 hardの方はそれではTLEするはず。
var q int var n int var P []int var flags []bool var answers []int func main() { q = ReadInt() for i := 0; i < q; i++ { n = ReadInt() P = []int{-1} tmp := ReadIntSlice(n) P = append(P, tmp...) flags = make([]bool, n+1) for j := 0; j <= n; j++ { flags[j] = false } answers = make([]int, n+1) for j := 1; j <= n; j++ { if flags[j] { continue } sub(j, 0) } fmt.Println(PrintIntsLine(answers[1:]...)) } } func sub(id, num int) int { if flags[id] { return num } flags[id] = true nextId := P[id] answers[id] = sub(nextId, num+1) return answers[id] }
コンテスト後にtwitter観て気づきましたが、Union-Findでも求まりますね。
ここ数ヶ月Union Find使った記憶がないので、そろそろ手段として思い出しておかないとまずそうです。
C. Good Numbers
問題の要約
3の冪数（1, 3, 9, 27, ...）の部分和で表される数（同じ数値は2回以上使ってはいけない）をGood Numbersと定義する。
与えられた n に対して、 n <= m を満たす最小のGood Number m を答えよ、という問題。
easy versionの解答
3^9 を計算してみると 19683 であるため、答えるべきGood Numberを考えるにあたって、
3^10 以上の冪数は考える必要がない。
また、 3^9 までの冪数を使った部分和の数は、bit全探索で 2^10 個全て列挙できる。
列挙したGood Numbersを配列に集めてソートし、二分探索すれば境界となる m を計算できる。
var q int var n int var G []int var pows [20]int func main() { q = ReadInt() for i := 0; i < 10; i++ { pows[i] = PowInt(3, i) } G = []int{} // すべてのgood numbersを集めておく for i := 0; i < 1<<10; i++ { val := 0 for j := 0; j < 10; j++ { if NthBit(i, j) == 1 { val += pows[j] } } G = append(G, val) } sort.Sort(sort.IntSlice(G)) for i := 0; i < q; i++ { n = ReadInt() // m は中央を意味する何らかの値 isOK := func(m int) bool { if G[m] >= n { return true } return false } ng, ok := -1, len(G) for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } fmt.Println(G[ok]) } }
よくよく考えたら、easyの制約ではクエリごとにGood Numbers配列すべて線形探索しても間に合いますね。
hard versionの解答
今度は 1 <= n <= 10^18 と制約がとても大きくなっている。
同じ要領で全探索しようと思い、 3^39 を計算すると 4*10^18 以上と確認できる。
よって 3^40 以上の冪数は考えなくてよいが、easyの要領でGood Numbersを全列挙しようとしても、
2^40 個になってしまうため、同じ方法ではメモリも時間も足りない。
ここで、2^20 ならば全列挙できることに着目し、半分全列挙を考える。
まず、 3^0 ~ 3^19 までの冪数を用いたGood Numbersを全列挙し、ソートする。
次に、 3^20 ~ 3^39 までの冪数を用いたGood Numbersを全列挙し、ソートする。
これらから互いに1つずつ選んで和を取ると、すべてのGood Numbersを列挙できる。
蟻本に従って、大きい方のGood Numbersすべてに対して、小さい方のGood Numbersの境界を探る二分探索をするやり方だと、
1クエリあたりおおよそ 2^20 * log(2^20) ステップと見積もれるので、最大で500個のクエリに対してこれでは間に合わないとわかる。
よくよく考えると、大きい方のGood Numbersについても単調性があることがわかる。
すなわち、「ある大きい方のGood Numberを採用したときに、
小さい方のGood Numberから何かしら選んで n 以上とできるならば、
大きい方のGood Numbersからさらに大きいものを選んでも n 以上の和を達成することは可能である」と言える。
よって結局、それぞれのGood Numbersの配列を二分探索することでも、題意に沿うGood Numbersが計算できる。
二分探索の条件部分でさらに二分探索をすることになるため、ある n に対する計算ステップは、
大体 log((log2^20)^2) と見積もれる。
全体の、計算量は O(q * (log(2^(n/2)))^2) で間に合う。
var q int var n int64 // var G []int var befG, aftG DirRange var pows [50]int64 type DirRange []int64 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() { q = ReadInt() for i := 0; i < 40; i++ { pows[i] = PowInt64(3, int64(i)) } befG, aftG = make(DirRange, 0, 1000000), make(DirRange, 0, 1000000) // すべてのgood numbersを集めておく for i := 0; i < 1<<20; i++ { val := int64(0) for j := 0; j < 20; j++ { if NthBit(i, j) == 1 { val += pows[j] } } befG = append(befG, val) } for i := 0; i < 1<<20; i++ { val := int64(0) for j := 0; j < 20; j++ { if NthBit(i, j) == 1 { val += pows[20+j] } } aftG = append(aftG, val) } sort.Sort(befG) sort.Sort(aftG) for i := 0; i < q; i++ { n = ReadInt64() aftIdx := decideAftIdx() befIdx := decideBefIdx(aftIdx) fmt.Println(aftG[aftIdx] + befG[befIdx]) } } func decideAftIdx() int { // m は中央を意味する何らかの値 isOK := func(m int) bool { befIdx := decideBefIdx(m) if befIdx < len(befG) { return true } return false } ng, ok := -1, len(aftG) for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } return ok } func decideBefIdx(m int) int { aftVal := aftG[m] // m は中央を意味する何らかの値 isOK := func(m int) bool { s := aftVal + befG[m] if s >= n { return true } return false } ng, ok := -1, len(befG) for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } return ok } // PowInt is integer version of math.Pow // PowInt calculate a power by Binary Power (二分累乗法(O(log e))). func PowInt64(a, e int64) int64 { if a < 0 || e < 0 { panic(errors.New("[argument error]: PowInt does not accept negative integers")) } if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := PowInt64(a, halfE) return half * half } return a * PowInt64(a, e-1) }
コンテスト中に提出したコードでは、「二分探索の条件部分でさらに二分探索する」部分でサボった実装をしてしまい、 特定のケースで落ちる書き方をしていました。
せっかくわざわざ蟻本開いて初めて実践で使ってみたのに、残念。
Editorialのスマートな解法
通している人数からしてももっと簡単なやり方があるのだと思い、こちらもさらっておきます。
Good Numberとは、3進数表現したときに、各桁がすべて 0, 1 のいずれかで表される数と言い換えられます。
なので、与えられた n を3進数表現したとき、 2 の桁が存在しなければそれがそのまま答えになります。
一方で、 2 がどこかの桁に登場したときは、貪欲法の感覚（というよりは桁DPでよく考えるアレ）で、
n より大きい最小の数を構成することを考えます。
このために、以下の図に示すように、 n の3進数表現で2が登場する最上位の桁を調べます。
この桁以下の 2 はすべて潰す必要があるためです。
また、現在の n より大きい数値とするために、調べた 2 の最上位桁のさらに上に存在する、
0 の桁で最初に出会うもの（最下位桁のもの）を調べます。
この桁を 1 とすることで、あらたに 2 の桁は登場させずに、 n よりも大きなGood Numberを構成できます。
さらに、立てた 1 よりも小さい桁はすべて 0 としてしまっても、依然として n よりは大きいGood Numberとできるので、
これが答えとなります。
var q int var pows [40]int64 func main() { q = ReadInt() pows[0] = 1 for i := 1; i < 40; i++ { pows[i] = pows[i-1] * 3 } for tc := 0; tc < q; tc++ { inn := ReadInt64() n := inn ternary := [40]int{} for i := 0; i < 40; i++ { ternary[i] = int(n % 3) n /= 3 } twoIdx, zeroIdx := -1, -1 for i := 0; i < 40; i++ { if ternary[i] == 2 { twoIdx = i } } if twoIdx == -1 { fmt.Println(inn) continue } for i := twoIdx + 1; i < 40; i++ { if ternary[i] == 0 { zeroIdx = i ternary[i] = 1 break } } ans := int64(0) for i := zeroIdx; i < 40; i++ { ans += pows[i] * int64(ternary[i]) } fmt.Println(ans) } }
こういう見方が冷静にできないとだめだなぁと反省しました。
ものにもよるだろうけど、C以降でのeasyとhardでは、一旦思考をリセットしたほうが良さそう。
Codeforces Round No.594 (Div.2) 参加記録（A, B, D1解答）
点数的にCを解きたかったけど、ちゃんとD1に移って得点を確保できたのは、コンテストムーブとしては評価してあげたい。
※Cの数え上げはAtCoderでも活きそうな価値の高そうな香りを感じるので、取り組み次第追記します。
※D2はDiv.1レベルの人もかなり苦戦している問題のようで、おそらくしばらくは取り組まないかと思います。
A. Integer Points
問題の要約
与えられた直線群の格子点の数を求める問題。
解答
問題だけみると難しくも見えそうだが、与えられた直線が傾き1か-1のいずれかで切片が異なるだけなので、 整理するととても簡単になる。
平行な直線は交わらないので無視して、傾きが異なる者同士を方程式にして解いてみると、
x = (q-p)/2 となる。
この x が整数値となれば同時に y も整数値となるため、交点は格子点となる。
ただし、それぞれの傾きの直線の数 n, m の数は大きいので、すべての p, q の組み合わせについて知らべるとTLEしてしまう。
p, q の組み合わせを考えたとき、それぞれの偶奇性が一致していれば格子点になると読み替えられるので、
配列 P, Q の偶数・奇数の数をそれぞれカウントして、それらの掛け算で答えを求める。
var t int func main() { t = ReadInt() for i := 0; i < t; i++ { n := ReadInt() P := ReadIntSlice(n) m := ReadInt() Q := ReadIntSlice(m) peven := 0 qeven := 0 for j := 0; j < n; j++ { if P[j]%2 == 0 { peven++ } } for j := 0; j < m; j++ { if Q[j]%2 == 0 { qeven++ } } ans := int64(peven)*int64(qeven) + int64(n-peven)*int64(m-qeven) fmt.Println(ans) } }
10^5 に引っ張られて32bitでのオーバーフローの可能性を捨てないようにしましょう（1敗）。
B. Grow The Tree
問題の要約
与えられた棒を使って、2次元平面上に端点同士を繋げる形で、またx, y軸にそれぞれ平行となるように配置して「木」を作る。 木の片方の端点を原点に置くとき、もう片方の端点が原点からできるだけ遠くになるように配置したとき、 その長さの2乗を答える問題。
解答
x, y軸に平行になるように棒を設置するにあたって、一度決めた方向とは逆に伸ばすことは、明らかに無意味である。
このようにすると、距離は三平方の定理で (x軸方向に伸びた距離)^2 + (y軸方向に伸びた距離)^2 で求まる。
なんとなくサンプルを見ても、長い棒はできるだけ同じ軸に平行に伸ばす方向に設置したく成るし、実際にそうすれば良い。
var n int var A []int func main() { n = ReadInt() A = ReadIntSlice(n) sort.Sort(sort.IntSlice(A)) l, r := 0, n-1 hori, verti := int64(0), int64(0) for i := 0; i < n; i++ { if i%2 == 0 { // 後から a := A[r] r-- hori += int64(a) } else { // 前から a := A[l] l++ verti += int64(a) } } ans := hori*hori + verti*verti fmt.Println(ans) }
簡易的な証明として、はじめに決めたルール通りに一度決めた方向に伸ばすようにした場合、 x, y軸に伸ばす距離の和は、どのような並べ方をしても一定である。
x, y軸に伸ばす距離を a, b また和を c = a + b とする。
(a+1)^2 + (b-1)^2 を考えると a^2 + 2*a + 1 + b^2 - 2*b + 1 = a^2 + b^2 + 2*(a - b + 1) となるが、
これは a >= b ならばもとの a, b の状態で計算される原点からの距離よりも確実に大きくなる。
よって、一方向についてより長いものを優先的に、もう片方は短いものを優先的に選ぶ、上のアルゴリズムで最大化できる。
。。コンテスト中は、なんとなく一般的に成り立ちそうだな、ぐらいで流してすぐに提出してしまいましたが、 これぐらいならそのムーブで正解かなと思います。
D1. The World Is Just a Programming Task (Easy Version)
なんだこの問題名は。
問題の要約
与えられた丸括弧からなる文字列について、「一度だけ」好きな位置間で交換して良い（同じ場所を交換しても良い＝交換しなくても良い）。
この状態で "cyclical shift" なるものを考える。
これは、後 k 文字を前 n-k 文字の前に移動させてできる文字列のことである。
括弧文字列の美しさを、「すべてのcyclical shiftに対して、正しい括弧列を形成するものの数」と定義する
ある与えられた括弧文字列に対して、前述の交換を施し、考えられる美しさの最大値を答えよ。
解答
交換するインデックスについては1-basedなのに、cyclical shiftを考えるときは0-basedっぽいことに注意。
制約が n <= 500 と小さめなので、全探索を検討する。
すべての交換のペアが 500^500 であり、交換の結果できた文字列の美しさの計算が O(n) でできれば良い。
基本的には、スタックを使った字句解析を行うことで正しい括弧列をつくるcyclical shiftの数を求めた。
もろもろを計算するために、括弧用の char 型とインデックス用の int 型で構造体を定義し、
このインスタンスを用いたスタックを使う。
図に示すように、スタックに残った開き括弧と閉じ括弧について着目する。 このインデックスの間に存在する、正しい括弧列の一番外側のものがcyclical shiftの文字列切り出しの起点となる場合、 cyclical shiftは全体で見て正しい括弧列となる（ただし、図に示すように、いくつかの場合分けが必要）。 また、スタックに残っている開き括弧の最初の位置で切り出しても正しい括弧列となるため、 コード中では最後にインクリメントして返している。
上の説明における、「正しい括弧列の一番外側のもの（図中の赤線のインデックス）」は、
スタックで処理する過程で開き括弧が消えるとき、スタックトップが閉じ括弧、もしくはスタックが空となる場合に、
その開き括弧のインデックスを記憶しておけば良い（コード中の変数 memo に該当）。
var n int var S []rune func main() { n = ReadInt() S = ReadRuneSlice() ans := 0 l, r := 0, 0 for i := 0; i < n; i++ { for j := i; j < n; j++ { // 入れ替える S[i], S[j] = S[j], S[i] tmp := sub() if ans < tmp { ans = tmp l, r = i, j } // もとに戻す S[i], S[j] = S[j], S[i] } } fmt.Println(ans) fmt.Println(l+1, r+1) } type Char struct { idx int c rune } func sub() int { // スタックで字句解析する s := make([]Char, 0, 1000) memo := []int{} for i := 0; i < n; i++ { r := S[i] char := Char{idx: i, c: r} if len(s) == 0 || r == '(' { s = append(s, char) continue } if r == ')' && s[len(s)-1].c == '(' { popped := s[len(s)-1] s = s[:len(s)-1] if len(s) == 0 || s[len(s)-1].c == ')' { memo = append(memo, popped.idx) } } else { s = append(s, char) } } // スタックに何も残っていないときはmemoの長さ if len(s) == 0 { return len(memo) } // 残ったカッコの数をチェック op, cl := 0, 0 for i := 0; i < len(s); i++ { if s[i].c == '(' { op++ } else { cl++ } } // 数が一致しないとダメ if op != cl { return 0 } l, r := 0, 0 for i := 0; i < len(s); i++ { if s[i].c == '(' { r = s[i].idx break } } for i := len(s) - 1; i >= 0; i-- { if s[i].c == ')' { l = s[i].idx break } } ans := 0 for i := 0; i < len(memo); i++ { if l < memo[i] && memo[i] <= r { ans++ } } return ans + 1 }
解いてる人の人数的にCより高得点がほしかった。
公式Editorialの解法について
正直コンテスト中に書いてて辛かったので、もっとスマートに考えるべきだと思い、Editorialも参照しました。
Note that the answer to the question about the number of cyclic shifts, which are correct bracket sequences, equals the number of minimal prefix balances.
具体的にはEditorialにもあるように、閉じ括弧を -1 、開き括弧を 1 としたときに、
全体文字列の累積和を計算し、累積和中の最小値の数が答えとなります。
以下の図に示すように、累積和が最小値を取るところでcyclical shiftを考えると、たしかにそれは全体で正しい括弧列となります。
なぜこれでうまくいくか？
正直、自分はぱっと理解できなかったので、もう少し掘り下げました。
前提として開き括弧と閉じ括弧の数は等しいため、この累積和は最終的に 0 となります。
つまり、ある部分で累積和がマイナス、すなわち閉じ括弧が過剰になったとしても、
その後には過剰分の閉じ括弧を消化できる量の開き括弧が「余分に」存在することが保証されています。
また、cyclic shiftを考えたときに、消化されない余分な閉じ括弧が文字列全体で前方に移動させることはできません。 そのような位置で切り出さないために、 余分な閉じ括弧の数が極大となる「累積和全体での最小値」について着目しなければなりません。
括弧列に関してEditorialのような扱い方をしたことがなかったので、覚えておきたいところ。
（天下一魔力発電とかそんなやり方だったっけ。。？）
Codeforces Round No.593 (Div.2) 参加記録（A〜C解答）
Cの構築難しい。。と思ってたらみんなはやすやすと通していて驚きました。
構築は簡単なものでも刺さらないとずっと解けないので、筋の良い考え方のパターンをためていきたいところ。
※Dは実装方法が参考になりそうなので、取り組み次第追記します。
A. Stones
問題の要約
3つの石が積まれた山から、2通りの決まった石の取り除き方を実行したとき、最大で何個取れるか？という問題。
解答
2番目の方法でできる限りたくさん取って、取れなくなったら今度は1番目の方法でできる限りたくさん取る、でOK。
以下は本番中に考えた直感的な証明。
それぞれ山をA, B, Cとすると、Cから石を取得する方法は2番目の「Bから1つCから2つ」という方法しかない。 もう片方の石のとり方は「Aから1つBから2つ」というものなので、Bの山の減り方に着目すると、先に2番目の方法で取り尽くしたほうが良い。
制約が小さいので、シミュレーションで書きました。
var t int func main() { t = ReadInt() for i := 0; i < t; i++ { a, b, c := ReadInt3() ans := 0 for b >= 1 && c >= 2 { b-- c -= 2 ans += 3 } for a >= 1 && b >= 2 { a-- b -= 2 ans += 3 } fmt.Println(ans) } }
B. Alice and the List of Presents
問題の要約
n 種類のプレゼントを m 人の子どもたちに振り分ける方法は何通りか？という問題。
ただし、ルールが2つあって、
- ある種類のプレゼントについて、ある1人に割り振る数は0個か1個のいずれか。
- ある種類のプレゼントについて、必ず最低1人には1個割り振る必要がある。
解答
ある1種類のプレゼントについて考えたとき、の m 人の子どもたちへの割り当て方を、
m 人の子供をビット列として見立てるとスッキリする。
ビットが立っているときにプレゼントを1個割り振ると考えると、
1 ~ (2^m-1) の割り振り方がある（2の制約から、すべてのビットが0の場合はNG）。
よって、あるプレゼントについては割り振り方が (2^m - 1) 通りあり、
どのプレゼントについてもこれは同じなので、
積事象を考えて (2^m - 1) ^ n が答え。
modpow をスニペットにしているので、それを呼び出して終わり。。
※64bit整数で計算しないとオーバーフローでWAするので注意しましょう（1敗）。
const MOD = 1000000000 + 7 var n, m int64 func main() { n, m = ReadInt64_2() tmp := modpow(2, m, MOD) tmp = NegativeMod(tmp-1, MOD) ans := modpow(tmp, n, MOD) ans %= MOD fmt.Println(ans) } // ModInv returns $a^{-1} mod m$ by Fermat's little theorem. // O(1), but C is nearly equal to 30 (when m is 1000000000+7). func ModInv(a, m int64) int64 { return modpow(a, m-2, m) } func modpow(a, e, m int64) int64 { if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := modpow(a, halfE, m) return half * half % m } return a * modpow(a, e-1, m) % m } // 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 }
C. Labs
問題の要約
n^2 個のラボを n 個のラボからなるグループ n 個に分割したとき、
問題で定義された6パターンの関数値の最小値が最大となるような分割方法を答える問題。
解答
※後半かなり雑です。
あるグループA, B間の関数値を考えたとき、 n * n 通りの大小関係の比較が起こることから、
水の流れる総量は n^2 となる。
なので f(A, B) = x のとき f(B, A) = n^2 - x となる。
よって、最大化した最小値は floor(n^2 / 2) としかならないはず。
このような構築方法は無いかと考える。
。。ここまではコンテスト中かなり時間がかかったものの、気づけて、 そこからは無証明の推測で解きました。
n = 4 の場合を考えると、もとの行列で縦のグループを観たとき、
左から1番目のグループと2番目のグループを比較すると、目的の値に対して不足分があります。
足りないのは floor(n / 2) で、上 floor(n / 2) 行を反転させれば辻褄があう、と考えました。
一応、コンテス中は n = 5 のケースも考えてあっていることを確認し提出しました。
実際には、行ごとに考えたときに矢印の流れが均等になっている（半分の行では矢印が右向きに流れて、もう半分は左向きに流れる）ことに気づくことができれば確信を持てそうです。 下の行から上の行へは矢印は伸びず、逆を考えた場合は必ず矢印が伸びるので、行間では特にグループ間の差を考える必要はありません。
var n int var answers [][]int func main() { n = ReadInt() r := n / 2 answers = make([][]int, n) for i := 0; i < n; i++ { answers[i] = make([]int, n) } for i := 0; i < n; i++ { for j := 0; j < n; j++ { answers[i][j] = i*n + (j + 1) } } for i := 0; i < r; i++ { answers[i] = Reverse(answers[i]) } for j := 0; j < n; j++ { for i := 0; i < n; i++ { if i == n-1 { fmt.Printf("%d\n", answers[i][j]) } else { fmt.Printf("%d ", answers[i][j]) } } } } func Reverse(A []int) []int { res := []int{} n := len(A) for i := n - 1; i >= 0; i-- { res = append(res, A[i]) } return res }
あくまでもコンテスト中の思考整理のために書いた方法なので、 模範解答はEditorialのもとの行列をジグザグにスキャンして各グループに配置する方法がベストかと思います。
「ジグザグに見る」っていうのをパターン化するのは賢くはないが、対症療法にはなりえるかも？
Codeforces Round No.592 (Div.2) 参加記録（A〜D解答）
Cが少しでもいけそうと思ってしまった時点で負けでした。
※Bは通ったものの、正当性の保証が全くできていないのでコードのみ記載します（2019-11-04追記）。
※Cは後日追記します（2019-10-14追記）。
A: Pens and Pencils
問題
※あまりにも問題文が冗長なので、要点のみ。
a 個の講義と b 個の実践演習がある。
1本のペンで c 個の講義のノートを取る事ができ、1本の鉛筆で d 個の実践演習の設計図を描ける。
全部の講義と実践演習をこなしたいが、筆箱の容量はペンと鉛筆合わせて k 本までしか入らない。
すべての講義と実践演習をこなせるか判定し、こなせる場合は筆箱に収まるペンと鉛筆の本数をそれぞれ答えよ。
テストケースは t 個あるため、それぞれについて答えよ。
制約:
1 <= t <= 1001 <= a, b, c, d, k <= 100
解答
答えはなんでも良いので最小化する必要はないが、最小限必要な本数をそれぞれ答えるほうが簡単なので、それを求める。
a 個の講義をこなすために必要なペンの本数と、 b 個の実践演習をこなすために必要な鉛筆の本数は、
それぞれ Ceil(a/c), Ceil(b/d) で求まる。
それの合計が k を超えていなければ、それぞれ出力すれば良い。
var t int func main() { t = ReadInt() for i := 0; i < t; i++ { a, b, c, d := ReadInt4() k := ReadInt() pen := (a + (c - 1)) / c pencil := (b + (d - 1)) / d if pen+pencil > k { fmt.Println(-1) } else { fmt.Println(pen, pencil) } } }
オーバーフローとゼロ除算に注意するぐらい。
B. Rooms and Staircases
問題
※問題URLの図がわかりやすいため、ここでは要点のみ。
Nikolayは2階建ての家に住んでいる。家のそれぞれのフロアには n 個の部屋があり、一列に並んでいる。
左から 1 ~ n の番号が振られている。
同じフロアの隣り合っている部屋はすべて移動可能である。 また、いくつかの部屋には1階と2階をつなぐ階段がある場合があり、その場合は、各階同じ番号の部屋を行き来できる。
Nikolayは以下の2つのルールを守りながら、できるだけ多くの部屋を回りたい。 回れる部屋の最大個数を答えよ。
- スタートする部屋は好きに選ぶことができる。
- 一度通った部屋は二度と通ることはできない。
t 個のテストケースに対して答えよ。
制約:
1 <= t <= 1001 <= n <= 1000
解答
※とりあえずはコードのみ。
いずれかのフロアの端の部屋から出発したほうがよく、出発地点からできるだけ遠くの階段のある部屋まで移動する。 階段を使ったあとは、また別フロアの出発地点の部屋番号の部屋まで戻る。
複数の出発地点のうち、回ることができた部屋数が大きい方を出力する。
var t int func main() { t = ReadInt() for i := 0; i < t; i++ { n := ReadInt() S := ReadRuneSlice() allZero := true for i := 0; i < n; i++ { if S[i] == '1' { allZero = false break } } if allZero { fmt.Println(n) continue } if S[0] == '1' || S[n-1] == '1' { fmt.Println(2 * n) continue } minIdx, maxIdx := 0, n-1 for j := 0; j < n; j++ { if S[j] == '1' { minIdx = j break } } for j := n - 1; j >= 0; j-- { if S[j] == '1' { maxIdx = j break } } res := Max(2*(maxIdx+1), 2*(n-(minIdx))) fmt.Println(res) } }
正当性はどうやって保証するのだろう。。？
後日公式editorialが公開されたので、そちらの内容を追記します。
最も左の部屋にある階段を l 、最も右の部屋にある階段を r とすると、
それらの部屋で区切られる端っこの4つの部屋のセグメントが重要となります。
これらのセグメントは、スタート地点として選ぶことを除けば、一度入ってしまうともう出られないセグメントといえます。
スタート地点として選んだとしても、これらの4つのセグメントのうち、同時に通過できるのは2つまでであり、 それ以外の部屋も通過することを考えると、解答に示したような「左端の部屋から左端の部屋へ or 右端の部屋から右端の部屋へ」のいずれか大きい方を選ぶ通過の仕方が最大となります。
C. The Football Season
問題
Berlandのフットボールのシーズンが終わった。
Berlandフットボールのルールによると、それぞれの試合は2つのチームで争われる。
試合結果は、引き分けかどちらか片方のチームの勝利・敗北のいずれかである。
チームが勝つと勝利チームに w ポイントが入り、負けると敗北チームは点数を獲得できない。
また、引き分けの場合は両チームに d ポイントが入る。
マネージャは結果をまとめようとしたが、詳細を紛失してしまい、
残されているのは n 試合で p ポイント獲得した、という情報のみだった。
これらの情報から x, y, z 、すなわち勝利数、敗北数、引き分け数を求めて出力せよ。
答えが存在しない場合は -1 を出力せよ。
制約: 1 <= n <= 10^12, 0 <= p <= 10^17, 1 <= d < w <= 10^5
解答（2019-10-14追記）
制約が大きすぎるため、愚直に全探索するとTLEしてしまう。
以下の2つを抑えると、全探索の範囲を大幅に小さくできる。
w > dのため、xをできるだけ大きくした方が良い、すなわち、yは小さい値から探索すれば良い。- 1と併せて考えると、
y < wまでの探索で打ち切って良い。
1はほとんど自明だが、2は以下のようにして考えられる。
y = m*w + y' (m >= 0, 0 <= y' < w)とすると、y試合引き分けとなったことによって取得できる点数はd*y = d*m*w + y'*dである。 ここで、得点d*m*wはd*m試合勝った場合の得点と同じである。 1より、y試合引き分けと考えるよりもy'試合引き分けと考えたほうが良いため、0 <= y < wで十分。
y が決まれば x, z も与えられた方程式から順に決まるため、それぞれ0以上の整数であればそれを出力すれば良い。。
var n, p, w, d int64 func main() { n, p, w, d = ReadInt64_4() for y := int64(0); y < w; y++ { if (p-d*y)%w == 0 { x := (p - d*y) / w z := n - x - y if x >= 0 && y >= 0 && z >= 0 { fmt.Println(x, y, z) return } } } fmt.Println(-1) }
Codeforcesの本コンテストのブログのやりとりを参考にしました。 （多分、整数問題たくさん解いてきた人には典型なんだろうなぁ。）
本番中は拡張ユークリッドの互除法に固執してしまい、全く手が出ませんでした。
さっさと諦めるのがベストだったので、愚直に問題と向き合うだけではなく、選球眼も磨いていきたいところです。
D. Paint the Tree
問題
n 頂点からなる木が与えられる。
木は、無向で連結で閉路のないグラフである。
木の各頂点を、3つの色のうち1つを選んで塗らなければならない。 各頂点について、いずれかの色で塗る場合のコストがわかっているとする。
色を塗る際は、以下のルールに従う必要がある。
木の任意の3つの頂点として、
(x, y, z), x != y, y != z, z != x, xとyは1つの辺でつながっている, yとzは1つの辺でつながっているというものを考えたとき、x, y, zはそれぞれ違う色で塗られなければならない。
このようなルールのもとですべての頂点を塗るときの、最小コストを求めよ。
また、塗り方が存在しない場合は -1 を出力せよ。
解答
一見、色々なことをやらなければいけないように見えるが、 以下の図に示すように、ある頂点の次数が3以上になるともうアウトになってしまうことがわかる。
よって、すべてのノードの次数は2以下でなければならず、ノードが一列に並んだような木しか考えなくて良い。
次に、その塗り方も単純で、次数が1のノードから塗り始めて、つながっているまだ塗っていないノードを順次塗っていくと、 最初の2つの色を決めた時点で、以降は自動的に塗るべき色が定まることがわかる。
図にも示したとおり、塗り方はせいぜい12通りしかないため、その 塗り方をすべて試して最小の塗り方はどれか、を調べれば良い。
訂正:
くるさんより訂正いただきました。
順方向の6通りだけで十分網羅できています（2つの連続ノードの塗り方は、2色の選び方が Comb(3, 2) 通りでその2色の並べ方が 2! 通りのため積で6通り、そして2つ決まればすべてが決まるので6通りで十分）。
実装部分が本体だと思うので、コードについても補足。
次数を調べたりする部分は素直にやればよいが、色の塗り方の持ち方などは色々な方針がある。 なるべくバグらせないように気をつけながら、実装方針として以下のように考えた。
- 毎回根から探索するのは大変なので、ある根から見た頂点のつながっている順番を配列で持っておく（
orders）。 - 12通りの塗り方について、各ノードの色をすべて保存しておく（
howto）。 - 各塗り方については前処理に従ってコストの計算のみに集中する。
var n int var C [4][]int var edges [100000 + 5][]int var degins [100000 + 5]int var howto [20][100000 + 5]int var orders [100000 + 5]int func main() { n = ReadInt() C[1] = ReadIntSlice(n) C[2] = ReadIntSlice(n) C[3] = ReadIntSlice(n) for i := 0; i < n-1; i++ { u, v := ReadInt2() u-- v-- edges[u] = append(edges[u], v) edges[v] = append(edges[v], u) } for i := 0; i < n; i++ { for _, e := range edges[i] { degins[e]++ } } for i := 0; i < n; i++ { if degins[i] > 2 { fmt.Println(-1) return } } roots := []int{} for i := 0; i < n; i++ { if degins[i] == 1 { roots = append(roots, i) } } dfs(roots[0], -1, 0) temp := [][]int{ []int{1, 2, 3}, []int{1, 3, 2}, []int{2, 1, 3}, []int{2, 3, 1}, []int{3, 1, 2}, []int{3, 2, 1}, } for i := 0; i < 6; i++ { for j := 0; j < n; j++ { howto[i][orders[j]] = temp[i][j%3] } } for i := 6; i < 12; i++ { for j := 0; j < n; j++ { howto[i][orders[n-1-j]] = temp[i-6][j%3] } } ans := int64(1 << 60) ansOrderIdx := -1 for i := 0; i < 12; i++ { tmpAns := int64(0) for j := 0; j < n; j++ { c := howto[i][j] tmpAns += int64(C[c][j]) } if ans >= tmpAns { ans = tmpAns ansOrderIdx = i } } fmt.Println(ans) for i := 0; i < n; i++ { if i == n-1 { fmt.Println(howto[ansOrderIdx][i]) } else { fmt.Printf("%d ", howto[ansOrderIdx][i]) } } } func dfs(cid, pid, curIdx int) { orders[curIdx] = cid for _, e := range edges[cid] { if e == pid { continue } dfs(e, cid, curIdx+1) } }
実装ゲーでした。 強い人達は「冗長、虚無」といった感想だったようですが、 自分レベルだと実装面ではできるだけバグらせにくい実装を考える労力が必要で、 やる価値はあるかと思います。
個人的な体感難易度は A < D < B << C でした。
Codeforcesはフルフィードバックはないことを加味すると、自分の性格上、AtCoder以上に早解き勝負に期待できないので、 すこしでも詰まったら積極的に次の問題にシフトしたほうが良さそうです。
Educational Codeforces Round No.74参加記録（A~D解答）
Cで本当にしょうもないミスをしてしまった。。
A. Prime Subtraction
問題
2つの整数 x, y が与えられる。 x > y であることが保証されている。
好きな素数 p を選んで、その素数を何回でも x から引くことが出来る。
そのようにして、 x を y と等しくなるように出来るか答えよ。
t 個の独立したテストケースに対して答えよ。
制約: 1 <= t <= 1000, 1 <= y < x <= 10^18
解答
x から適当な回数素数 p を引いて y にする、という部分をそのまま数式にすると、
x - n*p = y <=> p = (x-y)/n
x-y を適当な x-y の約数（1でもよい）で割った商を何かしらの素数にできるか？と考える。
x-y を素因数分解したときを考えると、適当な素数が残るような約数を選択できることがわかるので、 x-y が2以上であればOK。
1のときは、そのような n = 1 とするしかないため、適当な素数が選べない。
var t int func main() { t = ReadInt() for i := 0; i < t; i++ { x, y := ReadInt64_2() if x-y >= 2 { fmt.Println("YES") } else { fmt.Println("NO") } } }
B. Kill 'Em All
問題
※とても問題が長いので、適宜意訳。
Ivanはとあるゲームの最終ステージに苦労しており、全てのモンスターを倒すために手助けを必要としている。
ステージはとても長い廊下（無限に伸びる数直線でモデル化できる）からなっている。
廊下は x = 0 で2つの部分に分けられる。
右側は、 n 体のモンスターが存在し、位置は座標 X[i] で表される。
左側は、罠で埋め尽くされており、モンスターが負の座標に位置までやってきた途端、罠によってモンスターは死ぬ。
Ivanの武器はフェニックスロッドによる爆破であり、選択した爆破位置 c によって、モンスターたちは以下のような反応をする。
モンスターの座標を y とする。
c = yならば、モンスターは爆殺される。y < cならば、モンスターは左にr押し出される（モンスターの位置はy - rとなる）。y > cならば、モンスターは右にr押し出される（モンスターの位置はy + rとなる）。
Ivanは、できるだけ少ない爆破回数でモンスターを全滅させたい。
q 個の各クエリについて、最小の必要爆破回数を答えよ。
制約:
1 <= q <= 10^51 <= n, r <= 10^51 <= X[i] <= 10^5- クエリに渡って
nの合計は10^5を超えない。
解答
できる限り X[i] の大きいモンスターから爆殺していく貪欲法で良い。
これは以下の理由から正しいと言える。
まず、モンスターを直接攻撃しない、という戦略は損しかしない。 問題の設定上、モンスターを爆風で右に吹き飛ばすのは無意味であり、 モンスターを直接攻撃しないのであれば、無限遠の正の座標を爆破して、すべてのモンスターを左に寄せるほうがマシである。
また、そのようにするならば、一番右に存在するモンスターを直接狙う方が明らかに得である。
実装は、爆破回数を覚えておくことで、都度チェックしているモンスターの現在位置が計算できるので、 一度罠にかかったらbreakすればよい（自分の解答では横着をしていてbreakしていない）。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n, r := ReadInt2() X := ReadIntSlice(n) memo := make(map[int]int) for _, x := range X { memo[x] = 1 } XX := []int{} for k := range memo { XX = append(XX, k) } sort.Sort(sort.IntSlice(XX)) nn := len(XX) fmt.Println(XX) // m は中央を意味する何らかの値 isOK := func(m int) bool { // 後ろのモンスターから爆殺 cnt := 0 for j := nn - 1; j >= 0; j-- { // j番目に殺すモンスターの座標 xx := XX[j] - cnt*r if xx > 0 { // 爆殺する cnt++ } } if cnt <= m { return true } return false } ng, ok := 0, len(X) for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } fmt.Println(ok) } }
実際のところ、コンテスト中は貪欲法の正しさがあまりはっきりと認識できなかったため、二分探索のコードを書いて爆破回数の境界値を探ってしまいました （ほとんど書き終わってから結局意味がないことに気づきました）。 とはいえ、計算量的には間に合うだろうと思って、書き直してバグを生むことのほうが懸念されたので、このまま提出しました（system test終了後、460msecとなっていました）。
問題文が長くて読むのが大変、かつコンテスト中は致命的な部分（爆風による吹き飛び方の部分）にタイポがあったため、かなりストレスでした。
C. Standard Free2play
問題
※適宜意訳
高さ h の崖を下るゲームがある。
1 ~ h の各整数位置 x に動く足場が存在する。
足場は、崖の中に隠れているか、崖から露出して飛び出しているかの2つの状態がある。
初期状態では n 個の位置 P[1], ..., P[n] の足場が露出して飛び出している状態である。
キャラクターの初期位置は h であるため、 h の足場は初期状態で飛び出ている。
キャラクターは、 x の足場に居るときにレバーを引くことができ、レバーを引くと x, x-1 の2つの足場の状態が変化する。
キャラクターが立っている x の足場は崖に引っ込むため、キャラクターは落下することになる。
キャラクターはとても華奢であるため、安全に着地できるのは段差2以下の落下までである。 それ以上の落差で落下すると死亡してしまう。
状況によっては、安全に下に降りることができなくなってしまうが、いつでも購入可能な魔法のクリスタルを購入することで、 好きな足場1つの状態を変化させることができる。 クリスタルは使うと消滅する。
安全に地面 0 に着地するために、必要なクリスタルの最小個数はいくつか答えよ。
制約:
1 <= q <= 1001 <= h <= 10^9, 1 <= n <= 2*10^5h = p[1] > p[2] > ... > p[n] >= 1- 各クエリに渡った
nの合計は2*10^5を超えない。
解答
今現在キャラクターが存在する足場は露出しており、その1つ下の足場が露出しているか、隠れているかの2つの場合がある。
1のケースにあたった場合、2つ下の足場が露出していれば、無事に着地できるが、そうでない場合は3以上の落差で落下し死亡してしまう。 よってこれを回避するためにクリスタルを使う必要があるが、例えば、2つ下の足場をクリスタルによって露出させることで、落下死を防げる。
これを、足場を配列に見立てて素直にシミュレーションすることを考えたが、 h の範囲が大きいのと、
工夫をしたとしてもとても複雑でバグりやすいコードになりそうだったため、これは避けた。
結局の所、露出している足場が連続している部分に注目すればよいとわかる。
図のように、露出した足場の連続する部分の個数が、キャラクターが現在立っている足場を含めて奇数個ならば無事に降りれる。 そうでなければ、クリスタルで連続部の1つ下を、クリスタルで露出させる必要がある。
よって、例えばサンプルの3番目のクエリだと、以下の図のように、2箇所クリスタルで露出させる必要がある。
以上から、与えられた足場の列の連続部分に着目すれば、シミュレーションを簡略化でき、答えが求められる。 実装に際しては、いくつか注意すべき点がある。
- 最初の列だけは若干足場の数のカウントに注意する必要がある（立っている足場が途中経過によらずに
hで確定しているため） - 最後の列だけは、連続部が偶数個であっても、最後尾が1の場合はクリスタルは不要（キャラクタは2から0へ飛び降りることになるため）
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { _, n := ReadInt2() P := ReadIntSlice(n) ans := 0 num := 1 // 現在位置を1つとしてカウント j := 0 for j < n-1 { if P[j]-P[j+1] == 1 { // 差が1なら、列の長さをインクリメント、jは1つ先へ num++ j++ } else { // 差が2以上なら、列の長さは打ち止め、かつそれまでの列の長さが偶数なら購入する if num%2 == 0 { ans++ } // 列の最初をP[j+1]+1とする num = 2 j++ } } if num%2 == 0 { if P[n-1] >= 2 { ans++ } } fmt.Println(ans) } }
キャラクタは2から0へ飛び降りることになるため
。。コンテスト中は、この部分に気づいていたにもかかわらず、なぜか P[n-1] >= 2 の部分を P[n-1] >= 3 と書いてしまい
pretestすら通すことができませんでした。
別のコード
自分の頭のメモリ不足と言われたらどうしようもないですが、このようなシミュレーションのように、 「連続部の長さを数えながら、見ているセグメントの位置によっては微妙に処理内容を変える」というのは、結構脳に負担がかかります。 実際、コンテスト中も他の部分がバグっているのかと思い、初歩的な部分を見落としてしまいました。
リーダブルコードの149ページにも「一度に一つのタスクを適用する」というのがあるので、 それに倣って、
- 連続部の計算を別に事前に行っておく。
- 使用するクリスタルのカウントは別で集中して行う。
という方針でも書いてみました。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { _, n := ReadInt2() P := ReadIntSlice(n) ans := 0 tmp := []int{0} for j := 0; j < n-1; j++ { if P[j]-P[j+1] >= 2 { tmp = append(tmp, j+1) } } tmp = append(tmp, n) rows := [][]int{} for j := 0; j < len(tmp)-1; j++ { idx1, idx2 := tmp[j], tmp[j+1] rows = append(rows, P[idx1:idx2]) } if len(rows) == 1 { R := rows[0] if len(R)%2 == 0 && R[len(R)-1] >= 2 { fmt.Println(1) } else { fmt.Println(0) } continue } for k, R := range rows { if k == 0 { if len(R)%2 == 0 { ans++ } } else if k == len(rows)-1 { l := len(R) + 1 if l%2 == 0 && R[len(R)-1] >= 2 { ans++ } } else { l := len(R) + 1 if l%2 == 0 { ans++ } } } fmt.Println(ans) } }
。。今度は連続部が1つのみの場合について例外的に扱う必要が出てきてしまいました。
このあたりの強い人達がやっているベストプラクティスが知りたいところです。
D. AB-string（2019-12-08追記）
問題の概要
文字列 S について、 S を構成するすべての文字が、2文字以上の S の部分文字列でありかつ回文であるものに含まれているとき、
この文字列 S をgoodとする。
与えられた文字列について、goodな部分文字列の個数を求めよ、という問題。
解答
※基本的に公式editorialの解法をなぞったものです。
goodな文字列というのを考えるにあたって、goodとならない原因となる文字、すなわち回文に含まれない文字のことをnot goodな文字と呼ぶ。
冷静に整理すると、ある文字列 S = ox..xo について、not goodな文字となる可能性があるのは、先頭と末尾の文字だけである。
なぜなら、それ以外の内部の文字について、隣に等しいものがあればそれ自体が回文になり、両隣が異なるときは3文字の回文となるためである。
よって、goodじゃない文字列というのは、1文字の文字列を除くと、以下の4パターンになる。
^AB+$^BA+$^A+B$^B+A$
これを数えて全体から引くことで、goodな文字列の数が求まる。
。。editorialはここまでで、実装についてはpythonのシンプルなコードが用意されているが、正直何をやっているのかよくわかりませんでした。
自分は最近特にお気に入りのランレングス符号化を仲介して数えました。
var n int64 var S []rune func main() { n = ReadInt64() S = ReadRuneSlice() ans := n * (n - 1) / 2 pressed, counts := RunLengthEncoding(S) length := len(pressed) for i := 0; i < length; i++ { if i+1 < length { ans -= int64(counts[i+1]) } if i-1 >= 0 { ans -= int64(counts[i-1]) } } // 重複して減らした部分を補正 ans += int64(length - 1) fmt.Println(ans) }
はじめ dp[i]: i番目の文字が末尾となるgoodな文字列の数 というDPを考えて、最後に総和を取ろうとしたのですが、
遷移がうまく定義できずに諦めました（なんかできそうな気もするけど）。
感想
Cなんかは特別なアルゴリズムを使っているわけではないので、純粋な実装力不足が目立つあたり落ち込みますね。。
C++の優れたコードをちゃんと読んで自分のコードにも適用したいので、C++もちょこちょこ勉強してスムーズに読めるぐらいはしておいたほうが良さそうです。
