Codeforces Round No.605 (Div.3) 参加記録 (A〜E解答)
- A. Three Friends
- B. Snow Walking Robot
- C. Yet Another Broken Keyboard
- D. Remove One Element
- E. Nearest Opposite Parity
A. Three Friends
問題の概要
数直線上に3人がそれぞれ座標 a, b, c にいる。
それぞれは、自身の座標を +1, -1, 0 変位させることができる。
ここで、総合距離を |a-b| + |a-c| + |b-c| とする。
ありうる総合距離の最小値を求めよ、という問題。
解答
まず、一般性を失わずに a <= b <= c となるようにする。
この状態では、総合距離は (b-a) + (c-b) + (c-a) = 2*(c-a) と表すことができる。
よって、移動後もこの関係が保たれているのであれば b はないものとして考えることができる。
よって、 a, c の位置関係に注意しながら、それぞれを右に動かすか、左に動かすか判断すれば良い。
オーバーフローには注意する。
var q int var a, b, c int64 func main() { q = ReadInt() for tc := 0; tc < q; tc++ { a, b, c = ReadInt64_3() solve() } } func solve() { A := LongInt{a, b, c} sort.Sort(A) aa, _, cc := A[0], A[1], A[2] if aa < cc { aa++ } if aa < cc { cc-- } ans := 2 * (cc - aa) fmt.Println(ans) } // AbsInt is integer version of math.Abs func AbsInt(a int64) int64 { if a < 0 { return -a } return a } type LongInt []int64 func (a LongInt) Len() int { return len(a) } func (a LongInt) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a LongInt) Less(i, j int) bool { return a[i] < a[j] }
。。こんな考え込まなくても、素直に全探索するべきですね（27通りしか無いので）。
通ってみればなんてことはないですが、こういった算数はpretestではびびりながら出しているので、 提出に14分かかっています。
今回のコンテストで一番反省すべき点だと思います。
B. Snow Walking Robot
問題の概要
L, R, U, D の命令を与えると、それぞれ左、右、上、下に1マス進むロボットがある。
ただし、このロボットは一度通ったマスを通ると壊れてしまう。
ロボットを壊さずに、自分の家から出発させて、命令の最後には自分の家に戻ってくるようにしたい。
今、命令列が与えられるので、この列のいくつかの命令を消去することで、上記の操作を成立させたい。
最大で何個の命令を残すことができるか、またその時の命令列を出力せよ、という問題。
解答
基本的には、上下と左右に分けて考えて、例えば UU..URR..RDD..DLL..L のように
長方形を描くように移動させることを考えればよい。
このように移動させるためには、上への移動回数と下への移動回数が釣り合う必要があるため、 それぞれのカウントの最小値を採用すれば良い。 左右に関しても一緒である。
ただし、上下の移動ができない場合、あるいは左右の移動ができない場合は、 長方形ではなく線分となってしまい、同じ道を通ってしまうことをケアする必要がある。
この場合はコーナーケースとして別に扱う。
var q int var S []rune func main() { q = ReadInt() for tc := 0; tc < q; tc++ { S = ReadRuneSlice() solve() } } func solve() { memo := make(map[rune]int) memo['L'], memo['R'], memo['U'], memo['D'] = 0, 0, 0, 0 for _, r := range S { memo[r]++ } lrTime := Min(memo['R'], memo['L']) udTime := Min(memo['U'], memo['D']) if lrTime == 0 && udTime == 0 { fmt.Println(0) fmt.Println("") return } if lrTime == 0 { // UDを1回ずつ fmt.Println(2) fmt.Println("UD") return } if udTime == 0 { // LRを1回ずつ fmt.Println(2) fmt.Println("LR") return } fmt.Println(lrTime*2 + udTime*2) answers := []rune{} for i := 0; i < lrTime; i++ { answers = append(answers, 'R') } for i := 0; i < udTime; i++ { answers = append(answers, 'D') } for i := 0; i < lrTime; i++ { answers = append(answers, 'L') } for i := 0; i < udTime; i++ { answers = append(answers, 'U') } fmt.Println(string(answers)) }
C. Yet Another Broken Keyboard
問題の概要
ある長さが n の文字列が与えられたため、タイピングの練習のため、この文字列のすべての連続部分文字列をタイプしようとした。
しかし、いくつかのキーが壊れているため、いくつかの連続部分文字列は不完全な状態で出力されてしまった。
n*(n+1)/2 個の全連続部分文字列のうち、正しくタイピングできたものはいくつか求めよ、という問題。
解答
まず、与えられた文字列に対して、壊れているキーのインデックスに目印をつける。
左から文字列をスキャンしたとき、今見ている文字を右端とする部分文字列でタイピングできるものの数は、 以下の図に示すように、タイプ出来ない文字から数えた文字の長さ分だけである。
タイプ不可の文字に出会うたびにカウンターをリセットすることで、これらの数値はすべて記録できるため、 最後に総和を計算すれば良い。
オーバーフローには注意する。
var n, k int var S []rune var Avail []rune func main() { n, k = ReadInt2() S = ReadRuneSlice() for i := 0; i < k; i++ { tmp := ReadRuneSlice() Avail = append(Avail, tmp[0]) } memo := make([]int, n) for i := 0; i < n; i++ { if !isAvail(S[i]) { memo[i] = -1 } } cur := int64(0) sums := make([]int64, n) for i := 0; i < n; i++ { if memo[i] == -1 { // アウトなのでリセット cur = 0 } else { // 継続 cur++ } sums[i] = cur } ans := int64(0) for i := 0; i < n; i++ { ans += sums[i] } fmt.Println(ans) } func isAvail(r rune) bool { for i := 0; i < len(Avail); i++ { if Avail[i] == r { return true } } return false }
。。こんなにめんどくさいことしなくても、タイプ不可能のものとそうでないものを2値化して、 ランレングス圧縮したものを使ったほうが簡単でした。
そこそこ時間をロスしてしまったので、これも結構な失敗でした。
D. Remove One Element
問題の概要
長さ n の整数配列 A が与えられる。
この整数配列の好きな要素を1個削除するか、もしくはそのままでも良い。
この状態の配列に対し、狭義単調増加である連続部分列を考える。
ありうる最も長い連続部分列の長さを求めよ、という問題。
解答
配列 A の要素に関して、消す要素を全探索することを考える。
すなわち、ある要素を削除したとき、影響を受けるのはその前後だけであり、
その際に作られる連続部分列がより大きいものとなるのなら更新していく、ということを考える。
まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。
更に、数列間の階差を計算しておく。
以下の図に示すように、ある要素を削除したとき、新たに比較すべき階差は元の階差の和で表される。
よって、階差の和が正となる場合にのみ、削除される要素の前後の連続部分列の長さを足し合わせる形で、新たに出来上がる連続部分列の長さを計算する。
var n int var A []int func main() { n = ReadInt() A = ReadIntSlice(n) // 階差 diff := []int{} // len(diff) == n-1 for i := 1; i < n; i++ { diff = append(diff, A[i]-A[i-1]) } // 自身が含まれる増加列の長さ L := make([]int, n) for i := 0; i < n; i++ { if i == 0 { L[i] = 1 continue } if A[i] > A[i-1] { L[i] = L[i-1] + 1 } else { L[i] = 1 } } cur, l := 0, 0 for i := n - 1; i >= 0; i-- { if cur == 0 { cur, l = L[i], L[i] } L[i] = l cur-- } ans := 0 // 何もしない場合の最大値で初期化 for i := 0; i < n; i++ { ChMax(&ans, L[i]) } // すべて試す for i := 1; i < len(diff); i++ { if diff[i] > 0 && diff[i-1] > 0 { continue } if diff[i] <= 0 && diff[i-1] <= 0 { continue } if diff[i]+diff[i-1] > 0 { // この場合のみ意味がある ChMax(&ans, L[i-1]+L[i+1]-1) } } fmt.Println(ans) } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false }
本番では階差数列のみをうまく扱って答えを出そうとしたらぐちゃぐちゃになってしまい、 結果バグったコードによりpretestで撃沈してしまいました。 また、そうでなくとも、階差のインデックスと元の配列のインデックスの調整で身長になる必要があり、あまりいい実装が出来ませんでした（というかよくよく見るといろいろな部分が省ける）。
まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。
この部分も結構面倒なのですが、「Union Findを使って増加列を同じグループとし、 それぞれが属するグループのサイズを見れば良い」という方法を くるさんにご教示いただきました。
あまりUnion Findを活用できていなかったと思うので、これからはもう少し視野を広げてみようと思います （というよりは問題にたくさん触れるべきなのですが）。
DPによる別解
こちらも同じくくるさんの解法を参考にしました。
dp1[i]: i番目の数値が属する連続部分列に関して、何個目かを記録する
dp2[i]: i番目以前の数値を1つ削除したときの、i番目の数値が属する連続部分列に関して、何個目かの最大値を記録する
以下のコードに示すように、 dp2 -> dp1 のような遷移がないため、正しく動作します。
var n int var A []int var dp1, dp2 [200000 + 5]int func main() { n = ReadInt() A = ReadIntSlice(n) for i := 0; i < n; i++ { dp1[i] = 1 } for i := 0; i < n; i++ { if i-1 >= 0 && A[i] > A[i-1] { ChMax(&dp1[i], dp1[i-1]+1) ChMax(&dp2[i], dp2[i-1]+1) } if i-2 >= 0 && A[i] > A[i-2] { ChMax(&dp2[i], dp1[i-2]+1) } } ans := 0 for i := 0; i < n; i++ { ChMax(&ans, dp1[i]) ChMax(&ans, dp2[i]) } fmt.Println(ans) }
なんと呼ぶべきかはわからないですが、 こういった片方向の遷移を行うものは過去のABCあたりでも解いたことがあるような気がします。
いずれにせよ、頻出パターンの1つではあると思うので、定着させていきたいところです。
E. Nearest Opposite Parity
問題の概要
長さ n の整数配列 A が与えられる。
ある位置 i からは、1回の移動で i - A[i] もしくは i + A[i] へと移動できる。
ある開始位置から移動をはじめて、開始位置の A[i] とは偶奇が反対のところへたどり着くためには、
最小で何回の移動が必要か、すべての位置に関して答えよ。
また、到達不可能であるならば -1 を出力せよ、という問題。
解答
公式Editorialをなぞったものです。
まず、ある位置 i から j まで移動できるとき、これを逆向きに考えて j -> i とエッジを張ります。
このようにして出来上がるグラフの辺の数は、最大でも 2*n であるため、全探索が間に合います。
そこで、偶数の要素をスタート地点とした多点BFSを考え、到達位置へのステップ数を記録します。 探索が完了したら、奇数の要素のステップ数を確認すれば、それが答えとなっています。
今度はこれを偶数と奇数を入れ替えて行うことで、すべての位置について答えを求めることが出来ます。
var n int var A []int var G [200000 + 5][]int var answers []int func main() { n = ReadInt() A = ReadIntSlice(n) for i := 0; i < n; i++ { lid, rid := i-A[i], i+A[i] if lid >= 0 { G[lid] = append(G[lid], i) } if rid < n { G[rid] = append(G[rid], i) } } oddIdxs, evenIdxs := []int{}, []int{} for i := 0; i < n; i++ { if A[i]%2 == 0 { evenIdxs = append(evenIdxs, i) } else { oddIdxs = append(oddIdxs, i) } } answers = make([]int, n) for i := 0; i < n; i++ { answers[i] = -1 } bfs(oddIdxs, evenIdxs) bfs(evenIdxs, oddIdxs) fmt.Println(PrintIntsLine(answers...)) } func bfs(starts, ends []int) { dist := make([]int, n) for i := 0; i < n; i++ { dist[i] = INF_BIT30 } queue := []int{} for _, sidx := range starts { dist[sidx] = 0 queue = append(queue, sidx) } for len(queue) > 0 { cid := queue[0] queue = queue[1:] for _, nid := range G[cid] { if dist[nid] == INF_BIT30 { dist[nid] = dist[cid] + 1 queue = append(queue, nid) } } } for _, eidx := range ends { if dist[eidx] != INF_BIT30 { answers[eidx] = dist[eidx] } } }
ICPC形式？のため、Dが解けずにコンテスト中は見ることすらできませんでしたが、 復習の際にDFSから考え始めたので論外でした。
Dijkstraしかり、「最短経路」が効かれているのだからBFSを検討しないと土俵にも立てていませんでした。
また、別に逆向きのグラフじゃなくても順方向のグラフで同じことをすればいけるのでは？とか考えましたが、 探索済みの箇所で衝突してしまうため無理でした。
確かAtCoderのうほょじごという問題が、 想定解法がこれと似たようなコンセプトだったような気がします（違ったらすみません）。 「逆から考える」っていう典型と見るべきなのでしょうか？
そろそろ過去に解けなかった問題もとき直したいところなのですが、時間が。。
ランレングス符号化で易問をさらに楽にする（緑ぐらいまでの人向け）
TL;DR
- AtCoder緑か自分（1300）程度までの人向けです。
- ランレングス符号化を使いやすい形で用意しておくと、意外と高頻度で便利に使えるよという話。
- 10月以降のコンテストの問題で役立ったものを、活用事例として紹介します。
きっかけ
AGC039のA問題が60分ぐらい使ってもWAが取れずに、Bへ向かうも解けず、初めての太陽をやらかしてしまいました。
それなりにレートも落ちてしまっただけに、復習して確実に経験値にしようと、A問題から復習に力を入れました。
人によって好みはわかれるかもしれませんが、このA問題がランレングス符号化を行うと見通しがよくなるもので、 このタイミングでようやくスニペットをこしらえることになりました （アルゴリズムの存在は知っていても、必要性を感じなかったので用意していなかった）。
すると、以降のコンテストでやたらと使用頻度が高くなり、 無駄に用意しているスニペット集の中でもかなり目立つものになってきました。
なので、自分程度までの人だったら同じように利用できるのではないかと思い、本記事を書くことにしました。
アルゴリズム
色々とバリエーションはありますが、 本記事ではwikipediaの該当ページで 一番最初に説明されている、最も基本的なものを指しています。
AAAAABBBBBBBBBAAA という文字列を 5A9B3A というように符号化するもので、
「連長圧縮」という日本語の通り直感的なものです。
AtCoderユーザは皆さん優秀なので、アルゴリズムの名前は知らなくても自然と使ってた、という人も多そうです。
メインの焦点は文字列だと思いますが、競技プログラミングでよく登場する整数配列についても、 しばしば便利に使えます。
実装例
言語はGolangですが、アルゴリズム自体はシンプルなので、他言語を使っている方も読む分にはほとんど問題ないかと思います。
ポイントとしては、 「文字とカウントを分離して別々の配列として出力する」 ことぐらいです （もっと便利なシグニチャがあったら教えていただきたいです）。
RunLengthDecoding(RunLengthEncoding(S)) == S となるように復号関数も一応用意していますが、
特に使ったことはありません。
// 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 }
Golangではジェネリクスがないので、自分の場合、この手の問題ではスニペットで必要な型をその時々に指定しています
（ interface{} だといちいち型アサーションするのが面倒）。
実際のところ、Golangも全然詳しくないので、もっといい方法があれば是非教えていただきたいです。
活用事例
ここからは、実際に活用できた問題と具体的な活用方法について書いていきます。
ABC143 C. Slimes
まさにランレングス符号化そのものです。
スニペット呼び出して、関数に放り込んで、出力のいずれかの配列の長さを提示して終わりです。
他の解き方でも簡単に解けるとは思いますが、バグの心配もなく貼るだけで終わるならばそれが一番だと思います。
var n int var S []rune func main() { n = ReadInt() S = ReadRuneSlice() comp, _ := RunLengthEncoding(S) fmt.Println(len(comp)) }
Educational Codeforces Round 75 A. Broken Keyboard
問題を要約すると、おおよそ以下のような感じです。
26文字のキーボードについていくつかの壊れたキーがあるので、故障していないキーだけを列挙する問題。
壊れたキーを叩くと、その文字について確実に2回タイプされてしまう、というのをヒントに解く。
「確実に故障していない」と断定できるのは、連続で奇数回タイプされた文字だけなので、 それを見つけるために文字列をfor文でスキャンしてカウントを取る、という方法でも簡単に解けます。
しかしながら、フルフィードバックではないCodeforcesではとにかくバグの出る余地をなくしたいので、 実績のあるスニペットを持ち出せると多少は安心できます。
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)) } }
Codefources Round 604 A. Beautiful String
問題を要約すると、おおよそ以下のような感じです。
a, b, c, ?の4文字からなる文字列が与えられる。
?の部分をa, b, cのいずれかに置き換えて、同じ文字が連続しないように文字列を構築せよ、という問題。
この問題も、やること自体は非常に簡単かつすぐに思いつくもので、 「文字列をスキャンして前後の文字と違うものを素直に選び続ければ良い」というだけです。
「最初から2つ以上連続する a, b, c が存在するとアウト」という部分を先に処理しておくと、
後半の構築に集中することが出来、バグらせる確率が多少減らせます。
文字列をスキャンして前後を見る、としても良いんですが、 先頭と末尾は処理が変わったり、、とか考えるのも面倒で、ランレングス符号化したものを見ると簡単です。 （結局構築時にそれは考える必要があるんですが）。
var t int var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { S = ReadRuneSlice() solve() } } func solve() { // 1文字のケース if len(S) == 1 && S[0] != '?' { fmt.Println(string(S)) return } if len(S) == 1 && S[0] == '?' { fmt.Println("a") return } // 以降は2文字以上 // 可能かどうか pressed, nums := RunLengthEncoding(S) for i := 0; i < len(pressed); i++ { r := pressed[i] cnt := nums[i] if r != '?' && cnt > 1 { fmt.Println(-1) return } } // 後は素直に構築するだけ }
Codefources Round 600 Div.2 A. Single Push
問題を要約すると、おおよそ以下のような感じです。
与えられた配列
Aに対して、1度だけ任意の連続区間に対してある正の整数加算することが許される。 操作は行わなくても良い。これによって、もう一方の与えられた配列
Bに等しくすることができるか？
これを達成するためには、
すべての要素に関して diff[i] = B[i] - A[i] を計算しておき、
この diff 配列が [0, ..., 0, k, ..., k, 0, ..., 0], k >= 0 のような形になっていればよい、
というのは割と簡単にわかると思います。
しかしながら、これをバグらせずに判定するのは、 いくつかの場合分けが必要だったり、それなりに神経を使うような気がします。
そこで、 整数配列に対するランレングス符号化 を考えます。
圧縮後の配列に対して、
- 負の整数が検出されたらアウト
- 正の整数が2つ以上検出されたらアウト
- そうでないならセーフ
のように判定すればよい、というふうな実装方針が立ちます。
前後の 0 埋めがないケースの場合分けなどが不要となり、それなりに実装の負荷は小さくなっているのではないでしょうか。
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") } }
Codeforces Round 604 C. Beautiful Regional Contest
問題を要約すると、おおよそ以下のような感じです。
あるプログラミングコンテストにおいて、
n人の解答問題数が配列で与えられるので、 それぞれの人に金・銀・銅メダルを授与することを考える。以下の条件を満たすように、それぞれのメダルの数を求める問題。
- それぞれのメダルの数は正の整数である。
- 金メダルの数は、銀・銅メダルよりも大きい必要がある。ただし、銀メダルと銅メダルの数量関係は不問である。
- 金メダルを受賞する参加者は、銀メダルを受賞する参加者よりも多くの問題を解いていなければならない。
- 銀メダルを...、銅メダルを...。
- 銅メダルを...、メダルを受賞していない参加者よりも多くの問題を解いていなければならない。
- 3つのメダルの合計個数は、
Floor(n/2)以下である必要がある。
考えるポイントが多いだけに、ここでも前処理として整数配列に対するランレングス符号化を行っておくと、 問題の本質部分に集中できて楽です。
条件3, 4, 5を踏まえると、メダルの種類の境界において、 問題の正解数に1以上の差がある必要がある、すなわち、正解数が異なっている必要があるとわかります。
なので、各メダルの枚数を加算するにあたっては、ランレングス符号化を行った後の長さが使えます。
var t int var n int var P []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() P = ReadIntSlice(n) solve() } } func solve() { g, s, b := 0, 0, 0 limit := n / 2 _, counts := RunLengthEncoding(P) // 圧縮後に最低長さ3は必要 if len(counts) < 3 { fmt.Println(0, 0, 0) return } // gを決める g += counts[0] // sを決める、伸ばす idx := 1 for idx < len(counts) { // gを超えたらbreak if s > g { break } s += counts[idx] idx++ } // bを決める、伸ばす for idx < len(counts) { // gを超えたらbreak if b > g { break } b += counts[idx] idx++ } if g == 0 || s == 0 || b == 0 { fmt.Println(0, 0, 0) return } if s <= g || b <= g { fmt.Println(0, 0, 0) return } sum := g + s + b if sum > limit { fmt.Println(0, 0, 0) return } // bをできるだけ伸ばす for idx < len(counts) { // 足した結果がlimitを超えるなら足さないでbreak if sum+counts[idx] > limit { break } b += counts[idx] sum += counts[idx] idx++ } fmt.Println(g, s, b) }
まとめ
ランレングス圧縮を用意しておくと、簡単な問題がさらに楽になったり、 多かれ少なかれバグの心配が減ったりと、結構便利だよ、ということを伝えるための内容でした。
正直見返してみると、若干過剰適合というか、「金槌を手にして多くの問題が釘に見えている」という状態に落ちているような気もします。
とはいえ、それで損した感じはなく、少なくとも毒にはなっていないだろうということで、今回このように紹介してみました。
また、問題例のほとんどがCodeforcesである通り、最近こどふぉにも積極的に参加していますので、 近いレベル帯のフレンド（ライバル）募集中です （知っている人がみんな紫以上でDiv1に行っちゃったり、Div2一緒に出ても大差つけられてしまって悲しい）。
Codeforces Round No.604 (Div.2) 参加記録（A〜D解答）
今回もランレングス符号化が活躍してくれた。
A. Beautiful String
問題の概要
a, b, c, ? の4文字からなる文字列が与えられる。
? の部分を a, b, c のいずれかに置き換えて、同じ文字が連続しないように文字列を構築せよ、という問題。
解答
基本的には、文字列を舐めて前後の文字と違うものを素直に選び続ければ良い。 効率的な実装を心がけたい。
面倒なコーナーケースは潰しておきたいと思ったので、まずは1文字だけの場合を処理する。
2文字以上の場合も、まずは構築不可能な場合、すなわち、最初から連続する部分が存在しないかをチェックする。
このチェックにはランレングス符号化が便利。
a, b, c のいずれかが2文字以上続いていたらアウトと判定すれば良い。
それらのチェックが終わったら後は純粋に構築していくだけなので、バグに気をつけながら適宜関数に切り分けたりしてコーディングしていく。
var t int var S []rune func main() { t = ReadInt() for tc := 0; tc < t; tc++ { S = ReadRuneSlice() solve() } } func solve() { // 1文字のケース if len(S) == 1 && S[0] != '?' { fmt.Println(string(S)) return } if len(S) == 1 && S[0] == '?' { fmt.Println("a") return } // 以降は2文字以上 // 可能かどうか pressed, nums := RunLengthEncoding(S) for i := 0; i < len(pressed); i++ { r := pressed[i] cnt := nums[i] if r != '?' && cnt > 1 { fmt.Println(-1) return } } for i := 0; i < len(S); i++ { // 決まっていたらパス if S[i] != '?' { continue } if i == 0 { // 次を見る next := S[i+1] S[i] = sub(next) } else if i == len(S)-1 { // 前を見る before := S[i-1] S[i] = sub(before) } else { // 前後を見る next, before := S[i+1], S[i-1] S[i] = subsub(next, before) } } fmt.Println(string(S)) } // rはa, b, c, ?のいずれかで、r以外のa, b, cのいずれかを返す // ?だったらaを返す func sub(r rune) rune { if r == 'a' { return 'b' } else if r == 'b' { return 'c' } else if r == 'c' { return 'a' } else { return 'a' } } func subsub(r, s rune) rune { memo := make(map[rune]bool) memo[r] = true memo[s] = true isA := memo['a'] isB := memo['b'] isC := memo['c'] if !isA { return 'a' } else if !isB { return 'b' } else if !isC { return 'c' } return 'a' } // 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 }
Aから20分くらいかかって幸先が良くないですが、特別詰まったわけではないと思い込みつつ先に進みました。
B. Beautiful Numbers
問題の概要
1, 2, .., n までの順列が配列の形で与えられる。
ここから長さ m の連続する部分列を切り出したとき、 1, 2, .., m の順列になっているかを、
すべての m について判定する問題。
解答
O(n^2) は許されない制約であるため、全探索的な愚直な解法は認められない。
元の順列の 1, 2, .., m の要素の位置を pos[1], pos[2], .., pos[m] とする。
ここで max(pos[i]) - min(pos[i]) + 1 (1 <= i <= m) によって、 1, 2, .., m の要素を含む連続部分配列のうち、
長さが最小のものの長さが手に入る。
この長さが m であれば m の順列をなす連続部分列が取得できるし、
m より大きくなってしまうならば、不純物が混じってしまうため、目的の連続部分列は取得できない（必要十分条件になっている）。
よって、上述の max, min を都度更新していけばすべての m について高速に判定できる。
計算量は全体で O(n) 。
var t int var n int var P []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() P = ReadIntSlice(n) solve() } } func solve() { pos := make([]int, n+1) for i := 0; i < n; i++ { p := P[i] pos[p] = i } answers := make([]rune, n) l, r := pos[1], pos[1] answers[0] = '1' for i := 2; i <= n; i++ { ChMin(&l, pos[i]) ChMax(&r, pos[i]) dist := r - l + 1 if dist == i { answers[i-1] = '1' } else { answers[i-1] = '0' } } fmt.Println(string(answers)) } // ChMin accepts a pointer of integer and a target value. // If target value is SMALLER than the first argument, // then the first argument will be updated by the second argument. func ChMin(updatedValue *int, target int) bool { if *updatedValue > target { *updatedValue = target return true } return false } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false }
C. Beautiful Regional Contest
問題の概要
あるプログラミングコンテストにおいて、 n 人の解答問題数が配列で与えられるので、
それぞれの人に金・銀・銅メダルを授与することを考える。
以下の条件を満たすように、それぞれのメダルの数を求める問題。
- それぞれのメダルの数は正の整数である。
- 金メダルの数は、銀・銅メダルよりも大きい必要がある。ただし、銀メダルと銅メダルの数量関係は不問である。
- 金メダルを受賞する参加者は、銀メダルを受賞する参加者よりも多くの問題を解いていなければならない。
- 銀メダルを...、銅メダルを...。
- 銅メダルを...、メダルを受賞していない参加者よりも多くの問題を解いていなければならない。
- 3つのメダルの合計個数は、
Floor(n/2)以下である必要がある。
解答
満たすべき条件が多いが、素直にそれらを満たすように貪欲的に解を構築していく方針で考える。
条件を整理していく。
条件3, 4, 5より、メダルの種類の境界（メダルを授与されない参加者は透明のメダルでももらうと思っておく）において、 問題の正解数に1以上の差がある必要がある、すなわち、正解数が異なっている必要がある。
よって、ここでもランレングス符号化を施しておくと見通しが良くなる。 以降は、ランレングス符号化が行われている前提で話をすすめる。
（※当然ながら、正答数が多いひとを差し置いて、それより正答数が小さい人にメダルを授与することはできないことに注意する。）
条件1より、符号化後に要素数が3以上である必要があるため、そうでない場合は不可能として終了する。
条件2より、金メダルの受賞者は少ないほうが良いため、正解数が最大の人のみとする。
ここからは、銀メダルと銅メダルの受賞者数を、条件2, 6に気をつけながら増やしていけば良い。 銀メダルについては、金メダルの数より大きくなりさえすればよい。 銅メダルについても、まずは金メダルの数よりは大きくし、まだ条件6に対して余裕があるのであれば、 さらに追加していけば良い。
var t int var n int var P []int func main() { t = ReadInt() for tc := 0; tc < t; tc++ { n = ReadInt() P = ReadIntSlice(n) solve() } } func solve() { g, s, b := 0, 0, 0 limit := n / 2 _, counts := RunLengthEncoding(P) // 圧縮後に最低長さ3は必要 if len(counts) < 3 { fmt.Println(0, 0, 0) return } // gを決める g += counts[0] // sを決める、伸ばす idx := 1 for idx < len(counts) { // gを超えたらbreak if s > g { break } s += counts[idx] idx++ } // bを決める、伸ばす for idx < len(counts) { // gを超えたらbreak if b > g { break } b += counts[idx] idx++ } if g == 0 || s == 0 || b == 0 { fmt.Println(0, 0, 0) return } if s <= g || b <= g { fmt.Println(0, 0, 0) return } sum := g + s + b if sum > limit { fmt.Println(0, 0, 0) return } // bをできるだけ伸ばす for idx < len(counts) { // 足した結果がlimitを超えるなら足さないでbreak if sum+counts[idx] > limit { break } b += counts[idx] sum += counts[idx] idx++ } fmt.Println(g, s, b) } // 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 }
D. Beautiful Sequence
問題の概要
0, 1, 2, 3 の数字がそれぞれ a, b, c, d 個与えられるので、
これらをすべて使い切って1列に並べる。
出来上がった数列に関して、隣り合う数字の差をすべて 1 とすることができるか判定し、
可能ならば具体的に構築せよ、という問題。
解答
判定だけなら結構簡単かもしれないが、構築も要求されるとすごく難しい。
（以下はeditorialそのままです。）
まず、作るべき数列に関して、偶数は 0, 0, .., 0, 2, 2, .., 2 と並べるのが最適となる。
こうすることで、 3 を置くことができる箇所を最大化できる一方で、 1 はどの間でも置くことができる。
※この時点で少し難しい気がする。
構築可能なときに必要な 1 の数が変わっておらず、かつ 3 を受け入れる箇所を最大化出来ているから最適、と読めば良い？
この後は、まず 3 を 2 の間に並べて、隙間の数が足りないならば端に置く、
続いて 1 を残っている隙間に入れて、足りなければやはり端に置く、とすれば良い。
しかし、具体的に条件分岐させて一発での構築を目指すと、かなり複雑になると思う（というより私は諦めました）。
editorialの実装例では、以下のように開始する数に関して全探索を行うような賢い実装を行っている。
var A map[int]int func main() { a, b, c, d := ReadInt4() total := a + b + c + d for i := 0; i < 4; i++ { A = make(map[int]int) A[0], A[1], A[2], A[3] = a, b, c, d answers := []int{} if A[i] > 0 { last := i answers = append(answers, last) A[last]-- for { if A[last-1] > 0 { A[last-1]-- answers = append(answers, last-1) last-- } else if A[last+1] > 0 { A[last+1]-- answers = append(answers, last+1) last++ } else { break } } if len(answers) == total { fmt.Println("YES") fmt.Println(PrintIntsLine(answers...)) return } } } fmt.Println("NO") }
配列ではなく辞書を使うことで last-1 の負数判定をなくしたりと、きれいな実装の参考になりました。
AtCoder緑ぐらいの人たちでランレングス符号化を用意していない人が居たら、ぜひ用意してみていただきたいです。 意外と便利なので。
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つ引き出しを増やしていくしか無いのかも。
未だにグローバルに変数を置いたり、命名を適当にやってしまうことに抵抗があります。
