競技プログラマーにアピールしたいVim/VSCodeVim
この記事の目的
エディタに興味の薄い競技プログラマー（あるいは誰でも）に、「Vimちょっと調べてみようかな、遊んでみようかな」と少しでも思ってもらうことです。
導入
私は昨年の4月に働き始めてからVimを使い始めて、1年半ほど経った今ではVimキーバインドは手放せないものとなりました。
職場で周囲のほとんどの人がVimを使っていたことから、「きっと素晴らしいものなんだろう」と思いはじめました。 当時は研修中で比較的時間に余裕があったため、帰宅してからVimについて調べたり練習したりしていました。
また一方で、昨年9月頃から始めた競技プログラミングでは、素早く問題を解くことが重要で、ひいては高速なコーディングがプレイする上で有利になります。 最近ではVSCodeを使っている競技プレイヤーも多いようですが、幸いVSCodeにはVSCodeVimという優れたVim拡張があります。 多少の初期投資によって今後一生活かせる、快適で高速で、そしてなにより楽しいコーディング体験をしてみませんか。
Vimって難しいんじゃないの？
しばしば、Vimの習得難易度は高いと聞きます。 自分もVimを使い始めるまではそう思っていましたし、実際にそのとおりな部分もあると思います。 しかしながら、標準のキーバインドや初歩的なコマンドを常用して快適にコーディング・文書作成する分には、それほど難しいものではないと思っています *1。
自分の場合、よく使うコマンドを整理した上で数週間Vim縛りでコーディング、テキスト編集をしていたら、自然と定着していました。
Vimを覚えるためのモチベーション
「これは便利そう」と思えるような「かんたんな」操作を実際に観てみる のが一番いい気がします。
よく「とりあえずvimtutorをやってみよう」とか「実践Vimという本を読むといいよ」と呼びかけているのを見かけます。 しかしながら、これらを両方完遂できる人はすでに決意が硬い人であって、殆どの「やってみようかな」レベルの人は途中で折れるか飽きてしまうような気がします *2。
いずれはこれらについても一度さらっておいたほうがいいのは間違いないのですが、 まずは強い動機づけをすることで、意欲を保ったまま効率的に学習できると考えています。 そのために、黒魔術のようなとても覚えられそうにないものではなく、すぐにでも便利に使えそうな操作を「下見してみる」のが良いかと思います。
私が1年半ほど使ってみて、今でも変わらずに便利だと思っておりかつかんたんな操作は、以下のようなものです。
テキストオブジェクトの操作
私がVimを学び始めて一番「おおっ」となったのはこれで、今でも他人に勧めたい操作No.1です。
かんたんに紹介すると、例えば ciw は "correct in word" の略で、現在カーソルが置かれている単語を削除しインサートモードに移行するコマンドです（ ※嘘でした ）。
削除後にインサートモードに移行してくれるおかげで、単語を即座に修正することができます。
あるいは、 da" とすると "delete all "" の略で、現在カーソルが置かれておりダブルクォートで囲まれている部分を、
ダブルクォート含めてすべて削除するコマンドです。
これらのコマンドを XYZ と表すなら、 X = {c(correct), d(delete), y(yank, copy), v(visual)}, Y = {i(in), a(all)}, Z = {(, ), [, ], ", ', w, ...}
というようなバリエーションが有り、それぞれの要素数の掛け算の数だけ異なった操作ができることになります。
※2020-07-16追記 : うっでぃさんよりコメントでご指摘いただきましたが、 in/allは嘘でした。正しくはinner/a or an objectというのが正式 のようです（ :h v_a 参照）。
2年以上頭の中でin/allで考えてしまったのでなかなか脳内修正が難しいですが、上述はあくまで「私の頭の中の動き」とお考えください（ていうかよくよく英語的に動詞・目的語で考えたらin/allじゃ文法が壊れてますね）。
同様な操作を普通のエディタでやるならば、マウスカーソルで正確にドラッグする手間が必要だと思います。 あるいは、カーソルを消したい文字の一番右に移動させてからback space長押し、とかでしょうか。
一方、Vimであれば「雑に」目標位置にカーソルを移動させたあと、上記の3つのキーを押下するだけで、所望の結果が達成できます。
ノーマルモードにおける o コマンド
めちゃくちゃ地味なんですが、これを知ったときかなり嬉しかったのを覚えています。
このコマンドは、現在のカーソル位置に関わらず、1つ下に改行してインサートモードに移行します。 行の途中にカーソルがあるけど、すぐ下に改行したい、というケースは結構あるのではないでしょうか。
これも普通のエディタだと、「カーソルを行末に移動させてEnter」という手間が必要だと思いますが、Vimならばキー入力一回のみです *3。
dd による1行削除、 yy による一行コピー
これもとても地味ですが、1行単位で削除したりコピーしたりというのは、頻繁に行う操作の1つかと思います。
Vimでは、これらはそれぞれ dd および yy で実現できます。
p で後ろにペーストできます。
普通のエディタを使っていた頃は、複数回左クリックし行を選択してからback spaceもしくはctrl+cとかやっていました （行全体を選択するのに2回でいいときと3回やらないとダメなときとかがあって、ちょっといらっとするときがあります）。
surround.vimによる「なにかを囲むもの」に対する操作
Vimネイティブなものではなく、プラギンの範疇なのですが、おそらくは導入することになるので紹介しています。
ちょっと操作がややこしくなりますが、例えば以下のように、ビジュアルモードで選択した範囲について Sb もしくは S( と打つと、
選択範囲を丸括弧で囲んでくれます。
また、ビジュアルモードを介さなくても、先述のテキストオブジェクトの要領で ysiw" と打つと、
現在カーソル位置にある単語に対してダブルクォートで囲むことができます。
あるいは、既存の「囲んでいるもの」を別のものに置換することもできます。
例えば、 cs'" と打つと、現在のカーソル位置を囲んでいる最近傍のシングルクォートを、ダブルクォートで置換します。
もう予想がつくかもしれませんが、 dsb とすると、カーソル位置を囲む最近傍の丸括弧を削除します。
紹介した操作の中ではちょっとだけ複雑ですが、何回も使っていると忘れないぐらいには頭に染み込んできます。 直前に別のプログラミング言語を使っていて、「この言語では丸括弧が必要なのに丸括弧なしで書いちゃった」というときなどはよく使っています。
ごく一部ですが、私が特に便利だと感じている操作を紹介しました。 殆どの操作において、普通のエディタならばマウスや矢印キーを慎重に使うことが要求されるのに対し、Vimでは雑かつ楽に実行できます。
VSCodeVim: VSCodeのVim拡張
VSCodeにおけるVim拡張がVSCodeVimなんですが、話を聞いたところ他のIDEのVimプラグインに比べて出来がいいようです*4。
個人的に優れていると思うのは、以下の点です。
- オリジナルのキーマッピング設定が（それなりに）可能、初心者によっては.vimrcよりも書きやすいかも
- 有名なVimプラギンがデフォルトで有効になっている
- VSCodeオリジナルの機能とのバッティングがない（自分が知らないだけかも）
1については、例えば ESC を jj にマッピングしたりだとか、
ctrl + h,l について、ノーマルモード時はビューグループ間の左右移動でインサートモード時はカーソルの1文字左右移動にしたりとか、
モードごとに動作を変えたりもできます。
なので、込み入ったものでなければ.vimrcに記述しているようなカスタムマッピングは、たいていVSCodeVimでも再現できます。
2については、surround.vim, easymotion, commentary.vimなどが該当します*5。
雑に紹介しておくと、easymotionはカーソル移動に関するプラギンで、例えば <space><space>j と打つと*6、下方向へのジャンプのアシスト文字が表示され、
対応する文字を入力すると、文字が付与されている部分にカーソルがジャンプします。
また、commentary.vimはコメント補助のプラギンで、 gcc とだけ打つとカーソル位置の行をコメントアウトしてくれます。
また、行ビジュアルモードで複数行選択している状態で gc と打つと、その行範囲をすべてコメントアウトしてくれます。
3については、そもそもVSCode本来の機能で便利なものが多いため、VSCodeの強みとVimの強みの両方を享受できます。 VSCodeの話になりますが、ファジーファインダーになっているquickOpenが特にお気に入りです。
インストール方法はVSCodeの他の拡張機能と同じで、簡単に導入・破棄できます。 「ちょっとだけVim試してみよう」と思ったら是非気軽にインストールしてみてください。
おまけ: Vimを学ぶことによる副次的なメリット
ある程度Vimに習熟してから気づいたことですが、以下のようなメリットがあったことに気づきました。
- いくつかのVimキーバインドとシェルのショートカットが同じであるため、シェルの操作も効率的に行えるようになる
- 置換コマンドを覚えると同時に、かんたんなsedコマンドの使い方も覚えられる
- 置換コマンドを覚えると同時に、正規表現も覚えられる
- CUIに抵抗がなくなる、CUIが好きになる
1年目はフロントエンドの業務がほとんどであり、シェルを操作する機会が少なかったため、 このあたりの抵抗が早めになくせたのは、個人的には結構大きいと思っています。
これらをVimを学習する主たる動機にするのは難しいと思いますが、一応触れておこうと思いました。
おわりに
Vimの解説記事などは出尽くしており、今更自分が書くほどでもないと思ったので、 「自分はVimのここが好きで、そんなに導入コストは高くないと思うから試してみて！」という部分に特化した内容をまとめてみました。
自分自身、これまでVimのいいところに触れる機会がなく、もっと早く知っていればなぁと思ったりしたので、 若い人などで「Vimってなんなの？」と思っている人が少しでも興味を持ってくれたりするととても嬉しいです。
ちなみに、私は業務ではVSCodeを、競技プログラミングではneovimを使っています*7。
*1:Vim scriptや周辺技術をちゃんと理解してプラギンを管理したり、あるいはプラギンを自作するとなると、とても難しくなってくるという認識です。
*2:どちらも優れた教材なのは疑いようがなく、実際に私も両方やりました。
*3:これは流石に自分のエディタ操作スキルが低いだけで、それぞれのエディタでショートカットがあるものなのかもしれません。
*4:聞いたところによると、Vimの基本的な機能もエミュレートできていないものもしばしばあるとか。
*5:最近はREADMEを読めていないので、もう少し増えているかもしれません。
Codeforces Round No.591 (Div.2) 参加記録（A〜D解答）
初めての unrated codeforces を体験してしまいました。
A, B, Cがコンテスト後に確認したところちゃんと通っており、Dは嘘解法だったようでpretestで弾かれていました。
Dも勉強になりそうな雰囲気なので、後日解説ACの上追記していきます（2019-10-11に追加）。
全体
A. CME
問題
※長いので意訳。
q 個のクエリに対して n が与えられる。
n 本のマッチ棒を必ず使い切り a + b = c という数式を満たすようにマッチ棒を a, b, c に割り当てる。
ただし、 a, b > 0 でなければならない。
数式を作る際にマッチ棒が足りない場合、好きな本数買い足すことができる。
各 n に対して、買い足す必要のあるマッチ棒の本数の最小値をそれぞれ答えよ。
制約: 1 <= q <= 100, 2 <= n <= 10^9
解答
必要なマッチの総本数は明らかに偶数であり、逆に偶数本マッチがあればCMEを作れる。
なので、 n が偶数ならば 0 、奇数ならば 1 とすれば良い。
ただし、 n = 2 のときは a + b = 1 となり、いずれかが 0 となって条件を満たせなくなる。
これを避けるために、左辺と右辺にそれぞれ 1 ずつ足す必要があり、2 本必要となる。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n := ReadInt() if n%2 == 0 { if n/2 == 1 { fmt.Println(2) } else { fmt.Println(0) } } else { fmt.Println(1) } } }
上で「明らかに」とか言ってますが、コンテスト中は無為に数式こねくり回してますし、 前日のAGCで太陽拝んでしまった後遺症でコーナーケース探りまくっていて、 提出に15分かかっています。
B. Strings Equalization
問題
2つの英小文字からなる、同じ長さの文字列 s, t が与えられる。
「操作」は何回行っても良い（0回でも良い）。
操作では、どちらの文字列についてでも、2つの隣り合った文字に関して、1つ目に選んだ文字を2つ目に選んだ文字に代入して良い。
q 個のクエリが与えられるので、それぞれの s, t について、任意回数の操作のもとで s, t を等しくできるかどうか判定せよ。
制約: 1 <= q <= 100, 1 <= |s| = |t| <= 100
解答
制約が小さく、文字列を全部舐めても大丈夫なことを抑える。
「何回でも操作ができる」というのが強力で、ある文字列中に存在する1文字によって、 それを左右に伝搬する形でその文字列の他の文字列を上書きしてしまえる。
よって、 s, t について舐めて、「それぞれに同じ文字が1文字でも存在すればOK、なければNG」とする。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { S := ReadRuneSlice() T := ReadRuneSlice() smemo := [ALPHABET_NUM]int{} tmemo := [ALPHABET_NUM]int{} for j := 0; j < len(S); j++ { s, t := S[j], T[j] smemo[s-'a']++ tmemo[t-'a']++ } flag := false for j := 0; j < ALPHABET_NUM; j++ { if smemo[j] > 0 && tmemo[j] > 0 { flag = true break } } if flag { fmt.Println("YES") } else { fmt.Println("NO") } } }
これも10分弱悩まされてしまったのが悔しい。
C. Save the Nature
問題
※長いので意訳。
n 枚のチケットを好きな順番で売ることができる。
売上の一部は以下の規則のもとで、環境保全基金に寄付される。
aの倍数番目で売られたチケットのx％が寄付される。bの倍数番目で売られたチケットのy％が寄付される。a, bの公倍数番目で売られたチケットのx + y％が寄付される。
できるだけ少ない枚数のチケット販売で目標トータル寄付金額 k を寄付したい。
目標を達成するためのチケット販売枚数の最小値を答えよ。
また、全チケットを販売しても目標が達成できない場合は -1 を出力せよ。
クエリが q 個与えらるため、それぞれについて答えよ。
制約:
1 <= q <= 1001 <= n <= 2 * 10^5100 <= p[i] <= 10^9, p[i] % 100 = 01 <= a, b <= n, 1 <= x, y <= 100, x + y <= 1001 <= k <= 10^14- チケットの全クエリの合計は
2 * 10^5を超えない。
解答
当然ながら、各クエリについてすべてのチケットの順列を総当りすることはできない。
また、チケットの金額が高いものほど、寄付割合の高い順番に配置したいが、
できるだけ少ない枚数のチケットで目標を達成したいという縛りがあるため、
貪欲に a, b の公倍数番目に高いチケットを配置するわけにはいかない。
とりあえず「答えを m 枚として、目標を達成できる最適なチケットの並べ方」をイメージしてみる。
このような並び方を考えたとき、 m 枚のチケットは、すべてのチケットを高い順に並べたときの金額の上位 m 枚となるはずである。
（仮に、必ずしも高い順に m 枚となっていなくても目標を達成できる場合、上位 m 枚に入らないチケットと上位 m 枚のチケットと交換しても、金額的に損しないので変わらずに目標を達成できる。）
また、 m 枚のチケットで目標が達成できるとき、 m + 1 以上のチケットでも当然目標が達成できる。
よって、二分探索で m の境界を探索してやればよい。
m 枚で条件を達成できるかの判定は、少し横着をして n * logn で行うことにした。
※大雑把な見積もりでも、
logn[i] * n[i]logn[i] = n[i](logn[i])^2 <= n[i](logn)^2 (n = Sum(n[i])) より、
Sum(n[i](logn[i])^2) <= (logn)^2 * Sum(n[i]) = n * (logn)^2 なので、間に合いそうと判断。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n := ReadInt() P := ReadIntSlice(n) for j := 0; j < n; j++ { P[j] /= 100 } x, a := ReadInt2() y, b := ReadInt2() k := ReadInt64() sort.Sort(sort.Reverse(sort.IntSlice(P))) percents := make([]int, n) for j := 0; j < n; j++ { if (j+1)%a == 0 && (j+1)%b == 0 { percents[j] = x + y } else if (j+1)%a == 0 { percents[j] = x } else if (j+1)%b == 0 { percents[j] = y } } isOK := func(m int) bool { tmp := make([]int, m) for h := 0; h < m; h++ { tmp[h] = percents[h] } sort.Sort(sort.Reverse(sort.IntSlice(tmp))) val := int64(0) for h := 0; h < m; h++ { val += int64(tmp[h]) * int64(P[h]) } if val >= k { return true } 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 } } if isOK(ok) { fmt.Println(ok) } else { fmt.Println(-1) } } }
正しい考察にたどり着くまでに結構時間がかかってしまったので、この速度を上げるように努めたいです。
D. Sequence Sorting（※2019-10-11に追加）
問題
整数の数列 A が与えられる。
この数列に対して、1回の操作で、ある要素 x を選んだときに、すべての x を一番右、もしくは一番左に移動させることができる。
各クエリについて、最終的に、数列が非減少となるようソートするために必要な操作回数の最小値を答えよ。
制約:
1 <= q <= 3*10^51 <= n <= 3*10^51 <= n <= n- クエリに渡って
nの合計は3*10^5は超えない。
解答
すべての要素について非減少となるようソート済みの数列に対して、
初期状態ですでにソート済みの部分列（間になにか「不純物」が挟まっていてもいい）を考える。
このソート済みの部分列の長さを l とし、数列中のユニークな要素の数を t とすると、
t - l の要素については必ず一度は左・右のいずれかに寄せる必要がある。
また、正しい順番であればそれぞれの操作対象の要素について1回のみ右・左のいずれかに寄せれば、目的のソート済み数列が得られる。
よって、一番長いソート済みの列の長さを求めることを考える。
これを数えるためには、数列中における各要素 x について、その登場位置の最大・最小をそれぞれ前計算して求めておくことで計算できる。
前計算のあとは、ユニークな要素を昇順ソートしたものに対し、前から順に見て「小さい方の要素の最大位置 < 大きい方の最小位置」となっていれば、
今注目している部分列の長さを加算し、そうでなければリセット、というふうにして線形探索すればよい。
各クエリにおいて、ソート部分がネックになるため、計算量は O(nlogn) 。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n := ReadInt() A := ReadIntSlice(n) maxIds, minIds := make(map[int]int), make(map[int]int) // A[j]のmax, minなidxを記録 for j := 0; j < n; j++ { maxIds[A[j]] = j } for j := n - 1; j >= 0; j-- { minIds[A[j]] = j } // A[j]についてuniq | sortする uniqs := []int{} for k := range maxIds { uniqs = append(uniqs, k) } sort.Sort(sort.IntSlice(uniqs)) ans := 1 tmpAns := 1 for j := 0; j < len(uniqs)-1; j++ { l, r := uniqs[j], uniqs[j+1] if maxIds[l] < minIds[r] { tmpAns++ } else { ChMax(&ans, tmpAns) tmpAns = 1 } } ChMax(&ans, tmpAns) fmt.Println(len(uniqs) - ans) } }
Goだと実行時間が1100msecぐらいになってました。
n = 3*10^5 における O(nlogn) あたりからはあまり横着した実装をしないように注意するべきなのかもしれません。
（minIdx, maxIdx は範囲が小さいのでちゃんと固定長配列とかでやるべきだったかも。）
感想
Cとかは別にクエリ形式にする必要ないのでは。。？
社会人として、日曜0時スタートのコンテストが unrated になるのはなかなか心にくるものがありますが、 問題自体は楽しいので引き続き参加していきたいです。
Codeforces Round No.590 (Div.3) 参加記録（A〜E解答）
全体
残り時間15分ぐらいで後回しにしたCが解けて5完でした。
Cに時間がかかりすぎてしまったのは悔やまれますが、実力的に何回参加しても好転はしないと思います。
Eはコンテスト中に目を通せて「面白そう」と思ったので、後日解き直しました（解説ACになりましたが）。
- 全体
- A. Equalize Prices Again
- B1. Social Network (easy version)
- B2. Social Network (hard version)
- C. Pipes
- D. Distinct Characters Queries
- E. Special Permutations
- 感想
A. Equalize Prices Again
問題
※やたらと長いので意訳。
各値段が A[i] コインである n 個の商品のすべての値段を等しくしたい。
もともとの商品の値段合計よりも小さくならないという条件のもとで、金額はいくらに設定すればよいか。
このようなクエリが q 個与えられるので、それぞれについて答えよ。
制約: 1 <= q <= 100, 1 <= n[i] <= 100, 1 <= A[i] <= 10^7
解答
各クエリの情報を読み込みながら、都度 Ceil(sum / n) を計算すれば良い。
var q int func main() { q = ReadInt() for i := 0; i < q; i++ { n := ReadInt() A := ReadIntSlice(n) sum := Sum(A...) fmt.Println((sum + (n - 1)) / n) } }
特に言うことはないと思います。
B1. Social Network (easy version)
問題
※問題文があまりにも冗長なので省略。
解答
要するに、以下を守りながら、ディスプレイを配列でモデル化し、シミュレーションを行えば良い。
- 次に処理するメッセージがすでにディスプレイに表示されているのならば、何もしない。
- 次に処理するメッセージが表示されていない場合は、そのメッセージを配列の先頭に挿入する。
- ディスプレイサイズが
kを超える場合、配列の最後尾のメッセージを配列から除外する。
最後に、シミュレーション終了時の配列を出力すればOK。
なお、easy versionは制約が小さいので、配列の調整やメッセージの存在チェックを適当に都度スキャンしても通る。 実際に、コンテスト中は完全なシミュレーションに集中したので、効率化を一切考えないコードを書いた。
var n, k int var A []int var Ids []int func main() { n, k = ReadInt2() A = ReadIntSlice(n) Ids = []int{} for i := 0; i < n; i++ { a := A[i] if isExist(a) { continue } newIds := []int{} newIds = append(newIds, a) if len(Ids) < k { newIds = append(newIds, Ids...) } else { newIds = append(newIds, Ids[:len(Ids)-1]...) } Ids = newIds } fmt.Println(len(Ids)) fmt.Println(PrintIntsLine(Ids...)) } func isExist(id int) bool { for i := 0; i < len(Ids); i++ { if id == Ids[i] { return true } } return false }
正直英文読解が最大の敵だと思いました （サンプル見るまで確信が持てませんでしたし、なんならサンプル見るまで勘違いしている部分もありました）。
B2. Social Network (hard version)
問題
※easy versionと問題設定は全く同じ。
制約: 1 <= n, k <= 2 * 10^5, 1 <= Id[i] <= 10^9
解答
総メッセージ数とディスプレイサイズが大きくなったため、easy versionのコードは通らなくなった。 具体的には、
- 存在チェックの際、ディスプレイをスキャンしている
- メッセージの出し入れの部分を、新しい配列に順番が正しくなるようにすべて詰め直している
部分がまずい。
それぞれ、
- 存在チェックを
mapで行う - ディスプレイの向きを逆向きにすることでQueueでディスプレイをモデル化できるため、出し入れが
O(1)で可能になる。
というふうに変更する。
var n, k int var A []int var Ids []int var memo map[int]int func main() { n, k = ReadInt2() A = ReadIntSlice(n) memo = make(map[int]int) for i := 0; i < n; i++ { memo[A[i]] = 0 } Ids = []int{} for i := 0; i < n; i++ { a := A[i] if isExist(a) { continue } // 追加 memo[a] = 1 Ids = append(Ids, a) if len(Ids) <= k { continue } else { memo[Ids[0]] = 0 Ids = Ids[1:] } } fmt.Println(len(Ids)) reverseIds := rev() fmt.Println(PrintIntsLine(reverseIds...)) } func isExist(id int) bool { if value, ok := memo[id]; ok { if value == 1 { return true } else { return false } } else { return false } } func rev() []int { res := []int{} for i := len(Ids) - 1; i >= 0; i-- { res = append(res, Ids[i]) } return res }
C. Pipes
問題
2行n列のマス目に対して、各マスに6種類のパイプが設置されている。 各マスのパイプを時計回り・反時計回りに90度単位で何回も回転させて良い。 左上から流入する水を、右下に流出させることが可能か答えよ。
また、このようなクエリは q 個与えられ、それぞれについて n およびパイプの配置が与えられるので、
それら全てに答えよ。
※パイプの種類や水の流し方に関する制約は、問題文の図が詳しいのでそちらをご参照ください。
制約: 1 <= q <= 10^4, 1 <= n <= 2 * 10^5(n の総和は 2 * 10^5 を超えないことが保証される)
解答
行列の列の総和がboundされているため、素直にクエリごとに各マスのパイプをチェックして問題ない。
整理すると、問題がシンプルになる。
- パイプ1, 2は互いに同じで、パイプ3, 4, 5, 6はそれぞれ互いに同じ
- 水を左方向に流す意味はない
- 3, 4, 5, 6のパイプを経由して行方向を上・下に移動した後に1, 2のパイプに出会った場合は、確実に失敗する
- それぞれ行列を上・下に踏み外すか、水が流れなくなるかのいずれかのため
以上から、初期位置を (0, 0) とし、出会ったパイプの種類によって座標を変化させていけば良い。
var q int var n int var Rows [2][]rune func main() { q = ReadInt() for i := 0; i < q; i++ { n = ReadInt() Rows[0] = ReadRuneSlice() Rows[1] = ReadRuneSlice() // 現在地 h, w := 0, 0 for w < n { if Rows[h][w] == '1' || Rows[h][w] == '2' { w++ } else { if h == 0 && (Rows[1][w] == '1' || Rows[1][w] == '2') { fmt.Println("NO") break } if h == 1 && (Rows[0][w] == '1' || Rows[0][w] == '2') { fmt.Println("NO") break } if h == 0 { h++ w++ } else { h-- w++ } } if w == n { if h == 0 { fmt.Println("NO") } else { fmt.Println("YES") } } } } }
It is guaranteed that the sum of n over all queries does not exceed 2 * 10^5
を見落としたため、無理だと思って先にDを解きました。
実装で手間取りすぎてこの問題だけで1時間弱使ってしまった結果を見ると、正しい動きでした。
D. Distinct Characters Queries
問題
英小文字のみからなる文字列 s と、この文字列に関する q 個のクエリが与えられる。
s[l;r] を s の部分文字列 s[l], s[l+1], ..., s[r] とする。
クエリは2つのタイプからなる。
1 pos c:s[pos]をcで置換する2 l r: 部分文字列s[l;r]内の異なる文字の個数を計算する
各クエリに答えよ。
制約: 1 <= |s| <= 10^5, 1 <= q <= 10^5
解答
26種類の文字について累積和が計算できれば、与えられた区間内の各文字の個数は計算できるので、 1個以上存在する文字の種類数が答えになる。
しかしながら、あるインデックスについて文字の置換が途中で割り込むため、通常の累積和では再計算していては間に合わない。
BITが要件を満たしており、26個に増やすのも容易に思えたため、BITを採用した。
const ALPHABET_NUM = 26 var S []rune var q int // [1, n] var bit [ALPHABET_NUM][100000 + 5]int var lenS int func sum(i, alpha int) int { s := 0 for i > 0 { s += bit[alpha][i] i -= i & (-i) } return s } func add(i, alpha, x int) { for i <= lenS { bit[alpha][i] += x i += i & (-i) } } func main() { S = ReadRuneSlice() q = ReadInt() lenS = len(S) for i := 0; i < len(S); i++ { r := S[i] c := int(r - 'a') add(i+1, c, 1) } for i := 0; i < q; i++ { query := ReadInt() if query == 1 { idx := ReadInt() R := ReadRuneSlice() newc := R[0] newcint := int(newc - 'a') oldc := S[idx-1] oldcint := int(oldc - 'a') add(idx, newcint, 1) add(idx, oldcint, -1) S[idx-1] = newc } else { l, r := ReadInt2() res := 0 for alpha := 0; alpha < ALPHABET_NUM; alpha++ { ss := sum(r, alpha) - sum(l-1, alpha) if ss > 0 { res++ } } fmt.Println(res) } } }
26個の累積和を計算し終わった後に点更新できない事に気づき、紙の蟻本を取りに行きました。
あと提出し終わった後、長さ0の文字列がケースに入っていないかとても心配でした （プログラムがコケるから無いだろうと決め込みましたが。。）。
E. Special Permutations
問題
数列 P(i, n) を [i, 1, 2, ..., i-1, i+1, ..., n] のように定義する。
すなわち、 n の順列とほとんど同じだが、 i のみが先頭に移動したものである。
また、数列 X: X[1], X[2], ..., X[m] (1 <= X[i] <= n) が与えられる。
pos(P, val) は数列Pが与えられたときの、数列P中における val が位置する1-basedのインデックスである。
ここで、関数 f(P) = Sum(|pos(P, X[i]) - pos(P, X[i+1])|) を定義する。
f(P(1, n), n), f(P(2, n), n), ..., f(P(n, n), n) を求めよ。
解答
問題文でも言われている通り、先頭に何が移動しようが、もとの昇順に並んだ数列 P(1, n) とほとんど同じであることを踏まえると、
関数 f の値もそれぞれ似通いそう、すなわち f(P(1, n), n) を事前にもとめておいて、
それを適切に調整すればうまく求められそうな気はする。
実際、以下の図のように場合分けによって、項間の距離が計算できる。
手順としては、以下のようなものとなる。
- 昇順に並んだ数列について関数値を求め、これをベースとする。これは、単純に
Xの階差の和で求まる。 - 各
X[i]についてX[i]が先頭に来る場合のX[i-1]とX[i+1]との距離（A[i]とする）を計算しておく。先述の図示した内容に従って場合分けすれば良い。 X中における1 <= i <= nなiが登場する箇所をリスト形式（C[i]とする）で記憶しておく。後半でベースをもとにf(P(i, n), n)を計算する際、リストC[i]の中身についてのみ、2で求めた値を参照する。もともとベースを計算するために用いた階差が、2で求めた値に置き換わることとなる。- すべての
Xに置ける隣接項のペア（公式tutorialではsegmentというワードが使われている）について、1 <= i <= nなiが間に挟まるものの数を数える。cnt[i]とすると、これが求まればベースからcnt[i]を引くことで、「iが先頭に来ることによってグループ1とグループ2の間の距離が1縮まる」という部分が、すべてのXの隣接項ペアについて考慮できたことになる。普通にやるとO(m * n)なので、imos法によりO(m + n)で賢く行う。 - これまでに前処理したデータを利用し、ベースを調整することで各
f(P(i, n), n)を求める。おおまかな方針は以下のようになる。X[idx]が先頭に移動する場合は、ベースを求めるのに使った階差の代わりにA[idx]を使うようにする。cnt[i]をベースから引く。
コードの最後で2重ループとなっているが、 C の要素数は全部で m であるため、
計算量は O(n + m) となって十分間に合う。
var n, m int var X []int var A, diff []int var C [][]int var cnt []int func main() { n, m = ReadInt2() X = ReadIntSlice(m) // Xの階差を計算する、和がf(P1(n))となる diff = make([]int, m-1) for i := 0; i < m-1; i++ { diff[i] = AbsInt(X[i] - X[i+1]) } // X[i]が数列の先頭に来る場合の、前後のxとの位置の差の絶対値を計算しておく A = make([]int, m) for i := 0; i < m; i++ { if i < m-1 { if X[i+1] > X[i] { A[i] += X[i+1] - 1 } else if X[i+1] < X[i] { A[i] += X[i+1] } } if i > 0 { if X[i-1] > X[i] { A[i] += X[i-1] - 1 } else if X[i-1] < X[i] { A[i] += X[i-1] } } } // X中における、1<=i<=nのiが登場する位置を記憶しておく C = make([][]int, n+1) for i := 1; i <= n; i++ { C[i] = []int{} } for i := 0; i < m; i++ { C[X[i]] = append(C[X[i]], i) } // cnt[i]: 1<=i<=nのiについて、 // Xにおけるすべての隣接項間のうち、隣接項間にiが挟まるものの個数 cnt = make([]int, n+1) for i := 0; i < m-1; i++ { if AbsInt(X[i]-X[i+1]) < 2 { continue } else { cnt[Min(X[i], X[i+1])+1]++ cnt[Max(X[i], X[i+1])]-- } } for i := 0; i < n; i++ { cnt[i+1] = cnt[i+1] + cnt[i] } base := int64(0) for _, d := range diff { base += int64(d) } answers := []int64{} for i := 1; i <= n; i++ { ans := base for _, idx := range C[i] { if idx == 0 { ans += int64(A[idx] - diff[idx]) } else if idx < m-1 { ans += int64(A[idx] - diff[idx] - diff[idx-1]) } else { ans += int64(A[idx] - diff[idx-1]) } } ans -= int64(cnt[i]) answers = append(answers, ans) } fmt.Println(PrintIntsLine(answers...)) } // PrintIntsLine returns integers string delimited by a space. func PrintIntsLine(A ...int64) string { res := []rune{} for i := 0; i < len(A); i++ { // str := strconv.Itoa(A[i]) str := strconv.FormatInt(A[i], 10) res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) }
図示したところの、「グループ1とグループ2の要素間はもともとの距離から1縮まる」の部分が、 なぜか自力では最後の方まで抜けてしまっていました。。 気づいてもimos法の適用までには至れず、解説ACとなりました。
個々に要求される知識や実装はそれほど難しいわけではないですが、 しっかり落ち着いて解ききるにはまだ地の力足りてないなぁ、という気がします。
筋トレしましょう。
感想
Codeforcesってクエリ問題多いんですかね？
今回Cでやらかした制約の見落としなんかはこれからもありそうなので気をつけたいと思います。
Codeforces Round No.589 (Div.2) 参加記録（A〜C解答）
全体
結果は前回と同じくA, Bの2完でしたが、通すべきCを通せなかったので順位もパフォーマンスも惨憺たる事に。。
Dも難易度的にはちょうど良さそうで解いてみたいのですが、 方針としてコンテスト中の集中力がある状態で目を通した問題のみ時間を書けて復習する、としているので、とりあえずはCまでを解きます。
A. Distinct Digits
問題
以下の2つの条件を満たす x が存在すれば、どれでも良いので1つ出力せよ。
存在しない場合は -1 を出力せよ。
l <= x <= rxのすべての桁の数が異なる
制約: 1 <= l <= r <= 10^5
解答
調べるべき範囲が十分狭いので、全探索を行う。
var l, r int func main() { l, r = ReadInt2() for i := l; i <= r; i++ { if sub(i) { fmt.Println(i) return } } fmt.Println(-1) } // すべての桁の数字が異なるかどうか？ func sub(n int) bool { nn := n memo := [10]int{} for n > 0 { memo[n%10] = 1 n /= 10 } res := 0 for i := 0; i < 10; i++ { res += memo[i] } if res == decimalLength(nn) { return true } return false } // nの10進数表現の桁数 func decimalLength(n int) int { res := 0 for n > 0 { res++ n /= 10 } return res }
なんということは無い問題なんですが、個人的にこのような繰り返し整数除算するコードを書くのなんか苦手です（素因数分解とか）。
このときもやたらと石橋を叩いて時間を使いすぎたので、そろそろ自信を持ちたい。。
B. Filling the Grid
問題
※長いので意訳
各行・列に与えられた数値が1つのみのロジックパズル（マリオのピクロスみたいなやつ）について、
完成後のパターンとして考えられるものの数を 10^9+7 で割ったあまりで答えよ。
制約: 1 <= h, w <= 10^3
解答
素直にシミュレーションを行う。
行方向について決定するときは素直に決めればよいが、 続いて縦方向について決定するときは、矛盾のチェックを逐次行う。
矛盾が最後までなければ、未確定のマスの数の分だけ2倍していき、都度MODを取れば良い。
var h, w int var R, C []int var cells [1000 + 5][1000 + 5]int // 1: 黒, 0: 白 var dones [1000 + 5][1000 + 5]bool // true: 確定 func main() { h, w = ReadInt2() R = ReadIntSlice(h) C = ReadIntSlice(w) // 行は無責任に決める for i := 0; i < h; i++ { r := R[i] for j := 0; j < r; j++ { cells[i][j] = 1 dones[i][j] = true } // 白で確定させる cells[i][r] = 0 dones[i][r] = true } // 列はチェックしながら決める for j := 0; j < w; j++ { c := C[j] for i := 0; i < c; i++ { if dones[i][j] { // すでに決定済みかつ、白でないとダメなら矛盾 // 黒だったならOK if cells[i][j] == 0 { fmt.Println(0) return } } else { cells[i][j] = 1 dones[i][j] = true } } // 白で確定させる if dones[c][j] { // すでに決定済みかつ、黒でないとダメなら矛盾 // 白だったならOK if cells[c][j] == 1 { fmt.Println(0) return } } else { cells[c][j] = 0 dones[c][j] = true } } ans := int64(1) for i := 0; i < h; i++ { for j := 0; j < w; j++ { if !dones[i][j] { ans *= int64(2) ans %= int64(MOD) } } } fmt.Println(ans) }
これまた途中でバグを生んでしまったり、ものすごく時間を使ってしまった。
何気なく i, j をイテレータとして使うにしても、列方向は j で固定するなど、
こういった部分で混乱を減らし、極力バグを生みにくくなるように工夫していきたい。
C. Primes and Multiplication
問題
※これも長いので省略
与えられた定義のもとで f(x, 1) * f(x, 2) * ... * f(x, n) % (10^9+7) を求めよ。
制約: 2 <= x <= 10^9, 1 <= n <= 10^18
解答
自分の解答が非常に説明しづらいので、大部分を図示する。
素直に定義式に従って与えられた式を分解していくと、たくさんの g(?, ?) の積を計算することになる。
特に n が非常に大きく、これをまともに全部計算するわけには行かないので、図示した赤枠の縦方向について効率的に計算できないか考える。
求め方は図中の文章通りで、説明の都合上ところどころ一般化して文字式で置いたりしているが、
コンテスト中は適宜適当な数値を当てはめて考えるとわかりやすいと思う（「例示は理解の試金石」*1）。
指数の計算をする部分は、指数部が大きすぎるので二分累乗法が必要。 逆元のスニペットを作るときに同時に作ることになると思うので、一緒に揃えておきたい。
var x, n int64 func main() { x, n = ReadInt64_2() primes := TrialDivision(int(x)) ans := int64(1) for p := range primes { prod := int64(1) for { if isOverflow(prod, int64(p)) { break } prod *= int64(p) if n < prod { break } num := int64(n / prod) tmp := modpow(int64(p), num, MOD) ans *= tmp ans %= MOD } } fmt.Println(ans % MOD) } func isOverflow(i, j int64) bool { return !(i < math.MaxInt64/j) } func modpow(a, e, m int64) int64 { if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := modpow(a, halfE, m) return half * half % m } return a * modpow(a, e-1, m) % m } // TrialDivision returns the result of prime factorization of integer N. func TrialDivision(n int) map[int]int { if n <= 1 { panic(errors.New("[argument error]: TrialDivision only accepts a NATURAL number")) } p := map[int]int{} for i := 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 }
上記のコードでオーバーフローチェックをしていますが、本番中に40分かけてもこれに気づけませんでした。。
初歩的とはいえ、このようなつまり方をしたのは初めてだったので、早い段階で自分の中の地雷処理ができたとポジティブに考えておきます。。
感想
百歩譲って未経験のタイプのオーバーフローを解決できなかったのはともかく、 A，Bの実装が遅すぎたのも問題でした。
競技プログラミングの筋トレが全く足りていないので、引き続きCodeforcesで鍛えていきたいと思います。
Codeforces Round No.588 (Div.2) 参加記録（A〜D解答）
初めてCodeforcesに参加しました。
CodeforcesはAtCoderほど日本語の記事が見当たらなかったので、そのあたりモチベーションにしつつブログの練習も兼ねて参加録をつけていこうと思います。
- 全体
- A. Dawid and Bags of Candies
- B. Ania and Minimizing
- C. Anadi and Domino
- D. Marcin and Training Camp
- 感想
全体
A, Bの2完でRate 1511スタートでした。 こちらも青色を目指して頑張っていこうと思います。
Cはpretestは通りましたが、ちゃんと全探索しておらずsystem testで撃沈しました。 Dもぱっと浮かんだ解法を後日実装したところ、撃沈していたので、この2問を重点的に復習していきます。
A. Dawid and Bags of Candies
問題
Dawidはキャンディの入った4つの袋を持っている。
i 番目の袋は A[i] 個のキャンディを含んでいる。
Dawidはこれらの袋を二人の友人のいずれかにそれぞれ配る（必ず配らなければならず、自身が保持してはいけない）。
二人の友人に同じ数のアメを配ることは可能か判定せよ。
制約: 1 <= A[i] <= 100
解答
それぞれの袋の配り方を全探索したいと考えた。
袋はどちらか一方に所属することになるので、ビット全探索を書いた。
var A []int func main() { A = ReadIntSlice(4) for i := 0; i < (1 << uint(4)); i++ { one, two := 0, 0 for j := 0; j < 4; j++ { if NthBit(i, j) == 1 { one += A[j] } else { two += A[j] } } if one == two { fmt.Println("YES") return } } fmt.Println("NO") }
B. Ania and Minimizing
問題
Aniaは大きな整数 S を持っている。
この S は、10進数表現で n 桁となる（上位桁の桁埋めのための0（leading zeroes）はない）。
Aniaは最大で k 個の桁を変えることができる（ただし、leading zeroesを作ってはいけない）。
Aniaができるだけ小さい数を作ろうとするとき、その値は何になるか答えよ。
制約: 1 <= n <= 200000, 0 <= k <= n
解答
S がとても大きいので文字列のまま処理する方針で考える。
気持ちとしては上位桁を小さくするほうが得なので、上の桁から0にしていきたいが、条件から「最上位桁を0とするのはご法度」となる。
なので、最上位桁は泣く泣く1とし、それ以降を可能なだけ0で置き換えていくことにする。
シミュレーションする際は、変える必要のない桁を変えて k を無駄に減らしてしまったり、ループを抜けるところを間違えて変える桁の過不足が発生しないように注意した。
var n, k int var S []rune func main() { n, k = ReadInt2() S = ReadRuneSlice() if k == 0 { fmt.Println(string(S)) return } if n == 1 { S[0] = '0' k-- } else { if S[0] != '1' { S[0] = '1' k-- } } if k == 0 { fmt.Println(string(S)) return } // この時点で k > 0 for i := 1; i < n; i++ { if S[i] != '0' { S[i] = '0' k-- } if k == 0 { break } } fmt.Println(string(S)) }
leading zeroes というのはあまり馴染みがなかったので覚えておきたいところ。
C. Anadi and Domino
問題
Anadiはドミノの1セットを持っている。 それぞれのドミノは、両サイドに1から6のサイコロの面が描かれており、それぞれの種類について1ピースあるため、全部で21個のドミノがある。
※URLの画像が親切なので詳しくはそちらをご参照ください。
また、Anadiは自己ループ・多重辺の無い無向グラフを持っており、そのグラフの辺にドミノを置こうとしている。 ドミノを置く際のルールは以下のようになっている。
- ドミノの両サイドが、辺を結ぶノードを向くようにする。
- 複数のドミノがあるノードを指すように置かれる場合、そのノードが刺されるドミノの数字は等しくなければならない。
Anadiは最大で何個のドミノを置けるか答えよ。
制約: 1 <= n <= 7, 1 <= m <= n*(n-1)/2 （それぞれノード、辺の数）
解答
よくわからないまま、サンプル4のノード数7の完全グラフのケースについて、色々とお絵かきをしながら考えた。
考えるうちに、ノードが6個以下の場合は、すべての辺に対してなんらかのドミノが置けることがわかった（1からnの番号を素直にノードに振ってやった後、その番号に向くようにドミノを選んで置いていけば良い）。
なので、 n <= 6 のケースでは m をそのまま出力すれば良い。
ノード数が7のときだけは、2つのノードは互いにドミノの数字をかぶらせる必要が出てくる。
ここで、ドミノの数字をかぶらせるノードペアが同じであれば、それぞれのノードに向けるドミノの数字のパターンが変わろうとも、置けるドミノの数は変わらない、事がわかる （使うドミノが数字に合わせて変わるだけで、使いたいドミノがセットの中にない、ということは起こらない。）
なので、ノード数が7の場合は、「ドミノの数をかぶらせるノードのペアの選び方」を全探索する。
ノード間の辺の有無や、ある種類のドミノの使用済みかどうかの判断はそれぞれともに行列を利用して行っている。
var n, m int var adjMatrix [10][10]int var dominoMatrix [10][10]int func main() { n, m = ReadInt2() for i := 0; i < m; i++ { a, b := ReadInt2() // 常にaをbより小さくする if a > b { a, b = b, a } adjMatrix[a][b] = 1 adjMatrix[b][a] = 1 } if n <= 6 { fmt.Println(m) } else { fmt.Println(sub()) } } func sub() int { res := 0 // i, jを同じ数字とする for i := 1; i <= n; i++ { for j := i + 1; j <= n; j++ { // ノードにサイコロの目を割り振る memo := make(map[int]int) dice := 1 for k := 1; k <= n; k++ { if k == j { continue } memo[k] = dice dice++ } memo[j] = memo[i] tmp := 0 initialize() for l := 1; l <= n; l++ { for m := l + 1; m <= n; m++ { ll, mm := memo[l], memo[m] if ll > mm { ll, mm = mm, ll } if adjMatrix[l][m] == 1 && dominoMatrix[ll][mm] == 1 { tmp++ dominoMatrix[ll][mm] = 0 } } } ChMax(&res, tmp) } } return res } func initialize() { for i := 1; i <= 6; i++ { dominoMatrix[i][i] = 1 for j := i + 1; j <= 6; j++ { dominoMatrix[i][j] = 1 } } }
コンテスト中は、「数字をかぶらせる必要のあるノード番号を7とし、 7を割り当てるノードを全部調べる」というようなことを考えていたら、 見るからにバグりそうなコードが出来上がってしまった（実際にsystem testで撃沈した）。
ヤバそうなコードを書いているときは、たいてい予想通りどこかでひっかかるので、 コンテスト中も途中で考えを捨てる勇気を持ちたい。
とはいえ、改めて整理して書いてみても、それなりに複雑なコードになってしまった。
ごちゃごちゃ考えずに、n の値によらずに全探索する方法もあるらしい。
そちらのほうが確実そうな一方で、実装方法がよくわかっていない（のでどなたか教えて下さい）。
全探索による別解（2019-10-06追記）
この記事を読んでくださったくるさんから、 全探索のコードを提供していただいたので、Goで書き直してみました（くるさんありがとうございます。。！呟いてみるもんですね）。
頂点数が7のときが〜とかかぶらせる数字は2個まで〜とか、そんな面倒な採番を考えなくても、 1〜6まで重複順列で全パターン洗い出してしまえばいいじゃないか、という解法です。
6^7*21 = 5878656 なので問題なく間に合いますね。
重複順列はスニペットにしているので、せっかくなので久しぶりにそれを使って書いてみました。 シンプルでバグらせようがなくてベストな解法だと思いました。
var n, m int var edges []Edge type Edge struct { s, t int } func main() { n, m = ReadInt2() for i := 0; i < m; i++ { s, t := ReadInt2() s-- t-- edges = append(edges, Edge{s, t}) } ans := 0 patterns := DuplicatePatterns([]int{0, 1, 2, 3, 4, 5}, n) for _, p := range patterns { A := [6][6]int{} for i := 0; i < 6; i++ { for j := 0; j < 6; j++ { A[i][j] = 1 } } cnt := 0 for _, e := range edges { l, r := p[e.s], p[e.t] if A[l][r] == 1 { A[l][r], A[r][l] = 0, 0 cnt++ } } ChMax(&ans, cnt) } fmt.Println(ans) } // DuplicatePatterns returns all patterns of n^k of elems([]int). func DuplicatePatterns(elems []int, k int) [][]int { return dupliRec([]int{}, elems, k) } // DFS function for DuplicatePatterns. func dupliRec(pattern, elems []int, k int) [][]int { if len(pattern) == k { return [][]int{pattern} } res := [][]int{} for _, e := range elems { newPattern := make([]int, len(pattern)) copy(newPattern, pattern) newPattern = append(newPattern, e) res = append(res, dupliRec(newPattern, elems, k)...) } return res }
D. Marcin and Training Camp
問題
Marcinは大学の講師で、n人の合宿に参加したい生徒を抱えている。 Marcinは、互いにcalmlyに共同作業できる生徒たちを送ろうとしているとしている。
生徒たちは1からn番の番号が振られており、それぞれ A[i], B[i] で特徴づけられている。
A[i]: このビット表現は、0から59のアルゴリズムを、i番目の生徒が知っているかどうかを示している（1ならば知っている）。B[i]:i番目の生徒のスキルの高さを示している（高ければ高いほどよい）。
生徒たちは、「あるアルゴリズムについて、自分は知っているが相手は知らない」というようなアルゴリズムが1つでもある場合に、相手のことを見下す。 2人以上のグループを組んだとき、相手のことを見下す生徒が一人もいない場合に、そのグループはcalmlyに共同作業できる。
共同作業できるグループを作る際、そのグループを構成する生徒のスキルレベルの和を最大化する場合、スキルレベルの和はいくらになるか答えよ。
解答
グリーディに考える。
グループが作れる条件を、「少なくとも1組のペアが、互いに知っているアルゴリズムの集合が同じで、互いを対等だと思っている」ことだと考える。
そこで、まずは対等な人同士でグループを作ってしまう。 対等な人のグループは、Aでソートすれば見つかる。
また、この対等な人たちでのみ構成されるグループに対して、まだグループが組めていない生徒を組み込んでいくことを考える。 具体的には、グループを表すビット集合と、ある生徒のビット集合のビットOR演算をとり、ビット集合がグループのビット集合のままであれば、 その生徒はグループに組み込むことができる。 逆に、グループのビット集合が変化してしまう場合、その生徒はそのグループの人全員を見下してしまうため、そのグループには組み込めない。
最後に、出来上がった全てのグループを併合しても問題ないため、グループに所属している生徒のスキルレベルの和を計算する。
和を計算するときは、32ビット整数の範囲を超えてしまうことに注意。
ソート部分の計算量が O(n * log(n)) で、対等な人たちのグループに残った人の組み込みを考える部分の計算量が O(n^2) となる。
var n int var A []int64 var B []int type Student struct { key int64 a int64 b int idx int } type StudentList []*Student type byKey struct { StudentList } func (l StudentList) Len() int { return len(l) } func (l StudentList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } func (l byKey) Less(i, j int) bool { return l.StudentList[i].key < l.StudentList[j].key } var flags []bool func main() { n = ReadInt() A = ReadInt64Slice(n) B = ReadIntSlice(n) flags = make([]bool, n) if n == 1 { fmt.Println(0) return } L := make(StudentList, 0, 200000) for i := 0; i < n; i++ { L = append(L, &Student{key: A[i], a: A[i], b: B[i], idx: i}) } sort.Stable(byKey{L}) // 2以上のサイズのメモ memo := make(map[int64]int) for i := 0; i < len(L); i++ { if i == 0 { if L[i].a == L[i+1].a { memo[L[i].a] = 1 } } else if i == len(L)-1 { if L[i-1].a == L[i].a { memo[L[i].a] = 1 } } else { if L[i-1].a == L[i].a || L[i].a == L[i+1].a { memo[L[i].a] = 1 } } } for bits := range memo { for i := 0; i < n; i++ { if bits|A[i] == bits { flags[i] = true } } } sum := int64(0) for i := 0; i < n; i++ { if flags[i] { sum += int64(B[i]) } } fmt.Println(sum) }
対等な人たちのグループを併合してから、そのグループのアルゴリズムセットが包含するような生徒を取り込む、というようにすると誤りになる （もとの個々のグループの人全員を見下してしまう生徒を組み込んでしまう場合がある）。
やむを得ず貪欲法を選択することになった場合は、ちゃんと整理しきってから提出したい。
これもどうやら全探索的なやり方があるらしいので、コンテスト中はできる限りそういったものが選択できるようにしたい。
感想
細かい部分でなれない実装が要求される感じがあり、本質的でない部分で消耗してしまった気がします。 最近のABCのE問題以降では、これぐらいの実装が要求されるものも少なくないように感じるため、慣れていきたいところです。
また、無証明の貪欲は危険だということも体験できたので、証明をスムーズにできる訓練もしていきたいと思います。
