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問のどこかで詰まるのが定例化してきたので、どこかで殻を破りたいところ。
といっても、引き続き問題を解いていくしか無いですね。
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のもとの行列をジグザグにスキャンして各グループに配置する方法がベストかと思います。
「ジグザグに見る」っていうのをパターン化するのは賢くはないが、対症療法にはなりえるかも？
