Educational Codeforces Round No.77 参加記録（A〜D解答）
A. Heating
問題の概要
k セクションある1つの暖房器具を設置するとコストが k^2 かかる。
最大 c 個の暖房器具を設置することで合計 sum セクション確保したい。
このときに必要となるコストの最小値はいくらか計算せよ、という問題。
解答
英語とサンプルでやるべきことが理解できたら80％ぐらいACだと思う（heating radiatorはともかくsectionって何？）。
以前のこどふぉで解いた問題の、逆に今度は小さくするバージョン、という感じ。
結論から言うと、できるだけ c 個の暖房器具のセクションが均等になるように選べば良い。
直感的には、2次元の場合のマンハッタン距離を考えたとき、
マンハッタン距離が同じ点の中では x=y の点がユークリッド距離が一番小さくなる、というのを多次元に考えている。
本番中に書いたコードでは、 c >= sum の場合を例外的に扱っているが、多分これは不要。
var n int var C, S []int64 func main() { n = ReadInt() C, S = make([]int64, n), make([]int64, n) for i := 0; i < n; i++ { c, s := ReadInt64_2() C[i], S[i] = c, s } for i := 0; i < n; i++ { c, sum := C[i], S[i] if c >= sum { fmt.Println(sum) continue } x := sum / c m := sum % c ans := x*x*(c-m) + (x+1)*(x+1)*m fmt.Println(ans) } }
15分はかかり過ぎだが、英語が難解すぎた。
B. Obtain Two Zeroes
問題の概要
非負整数 a, b が与えられる。
以下の2つの操作、
a := a - 2*x, b := b - xa := a - x, b := b - 2*x
を何回でも実行可能なとき、両方を同時に 0 にすることはできるか判定する問題。
解答
まず、それぞれの操作において x = 1 に操作を限定して良い
（ x = n とした場合、選んだ操作を x=1 で n 回実行した、と等しく考えることができる）。
それぞれの操作について、操作後の a, b の和を計算すると、ともに a + b - 3 となる。
つまり、いずれの操作を選んだとしても a, b の和は 3 ずつ減っていくこととなる。
よって、両方同時に 0 にするためには、 a, b の和が 3 の倍数であることが必要条件となる。
そして a, b の和が 3 の倍数のとき、 (a+b)/3 = m とすると、 m は両方同時に 0 にするために必要な操作回数となる。
また、1の操作を行った場合、 a の方を b よりも 1 多く減らせることになり、2の操作ではその逆となる。
つまり、 Abs(a - b) = diff とすると、 diff 分は両方同時に 0 とするために差を詰める必要があり、
これには diff 回のいずれか片方の操作が必要となる。
よって diff > m ならば先に片方が0に到達してしまうのでNOとなる。
一方で、 diff <= m ならば diff 回の操作で a, b を等しくすることが出来、
残った回数で a+b をピッタリ 0 にできることも保証されているので、結局、 diff > m ならばNO、そうでないならばYESとすればよい。
（コンテスト中はもう少し複雑に考えてしまった。）
var t int var a, b int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { a, b = ReadInt2() solve() } } func solve() { if (a+b)%3 != 0 { fmt.Println("NO") return } m := (a + b) / 3 diff := AbsInt(a - b) if diff > m { fmt.Println("NO") } else { fmt.Println("YES") } }
最近AtCoderで和を考えると不変量が見える〜みたいなのが2回ほどあったので、その反省が活かせて嬉しい。 と思ってたら、フレンドがみんな難なく通していてやっぱり悲しい。
C. Infinite Fence
問題の概要
無限に左から右へと並べられた板の列があり、左から 0, 1, ... と採番されている。
r, b の2つの正の整数が与えられ、以下のルールに基づいて、この板を塗っていく。
- 板の番号が
rで割り切れるのならば、その板を赤で塗る。 - 板の番号が
bで割り切れるのならば、その板を青で塗る。 - 板の番号が
r, bのいずれでも割り切れるのならば、その板を赤か青の好きな色で塗る。 - いずれでもないならば、その板は塗ってはいけない。
このようにして無限の板を塗っていき、塗られていない板を除外する。
このとき、連続する k 個の板が同じ色で塗られることを避けられるかどうかを判定する問題。
解答
とりあえず図を描いて考えてみると、 r, b の公約数を周期として、同じようなパターンが続くことがイメージできる。
そこで、最大公約数までをもう少し掘り下げて考えてみることにする。
まず、 r >= b であると仮定する（そうでない場合は、2つの数を入れ替えて考えれば良い）。
例えば、 r = 5, b = 2 のケースを図示すると、連続する列の長さが長くなるのは、値が小さい青色の方であるとわかる。
よって、 r >= b で一般化して、ある赤と赤に囲まれた区間を考える。
図のように、どのような区間でも青は b 間隔で並び、右端の赤が b の約数である、すなわち r, b の公約数であったとしても、
それは赤として考えれば良い（そのほうが k 個連続するのを避けるためには有利であるため）。
ここで、板全体を俯瞰したときに、青の連続する列の長さが最長となるのは、区間の左端の赤と青の板の番号の差が最小となる場合であるとわかる。
サンプルをいくつか試すと、「なんとなく Gcd(a, b) が最小値となりそう」とわかる。
。。コンテスト中はこれ以上時間を費やせず、とりあえずWAしたらまた考えようという気持ちでsubmitしたら通ってしまった。
var t int var r, b, k int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { r, b, k = ReadInt3() solve() } } const obey = "OBEY" const rebel = "REBEL" func solve() { if r < b { r, b = b, r } g := Gcd(r, b) m := (r-1-g)/b + 1 if m < k { fmt.Println(obey) } else { fmt.Println(rebel) } }
以下は、コンテスト後に書いた簡単な証明です（雑な手書きですみません）。
なんとかコンテスト中に解けたけど、時間がかなりかかったし難しい。。
具体的な例で仮説を立て、抽象化して検証する、場合によってはまた具体的な例に戻る、というのを自分は特別意図せずやっていますが、 もう少しスマートに短時間でできれば良いなぁとは思います（賢くなりたい）。
D. A Game with Traps
問題の概要
※大分端折っているので、詳しくは本文をご参照ください。
0, 1, .., n+1 のマス目を初期位置 0 からゴール n+1 を軍隊を引き連れながら目指す。
ただし、道中にはトラップがあるため、軍隊の兵士がそれを踏んで死なないようにして進まなければならない。
一方で、兵士1人1人に設定されている agility のパラメータが、トラップの威力以上である場合には、兵士はそのトラップの影響を受けない。
トラップは、トラップの先にある解除用ボタンの位置まで到達することで解除できる。
軍隊は、自身と一緒にしか移動できず、1マス移動するには1秒かかる。
t 秒間与えられたときに、ゴールまで引率できる兵士の数の最大値はいくらかを堪える問題。
解答
引率できる兵士はagilityの高い順であり、あるagilityの兵士がゴールできるならば、それ以上のagilityの兵士も全員ゴールできる。
よって、ゴールできるagilityの最小値を二分探索で求めることを考える。
あるagilityの兵士がゴールにたどり着けるかどうかの判定は、以下のようにして可能である。
あるトラップに対して、区間 [l, r] を考えると、この区間に関しては、少なくとも3回通過する必要がある。
すなわち、トラップの解除に向かうとき、元の位置に戻るとき、軍隊を引率して進行するときの3回である。
トラップの区間が交差している場合は、逐次トラップの区間を3回通過する必要はなく、 交差する区間をすべてマージして、その区間を3回通過するほうが、経過時間は短くなる。
よって、現在注目中のagilityに対して、影響を考慮すべきトラップの区間をマージすることで、
必要な時間を計算できる。
すなわち、マージ後の区間に関して、全区間が含んでいるマス目の合計数を T とすると、
n + 1 + 2*T で計算できる。
var m, n, k, t int var A []int type Trap struct { key int l, r, d int } type TrapList []*Trap type byKey struct { TrapList } func (l TrapList) Len() int { return len(l) } func (l TrapList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l byKey) Less(i, j int) bool { return l.TrapList[i].key < l.TrapList[j].key } // how to use // L := make(TrapList, 0, 200000+5) // L = append(L, &Trap{key: intValue}) // sort.Stable(byKey{ L }) // Stable ASC // sort.Stable(sort.Reverse(byKey{ L })) // Stable DESC var L TrapList func main() { m, n, k, t = ReadInt4() A = ReadIntSlice(m) L = make(TrapList, 0) for i := 0; i < k; i++ { l, r, d := ReadInt3() L = append(L, &Trap{key: l, l: l, r: r, d: d}) } maxAgility := Max(A...) // 区間の左端で昇順ソート sort.Stable(byKey{L}) // m は中央を意味する何らかの値 isOK := func(m int) bool { if C(m) { return true } return false } ng, ok := -1, maxAgility+1 for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } minAgility := ok num := 0 for i := 0; i < m; i++ { if A[i] >= minAgility { num++ } } fmt.Println(num) } func C(m int) bool { segments := []Trap{} l, r := 0, -1 for i := 0; i < len(L); i++ { t := L[i] if t.d <= m { continue } if r == -1 { l, r = t.l, t.r continue } if r >= t.l-1 { // マージして継続 ChMax(&r, t.r) } else { // マージせず中断して追加 segments = append(segments, Trap{l: l, r: r}) l, r = t.l, t.r } } if r != -1 { segments = append(segments, Trap{l: l, r: r}) } time := 1 + n for _, seg := range segments { time += 2 * (seg.r - seg.l + 1) } return time <= t }
本質部分である「トラップの区間は少なくとも3回通過する必要がある」という部分が整理できずに、コンテスト中は解くことが出来ませんでした。
「区間の通過回数を考える」みたいな部分は、整理する方法としては頻出・典型っぽい雰囲気を感じるので、よく覚えておきたいと思います。
二分探索の判定部分に関しては、区間更新可能な遅延評価ありのセグメント木や、
いもす法を使うことでもOKです（セグ木解法は O(N(logN)^2) なので、ちょっと危なそうですが）。
1次不定方程式とか中国剰余定理ともう少し仲良くなりたい。
Codeforces Round No.603 (Div.2) 参加記録（A〜D解答）
1問目からいきなり難問を置かないでください。。 青が見えていたのにまた遠のいてしまいました。
A. Sweet Problem
問題の概要
赤、緑、青色のキャンディがそれぞれ r, g, b 個ある。
1日に、これらのキャンディから、必ず異なった色のキャンディを1つずつ食べる必要がある。
最大何日食べることができるか計算せよ、という問題。
制約: 1 <= r, g, b <= 10^8
解答
場合分けして考える。
まず、 r, g, b を降順ソートして大きい順に a, b, c とする。
a >= b + c の場合を考える。
この場合は、 b + c が最適である。
この場合には a のキャンディが無限にあると考えても差し支えないので、
常に片方は a のキャンディを選び、もう片方は b, c の残っている方のキャンディを選べばよい。
b, c を選ぶ食べ方は損をするだけとなる。
次に、 a < b + c の場合を考える。
この場合は、すべてのキャンディを食べ尽くす方法と、 1つのキャンディが残る食べる方法のいずれかが存在する。 これは、明らかに最適な食べ方である。
まず、 a - b = diff とし、この差の分だけ a から減らし、 c を一緒に選ぶ。
a - b < c から、これは必ず可能である。
すると、キャンディの分布は (a, b, c) -> (b, b, c-diff) となる。
この後は、
a, bのキャンディでより多く残っている方、およびもう一方をcから選ぶcが尽きているならばa, bをそれぞれ選ぶ
この手順は a, b のキャンディの数が等しい状態からはじまるので、
c%2 == 0 ならば c が尽きたときには a, b が等しくなっているため、すべてのキャンディを食べられる。
c%2 == 1 ならば c が尽きたときには Abs(a-b) = 1 であるため、1つキャンディが残ることになる。
var t int var r, g, b int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { r, g, b = ReadInt3() solve() } } func solve() { A := []int{r, g, b} // 降順ソート sort.Sort(sort.Reverse(sort.IntSlice(A))) sum := A[1] + A[2] if sum <= A[0] { fmt.Println(sum) } else { if A[0] > A[1] { ans := 0 diff := A[0] - A[1] A[0] -= diff ans += diff A[2] -= diff tmp := (A[2] + (2 - 1)) / 2 ans += A[2] + A[0] - tmp fmt.Println(ans) } else { tmp := (A[2] + (2 - 1)) / 2 ans := A[2] + A[0] - tmp fmt.Println(ans) } } }
1問目にしては難しすぎでは？ それにしてもみんなさっと解いていたので驚きました。
B. PIN Codes
問題の概要
各桁が 0, 1, ..., 9 のいずれかであり、4桁のPINコードを持つ銀行カードが n 枚ある。
今、 n 枚全てのカードのPINコードについて、すべての異なるカードのペアでPINコードが異なるようにしたい。
あるカードのPINコードの1桁を任意の数字に変更するときの操作回数を1回とするとき、 最小何回の操作で目的を達成できるか求めよ、という問題。
制約: 2 <= n <= 10
解答
カードに 0-based で番号をふる（入力で与えられる順に自然に採番する）。
あるカードに着目して、それより前の番号のカードすべてと異なるようにすることを考える。
カードの数は少ないので、 O(n) の全探索で前のカードをすべてチェックすれば良い。
もし、前の番号のカードと一致するならば必ず少なくとも1桁は変更する必要がある。
このときに変更する桁は、PINコードの最下位桁とする。
ここで、変更後のPINコード全体が、現在注目中のカードの番号以降のカードのPINコード全体と衝突しないように、
すでに使用されている最下位桁の数値をメモとして保持しておく。
未使用の数字を変更後の最下位桁として採用すれば、いずれのカードとも衝突することはない。
また、重要な制約として、カードは最大でも 10 枚しか存在し得ないため、このような未使用の桁は必ず少なくとも1つは存在する。
これを素直にシミュレーションすれば良い。
var t int var n int var P [][]rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() P = [][]rune{} for i := 0; i < n; i++ { row := ReadRuneSlice() P = append(P, row) } solve() } } var used [10]int func solve() { num := 0 used = [10]int{} for i := 0; i < n; i++ { used[P[i][3]-'0'] = 1 } for i := 0; i < n; i++ { A := P[i] // 直前のものすべてと比較する for j := 0; j < i; j++ { B := P[j] // 等しいものがあればAの最下位桁を未使用のものに変更 if isEqual(A, B) { u := findMinUnused() A[3] = rune(u) + '0' num++ used[u] = 1 break } else { // 前のものと異なるなら何もしなくて良い continue } } } fmt.Println(num) for i := 0; i < n; i++ { fmt.Println(string(P[i])) } } func findMinUnused() int { for i := 0; i < 10; i++ { if used[i] == 0 { return i } } return -1 } func isEqual(a, b []rune) bool { for i := 0; i < 4; i++ { if a[i] != b[i] { return false } } return true }
制約をうまく使えず、ものすごく難しい考え方をして時間を浪費した挙げ句、 実装ミス（最下位桁で使用済みのものを最初にチェックしなかった）によりsystem test落ちという最悪ムーブをしてしまいました。
C. Everyone is a Winner!
問題の概要
レート n をコンテストの参加者 k 人に振り分けるとき、1人あたりの受け取るレートは Floor(n/k) とする。
k を任意の正の整数とするとき、考えられる1人あたりのレートをすべて列挙せよ、という問題。
制約: 1 <= n <= 10^9
解答
素直に考えるのであれば、 k = 1, 2, ..., n+1 として Floor(n/k) を計算すれば、
その列が答えとなる。
しかし、制約的にそれは出来ないため、効率的に行うことを考える。
厳密には異なるが、約数列挙に雰囲気が似ているため、 O(sqrt(n)) ベースの手法に焦点を当てつつ考える。
なんとなく、 k = 1, 2, ..., sqrt(n) まで考えて、 Floor(n/k) = q だけでなく、 k 自体も答えになりそうだ、と仮説を立てる。
この仮説は、以下のようにして正当性が示せる（手書きですみません）。
よって、 k = 1, 2, ..., sqrt(n) の k に対する Floor(n/k) = q は答えになるとともに、 k 自体も答えとなる。
一方で、 k > sqrt(n) の k については、 Floor(n/k) < sqrt(n) となり、これらはすでに答えとして追加されている。
よって、答えは O(sqrt(n)) で列挙できる。
また、出力に際して、答えの要素数も O(sqrt(n)) であるため、配列に詰めた後にソートすればよく、
これがネックとなり計算量は1テストケースあたり O(sqrt(n)*log(n)) となり、間に合う。
var t int var n int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() solve() } } func solve() { memo := make(map[int]int) memo[0] = 1 for k := 1; k*k <= n; k++ { memo[n/k] = 1 memo[k] = 1 } answers := []int{} for k := range memo { answers = append(answers, k) } sort.Sort(sort.IntSlice(answers)) fmt.Println(len(answers)) fmt.Println(PrintIntsLine(answers...)) }
例によって、コンテスト中はここまできっちり考えずに、ｴｲﾔしてしまいました。
D. Secret Passwords
問題の概要
あるシステムのパスワードのリストには、 n 個の小文字のアルファベットのみからなるパスワードが書かれている。
このシステムのパスワードは、ある2つのパスワードを比較したとき、2つのパスワードに共通して存在する文字が1文字でもある場合、
この2つのパスワードは等しいと判定される。
さらに、推移律も存在し、パスワード a, b が等しく b, c が等しい場合、 a, c も等しいと判定される。
この中には、1つだけadminのパスワードが含まれているため、adminのパスワードと等しいものを手に入れるために、 最低限必要なパスワードの数を答えよ、という問題。
解答
個々のパスワードをグラフの頂点と考え、等しければエッジを張る、というふうに考える。
まず、すべてのパスワードをスキャンし、特定のアルファベットが検出されたら、アルファベットのグループに加える。 UnionFindによって、各アルファベットについてグループに存在するものをすべて併合する。 すべてのアルファベットについて併合が終わると、推移律を満たす形で等しいと判定されるパスワードも同じグループに属するようになる。 よって、最後に連結成分の数を出力すれば、それば答えになっている。
公式editorialにあるように、二部グラフ上で考えるのも良さそう
（ a, b, .., z を片方のグループ、パスワードをもう片方のグループとし、パスワードと文字を結んでいき、同じくDFS等で連結成分の数を数える。
こちらのほうが計算量は若干小さい）。
var n int var S [][]rune var memo [30][]int func main() { n = ReadInt() S = make([][]rune, n) for i := 0; i < n; i++ { S[i] = ReadRuneSlice() } for i := 0; i < n; i++ { for _, r := range S[i] { tmp := r - 'a' memo[tmp] = append(memo[tmp], i) } } uf := NewUnionFind(n) for i := 0; i < ALPHABET_NUM; i++ { if len(memo[i]) == 0 { continue } top := memo[i][0] for j := 1; j < len(memo[i]); j++ { uf.Unite(top, memo[i][j]) } } fmt.Println(uf.CcNum()) } // 0-based // uf := NewUnionFind(n) // uf.Root(x) // Get root node of the node x // uf.Unite(x, y) // Unite node x and node y // uf.Same(x, y) // Judge x and y are in the same connected component. // uf.CcSize(x) // Get size of the connected component including node x // uf.CcNum() // Get number of connected components // UnionFind provides disjoint set algorithm. // Node id starts from 0 (0-based setting). type UnionFind struct { parents []int } // NewUnionFind returns a pointer of a new instance of UnionFind. func NewUnionFind(n int) *UnionFind { uf := new(UnionFind) uf.parents = make([]int, n) for i := 0; i < n; i++ { uf.parents[i] = -1 } return uf } // Root method returns root node of an argument node. // Root method is a recursive function. func (uf *UnionFind) Root(x int) int { if uf.parents[x] < 0 { return x } // route compression uf.parents[x] = uf.Root(uf.parents[x]) return uf.parents[x] } // Unite method merges a set including x and a set including y. func (uf *UnionFind) Unite(x, y int) bool { xp := uf.Root(x) yp := uf.Root(y) if xp == yp { return false } // merge: xp -> yp // merge larger set to smaller set if uf.CcSize(xp) > uf.CcSize(yp) { xp, yp = yp, xp } // update set size uf.parents[yp] += uf.parents[xp] // finally, merge uf.parents[xp] = yp return true } // Same method returns whether x is in the set including y or not. func (uf *UnionFind) Same(x, y int) bool { return uf.Root(x) == uf.Root(y) } // CcSize method returns the size of a set including an argument node. func (uf *UnionFind) CcSize(x int) int { return -uf.parents[uf.Root(x)] } // CcNum method returns the number of connected components. // Time complextity is O(n) func (uf *UnionFind) CcNum() int { res := 0 for i := 0; i < len(uf.parents); i++ { if uf.parents[i] < 0 { res++ } } return res }
後日復習したら簡単だった。。
確かコンテスト中は前半でペースを乱されたのも合って、問題文の英語が読めなくて解けなかったという感じでした （そんなセキュリティunkなシステムあるかよ、的な感じで）。
問題文の本質的な部分を読み取ることに集中する訓練が、まだまだ足りないなと感じました。
時間が許すのなら、AtCoder始めたときのようにこどふぉも200問ぐらいまとめて解きたいです。
Codeforces Round No.602 (Div.2) 参加記録（A〜D1解答）
※DのHardバージョンは近いうちに追記すると思います。
A. Math Problem
問題の概要
n 個の数直線上の区間が与えられる。
ここに、ある区間1つを加える。
ただし、この区間は n 個の与えられたすべての区間と、少なくとも1つの共有点（いずれの区間にも含まれる点）を持たなければならない。
加えるべき区間の最小の長さを答えよ、という問題。
解答
区間を並べた時の様子をイメージする。
このとき、最小の右端をとる区間が少なくとも1つ存在する（複数存在する場合もある）。
これを l とする。
また、最大の左端をとる区間が少なくとも1つ存在する（複数存在する場合もある）。
これを r とする。
求めるべき区間は、区間 l, r と共有点を保つ必要があるため、
少なくとも l の右端と r の左端は区間の端点とする必要がある。
このようにして出来上がる区間は、他の n-2 個の区間とも自然と共有点を持つことになるため、
この区間の長さが答えとなる。
区間の長さは、最小の右端を minR 、最大の左端を maxL とすると、
maxL - minR で求まる。
ただし、この値が負になる場合は、最小の右端の値が最大の左端の値を上回っている。
このときは、 [maxL, minR] の任意の値が、 n 個すべての区間と共有点を持つことになるため、答えは 0 とすればよい。
var t int var n int var L, R []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() L, R = make([]int, n), make([]int, n) for i := 0; i < n; i++ { l, r := ReadInt2() L[i], R[i] = l, r } solve() } } func solve() { minR, maxL := 1000000000+5, 0 for i := 0; i < n; i++ { ChMin(&minR, R[i]) ChMax(&maxL, L[i]) } fmt.Println(Max(maxL-minR, 0)) }
B. Box
問題の概要
ある 1, 2, ..., n の n 個の異なる数値の順列 P が、箱を開けるためのコードとなっている。
P はわからないが、情報として prefix maximums Q が与えられている。
※prefix maximumsは、 q[1] = p[1], q[2] = max(p[1], p[2]), q[3] = max(p[1], p[2], p[3]), ... のように定義されるもの。
これを元に、元の順列 P としてありうるものを1つ構築せよ、という問題。
解答
まず、prefix maximumsの定義から、 P[1] == Q[1] であるとわかる。
また、 i >= 2 に関して、 Q[i-1] < Q[i] となる場合は、 P[i] == Q[i] であるとわかる。
これらの自明な情報から、 P に関して確定した部分だけを先に埋めておく。
そして、未確定の部分を前から順番に確定させていくこと、および矛盾について考える。
前から順番に見るときに、未確定部分に選べる数値に関する必要条件は、
Q[i]以下であること[1, n]の数値のうち、未使用のものであること
の2つである。
よって、未使用の [1, n] の数値かつ Q[i] 以下のものを選ぶことになる。
条件に当てはまるものを適当に全探索してしまうと、 O(n^2) になってしまうため、少し工夫が必要となる。
実は、未使用のもののなかから選ぶ際には、小さいものから順番に選んでよい。 これは、以下のように考えることで正当性を示せる。
ある条件に合致する
Pについて、自明パートを終えた後の未確定部分についての部分列を考える。 この部分列は、自明パートで残った未使用の数値の順列となる。 prefix maximumsの定義からQ[j] >= Q[i] (j > i)と単調増加するため、 この部分列については昇順ソートしたものも必ず条件を満たす。
小さいものから割り当てていき、prefix maximumsの条件に抵触してしまった場合は、どうあがいても条件を満たす P は作れないので、 -1 を出力する。
以上の方針に従って実装すれば良い。 自明パートを終えた後の部分は、未使用の要素を小さい順にqueueに放り込むのが簡単だと思う。
var t int var n int var Q []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() Q = ReadIntSlice(n) solve() } } func solve() { memo := make([]int, n+1) for i := 1; i <= n; i++ { memo[i] = 1 } answers := make([]int, n) answers[0] = Q[0] memo[Q[0]] = 0 for i := 1; i < n; i++ { if Q[i-1] < Q[i] { answers[i] = Q[i] memo[Q[i]] = 0 } } // 未使用のものを小さい順にスライスに詰める unused := []int{} for i := 1; i <= n; i++ { if memo[i] == 1 { unused = append(unused, i) } } for i := 0; i < n; i++ { // 未割り当てならば、小さいものを割り当てる、矛盾したらアウト if answers[i] == 0 { // 次の未使用のものを取り出す c := unused[0] unused = unused[1:] if Q[i] >= c { answers[i] = c } else { fmt.Println(-1) return } } } fmt.Println(PrintIntsLine(answers...)) }
途中の貪欲法でよくあるタイプの証明は、コンテスト中にはここまではっきりとは言語化できていなかったので、もう少しこういった証明には慣れたいところです。
また本番では、メモ用配列をそのまま使って未使用のもののポインタを都度移動させるという、しゃくとり法っぽい実装をしてしまいました。 しゃくとり法に慣れていないのが悪いんですが、ちょっと実装に手間取ってしまったので、もう少し立ち止まってからコーディングすべきでした。
C. Messy
問題の概要
偶数の値 n 文字の丸括弧列 S が与えられる。
この丸括弧列の (, ) の数は等しいものとする。
ここで、1回の操作で S の l 文字目から r 文字目までの部分を反転させることができる。
※この反転という操作は、選んだ区間の括弧の種類を逆転させるという意味ではなく（そうすると開き括弧と綴じ括弧の総数が変化してしまう）、
列の順番の反転のことである。
また、 k が同時に与えられるため、 S のprefixのうち k 個のprefixが正しい括弧列となるようにしたい。
操作が最大で n 回可能であるときに、 k 個のprefixが正しい括弧列となるようにするための、操作手順を提示せよ、という問題。
解答
まず、 n 回が操作の上限であることを見逃してしまい、難問のように感じてしまったのが大反省（Outputの m という数値に途中から引っ張られてしまった？）。
一見、制約が強そうに見える反転という操作も、操作回数が十分であれば、どんな列にでも組み替えてしまえる、ということを把握したい （前から順番に注目して、そこに置きたい文字を後ろのほうを探索して見つけ、そこを始点・終点として反転すれば、始点については欲しい文字が手に入る、 これを以降の文字についても同様に行えば、任意のほしい文字列が手に入る）。
さて、目的の括弧列としては ()()()...(((...))) の形とすればよい。
前半部分の構築方法としては、 注目している文字のインデックスの偶奇からあるべき括弧の種類を調べ、 一致しているのであればスルー、不一致であれば後ろの方に存在するあるべき括弧を見つけ、始点と終点で反転すれば良い。
また、後半部分の構築方法としては、
前半分が ( となるように、後半分が ) となるように、同様の反転処理を行えば良い。
前半の ()()...() は、 () が合計 k-1 個作る必要がある。
そのため、前半部分の長さは 2*(k-1) となる。
前半の長さと全体長 n から後半の長さもわかるため、上述の前半分・後半分の処理を分けることができる。
反転処理は、別に関数として切り分けておくと再利用性も高くスッキリする。
var t int var n, k int var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n, k = ReadInt2() S = ReadRuneSlice() solve() } } func solve() { answers := [][]int{} for i := 0; i < 2*(k-1); i++ { if i%2 == 0 && S[i] == ')' { answers = append(answers, sub(i, '(')) } else if i%2 == 1 && S[i] == '(' { answers = append(answers, sub(i, ')')) } } tmp := (n - 2*(k-1)) / 2 for i := 2 * (k - 1); i < 2*(k-1)+tmp; i++ { if S[i] == ')' { answers = append(answers, sub(i, '(')) } } fmt.Println(len(answers)) for i := 0; i < len(answers); i++ { fmt.Println(answers[i][0]+1, answers[i][1]+1) } } // sからスタートしてrを発見したところで反転する // さらに始点と終点をスライスで返す func sub(s int, r rune) []int { t := s + 1 for i := s + 1; i < n; i++ { if S[i] == r { t = i break } } res := []int{s, t} // [s, t]を反転 rev := Reverse(S[s : t+1]) for i := 0; i < len(rev); i++ { S[s+i] = rev[i] } return res } func Reverse(A []rune) []rune { res := []rune{} n := len(A) for i := n - 1; i >= 0; i-- { res = append(res, A[i]) } return res }
Reverse みたいなのは地味にスニペットに用意しておくと、多少は快適です。
D1. Optimal Subsequences (Easy Version)
問題の概要
長さが n のある数列 A が与えられる。
この数列 A の長さ k の部分列を考える。
以下の条件を満たすとき、この部分列はoptimalであるとする。
- 考えられる任意の長さ
kの部分列のうち、部分列を構成する要素の和が最も大きい。 - 1を満たす部分列の中で、辞書順最小である。
m 個のリクエストが与えられるので、それらすべてに答える。
リクエスト j は (k[j], pos[j]) で与えられる。
これに対して、長さ k[j] のoptimalな部分列に対し、1-basedで位置 pos[j] の数値で答える。
Easy Versionの制約
1 <= n, m <= 100
解答
すべての k (1 <= k <= 100) について、optimalな部分列を前計算しておくことを考える。
制約が小さく制限時間も3secと長いので、よっぽど変なことをしない限りTLEしないだろうということで、 素直に考えていく。
まず、1つ目の条件を満たす必要があることを考えると、 A を降順ソートしたとき、
先頭 k 個の要素を部分列が含む必要がある。
optimalな部分列が含むべき要素がわかったので、これが辞書順最小となるような部分列を取得することを考える。
降順ソート後の A の先頭 k 個の配列を topk とする。
topk の構成要素と一致する辞書順最小の部分列を得るには、 topk の構成要素をできるだけ元の配列 A の前の方から貪欲に選択すれば良い。
以下のコードは、ソートや愚直な全探索を駆使して、ある k についてのoptimalな部分列を計算している。
subsub 関数が topk から辞書順最小の部分を求める関数で、ここが O(kn) となり一番ネックとなる部分である。
k は [1, n] 全てについて求めているため、全体で O(n^3) となる。
var n int var A []int var m int var k, pos int var answers [105][]int var sA []int func main() { n = ReadInt() A = ReadIntSlice(n) m = ReadInt() sA = make([]int, n) for i := 0; i < n; i++ { sA[i] = A[i] } sort.Sort(sort.Reverse(sort.IntSlice(sA))) sub() for i := 0; i < m; i++ { k, pos = ReadInt2() pos-- fmt.Println(answers[k][pos]) } } func sub() { for k := 1; k <= n; k++ { answers[k] = make([]int, k) topk := sA[:k] tmp := subsub(k, topk) sort.Sort(sort.IntSlice(tmp)) for i := 0; i < k; i++ { answers[k][i] = A[tmp[i]] } } } // Aのidxの配列を返す func subsub(k int, topk []int) []int { res := make([]int, k) memo := make([]bool, n) for i := 0; i < k; i++ { // Aと照合させる for j := 0; j < n; j++ { if topk[i] == A[j] && !memo[j] { res[i] = j memo[j] = true break } } } return res }
最近誤読というより重要な制約とかの見落としが多いので、強めに意識しないといけない。
Codeforces Round No.601 (Div.2) 参加記録（A〜C解答）
素の状態でB問題の嘘解法に疑問を持てず、もやもや。
A. Changing Volume
問題の概要
テレビのボリューム a を b に変化させたい。
-5, -2, -1, +1, +2, +5 の6つのボタンがあるので、できるだけ少ない回数でボリュームを合わせる場合、
最小で何回操作が必要か答える問題。
解答
まず、操作は「ボリュームを上げ続ける」か「ボリュームを下げ続ける」のいずれかで良い。
（+1 -> -1 は意味がなく +2 -> -1 は +1 一回で代替可能で、 +5 -> -2, +5 -> -1 もそれぞれ +1 -> +2, +2 -> +2 の操作で代替可能なため。）
この場合、できるだけ1回の操作で目的の b により近づけるボタンを選択すれば良い。
また、用意されているボタンは対称性があるため、 diff = Abs(b - a) という差の絶対値を考える。
そうすると、 diff に対して超過しないようにボタンの絶対値で引ける回数を調べればよく、
これはそれぞれの商とあまりを考えることで求められる。
var t int var a, b int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { a, b = ReadInt2() solve() } } func solve() { diff := AbsInt(b - a) ans := 0 ans += diff / 5 diff %= 5 ans += diff / 2 diff %= 2 ans += diff fmt.Println(ans) }
B. Fridge Lockers
問題の概要
n 人のが持つ n 個の冷蔵庫同士が鎖で繋がれており、さらに両端に鍵が取り付けられている。
自身の冷蔵庫に繋がれた鎖は自由に外すことができる（両端が外せるので繋がれた相手の冷蔵庫の鎖も外せる）。
すべてのメンバーについて、「自分が外せる鎖をすべて外したときに、他のすべての冷蔵庫に何らかの鎖が取り付けられている」 という状態が成り立つときに、privateであると呼ぶ。
各冷蔵庫にはコストが振られており、冷蔵庫 i, j 同士を鎖で結びつける場合、 A[i] + A[j] のコストがかかるとする。
同じ冷蔵庫のペアに、鎖を何本重ねてつなげても良い。
m 本の鎖が与えられたとき、privateな状態にするために必要な最小のコストを求め、privateに出来ない場合は -1 を出力する問題。
解答
ある冷蔵庫に着目したときに、その冷蔵庫につながっている鎖をすべて外して、なお他のすべての冷蔵庫に鎖がつながっていなければならないとすると、 すべての冷蔵庫は「少なくとも自分以外の異なる2つの冷蔵庫と鎖で繋がれていなければならない」と主張できる。 （もし、自分以外の1つの冷蔵庫としかつながっていない場合、その他方の冷蔵庫に鎖を外されたら、自分につながる鎖はなくなってしまう。）
このような状態を満たすためには、 1 -> 2 -> ... -> n -> 1 とループさせれば自然と構築できる。
このとき必要になる鎖は n 本であるため、最低 n 本の鎖があればprivateな状態は作れる。
ただし、 n = 2 の場合は、自分以外と繋げられる冷蔵庫の数は1個のみなので、この場合は鎖が何本あってもprivateには出来ない。
また、 n < m のときは、できるだけつなげるコストが小さい冷蔵庫同士を繰り返し鎖で結べばよく、
それは A についてソートして前2つを選べば良い(※)。
。。と思いきや、（※）部分は嘘解法。
今回はコンテスト中に m > n の制約が取っ払われたため、このようなケースはジャッジされなくなった。
var t int var n, m int var A []int type Edge struct { key int nodeId, cost int } type EdgeList []*Edge type byKey struct { EdgeList } func (l EdgeList) Len() int { return len(l) } func (l EdgeList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l byKey) Less(i, j int) bool { return l.EdgeList[i].key < l.EdgeList[j].key } // how to use // L := make(EdgeList, 0, 200000+5) // L = append(L, &Edge{key: intValue}) // sort.Stable(byKey{ L }) // Stable ASC // sort.Stable(sort.Reverse(byKey{ L })) // Stable DESC func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n, m = ReadInt2() A = ReadIntSlice(n) solve() } } func solve() { if m < n { fmt.Println(-1) return } if n == 2 { fmt.Println(-1) return } sumA := Sum(A...) cost := 2 * sumA L := make(EdgeList, 0) for i := 0; i < n; i++ { L = append(L, &Edge{key: A[i], nodeId: i + 1, cost: A[i]}) } sort.Stable(byKey{L}) mm := m - n cost += mm * (L[0].cost + L[1].cost) answers := [][]int{} for i := 1; i <= n; i++ { if i == n { answers = append(answers, []int{i, 1}) } else { answers = append(answers, []int{i, i + 1}) } } for i := 0; i < mm; i++ { // この部分は嘘解法に含まれるが、コンテスト後半のテストケースでは実行されることはない answers = append(answers, []int{L[0].nodeId, L[1].nodeId}) } fmt.Println(cost) for i := 0; i < m; i++ { fmt.Printf("%d %d\n", answers[i][0], answers[i][1]) } }
嘘解法の反例
ここで m > n のケースが議論されている。
嘘解法をざっくりと否定するならば以下のような感じでしょうか。
各冷蔵庫について、自身がループに組み込まれさえすれば良い。 鎖が
n本しかない場合は1つのループですべてをつなげればよいが、 たくさんある場合には、できるだけコストの小さい冷蔵庫とループが組めるようにするほうが良い。
たしかにこれは、なまじ慎重で賢明な人ほど考え込んで損をしている、というケースがかなりありそう。 激遅3完でも比較的マシなパフォーマンスが出たのはこの辺も影響していたのかも。。？
これに気づかずに突っ走ってしまった自分も大分問題な気がするけど、 Div2のBだからあまり考えなかったし、フルフィードバックならWAの後もう少し考え込むだろう、 ということにして、とりあえずは深入りしないようにします。
C. League of Leesins
問題の概要
1, 2, ..., n で構成される順列 P が与えられる。
この数列を前から順番に連続するtripleに分割し、 n-2 個のtripleからなる配列を生成する。
このtripleの配列中でtripleの順番をデタラメに入れ替え、
さらに、個々のtripleの中で数字の順番を入れ替える。
今、 n-2 個のtripleが与えられるので、元の順列 P を復元せよ、という問題。
解答
とりあえず、元の順列からtripleが切り分けられる様子を図示すると、 ある数字の出現頻度が大きなヒントになりそうなことがすぐに分かる。
ほとんど（ n-4 個）の数字の出現頻度は3回となり、1回、2回がそれぞれ2つずつ、という分布になる。
例えば、出現頻度が1のある数字を考えたとき、その数字を含むtripleは唯一で、
さらにその中に出現頻度が2回である数字の片方が含まれる。
このtripleを左から並べ始めるとすると、次に並べるべきは、1つ目のtripleに含まれる頻度2回の数字および頻度1回の数字を含む、 別のtripleであると決定できる。 使った数字の頻度を減らして考えると、以降も同様に考えられるため、左から順番に元の数列を復元していくことができる。
（難易度はぜんぜん違うけど、JSCのC問題のように、 一見複雑だけど実は左から順番に再帰的に決まっていく、というのはよく見る。）
続いて具体的な実装方法について考える。
上述の考察を踏まえると、1つ前に選んだtripleが左から (a, b, c) とすると、
次に選択すべきtripleは (b, c, x) のような形、すなわち「 b, c を含み、かつ a を含まないtriple」となる。
目的のtripleを探すのにすべてのtripleを探すわけには行かないので、一工夫が必要。
とはいえ、それほど面倒なことは考えずに、「ある数字 b を含む高々3つのtriple」の中からすべて調べれば良い。
これは、バケット法の要領でtripleを管理しておけば、ある数字 b のバケットの中を全探索する形で探索できる。
肝心の数列の復元部分については、目的のtripleを見つけるたびに x に該当する数字を都度appendしていくようにすればよい。
ここまで整理してもあまりいい実装にはならなかったので、 適宜関数を切り分けてバグらせないように注意する。
var n int var T [][]int var book [100000 + 5][][]int // バケット func main() { n = ReadInt() for i := 0; i < n-2; i++ { T = append(T, ReadIntSlice(3)) } // 頻度をカウント memo := make([]int, n+1) for i := 0; i < n-2; i++ { for j := 0; j < 3; j++ { q := T[i][j] memo[q]++ } } ones := []int{} twos := []int{} for i := 1; i < n+1; i++ { if memo[i] == 1 { ones = append(ones, i) } else if memo[i] == 2 { twos = append(twos, i) } } // バケットでtripleを管理 for i := 0; i < n-2; i++ { a, b, c := T[i][0], T[i][1], T[i][2] book[a] = append(book[a], []int{a, b, c}) book[b] = append(book[b], []int{a, b, c}) book[c] = append(book[c], []int{a, b, c}) } // 先頭のトリプルを見つけ、元の配列の3番目までを復元する targetInt := ones[0] firstTriple := book[targetInt][0] answers := make([]int, 3) for i := 0; i < 3; i++ { tmp := firstTriple[i] if memo[tmp] == 1 { answers[0] = tmp } else if memo[tmp] == 2 { answers[1] = tmp } else { answers[2] = tmp } } // 完全に復元されるまでループ for len(answers) < n { l := len(answers) ex, inc1, inc2 := answers[l-3], answers[l-2], answers[l-1] // 高々3個のtripleから該当するものを見つける for _, tri := range book[inc2] { if sub(tri, ex, inc1, inc2) { // inc1, inc2以外の値をanswersに追加する answers = append(answers, subsubsub(tri, inc1, inc2)) break } } } fmt.Println(PrintIntsLine(answers...)) } // triが目的のものだったらtrue func sub(tri []int, ex, inc1, inc2 int) bool { // exを含んだらfalse if subsub(tri, ex) { return false } // inc1を含まないならfalse if !subsub(tri, inc1) { return false } // inc2を含まないならfalse if !subsub(tri, inc2) { return false } return true } // triがtargetを含んだらtrue func subsub(tri []int, target int) bool { for _, v := range tri { if v == target { return true } } return false } // inc1, inc2以外の値を返す func subsubsub(tri []int, inc1, inc2 int) int { for _, v := range tri { if v != inc1 && v != inc2 { return v } } return -1 }
所望のtripleの検索方法の部分で何故か難しく考えてしまい、時間を浪費してしまったのが大反省。 しかしながら、競技でこういった実装・発想をした経験がなかったので、1つ1つ引き出しを増やしていくしか無いのかも。
未だにグローバルに変数を置いたり、命名を適当にやってしまうことに抵抗があります。
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元の場合だけでも覚えておくと、思考のツールとして便利そうです。
整数問題が得意になる気配が感じられません。
