実装の練習
問題と解答メモ
A (500)
【問題】数直線上の3つの点の座標 a,b,c と距離 d が与えられる。どの座標間の距離も d 以上になるように点を動かしたい。移動距離の最短は？
座標をソートして隣り合う 2 点の距離が d 以上になるようにすればよい。かんたん。
B (1200)
【問題】文字列のペアが n 個ある。各ペア (S,T) について、Sの各文字を何個かに複製して ( h を hh や hhh などににできる) T にできるかを判定せよ。n<=1e5, sum of length<=1e6.
たとえば hello を h1e1l2o1 などと管理する。そのうえで「同じ場所の文字が一緒かつTの方が数値が大きい」、というのが同値条件。よくみる管理の仕方を思い出せばできた。なんか名前あったけど忘れちゃった。
C1 (1200) & C2 (1700)
【問題】長さ n の数列 (a[i]) と数 M がある。添え字 i について、i-1 番目以下の要素いくつかを消して i 番目までの和を M 以下にしたい。消す個数の最小値を、すべての i について求めよ。消し方は i について独立に行う。a[i]<=100, n<=2e5 (easy ver. はn<=100).
easy ver. は愚直にソートして計算すればできそう。O(n^2 log n).
hard ver. は、a[i] がそんなに大きくないことを利用し、a[i]=k となる i の個数 ct[k] を管理して順に見ていくとよい。なるだけ要素を残すには、k の小さい方から追加していくとよい。これで O(n max(a[i])) でできるので間に合う。数字の制約があるときはカウント作戦が使えることがあるので忘れないこと。
D (1700)
【問題】長さ n の数列 a[i] がある。1 個捨てて並び替えて等差数列にしたい。それができるかどうか判定し、できるならそのために取り除く要素の index を出力せよ。n<=2e5.
あらかじめソートしておき、差を取る。1 個除いて等差数列にできるなら、差の列がだいたい同じで少し違う。端 1 個が違うならそこを捨てればよい。隣り合う二つが異なり、その和が他と一緒なら、そこを捨てればよい。他はできない。
パターンをちゃんとつぶしながら、正確に実装しよう。めんどうだけどやることはわかりやすい。先に n<=3 を捨てておくと楽。
E (2000)
【問題】盤面に a, b, c, ... と名前のついた「へび」を順に置いていく。「へび」は幅 1 の長方形で、26匹まで置ける。また、重ねて置いていくので、下になったものは見えなくなる。さて、盤面が n 個ある。各盤面は英小文字と "." で表されている。これが「へび」を置いたあとの盤面になるかどうか判定し、できるなら置き方 (頭と尾の座標) を指定せよ。盤面のタテヨコは 2e3 以下で、面積の総和は 4e6 以下。
ヘビとしてありうるかは、何もないか (=隠れた)、行だけみて1か所だけ存在するか、列だけみて1か所だけ存在するか。そのうえで、始点から終点まで自分以上の文字で途切れなく続いている必要がある。盤面の各行各列で、各文字が存在するかの bool 配列を持っておき、上の判定をしていくとよい。できる。けど面倒。
F (2200)
【問題】n 人と m 枚のピザがある。ピザにはトッピングが 9 種類あり、n 人それぞれが好きな具材のリストを持っている。またピザにのっているトッピングのリストと値段が与えられる。m 枚の内 2 枚ピザを買う。各人は、ピザ 2 枚合わせて好きなトッピングすべてがのっていれば喜ぶ。喜ぶ人数を最大化したい。その上で値段を最小化したい。どのピザを買えばよいか出力せよ。n, m <= 1e5.
トッピングがあるかどうかは bit で管理するとよい。すると取るピザを固定すれば、各人が好むかが bit 演算で判定できる。これで O(n^2 m) でできるが足りない。実はトッピングの選び方は 512 通りしかないので、トッピングごとに集計すれば同様の全探索で O(512^3) でできる。判定をbit 演算で行うので定数倍が小さく、これで間に合う。
トッピングの管理を bit で行うのを思いつけば解けそう。というか当たり前といえば当たり前なので、思いつくというよりは息をするように実装したい。実装は面倒だけど...
G1 (2100) & G2 (2800)
【問題】曲が n 個ある。各曲 i には長さ t[i] とジャンル g[i] が定まっている (ジャンルは 3 種類)。これを使って長さがちょうど T 分のプレイリストを作りたい。ただし同じ曲は 1 回までしか使わず、同じジャンルが隣り合わないようにしたい。そのようなプレイリストの個数 (の mod 1e9+7) を求めよ。制約は n,t[i]<=15 (resp. 50), T<=225 (resp. 2500).
easy ver. は全探索方針で倒せそう。ジャンル i の個数が c[i] であるような曲の選び方に対し、ジャンルが隣り合わないような並べ方の総数が DP で求まる。なので曲すべての選び方に対し、時間の和が T になるかチェックし、T になればジャンルの個数に応じて事前にもとめた DP の値を加算すればよい。これで O(2^n+n^3) でできる。
hard ver. は解けなかった... ナップサックっぽい作戦でいくのかなと思ったけどうまく求まらず。解説を読んで考える。
作戦としては、うまく fix した上でナップサックっぽいDP。ジャンルは 0-indexed とする。各曲の個数 c[i] と長さ l[i] を fix すると、上の DP の値で並べ方が決まる。なので各ジャンルで曲の個数と長さについて選び方をナップサックっぽいDPで出して、(各ジャンルの選び方)*(並べ方) を計算し、l[0]+l[1]+l[2] = T および c[i] < n なる組合せすべてについて足すとよい。しかしこれだと足すときに定数は小さいながら O(n^3 * T^2) かかる。
そこで解説では 1, 2 をまとめて計算していた。それにより O(n^3 * T) に減らせ、定数が小さいので間に合う、という寸法。アイデアをまとめると
・曲をジャンルごとにまとめ、計算しやすくする
・計算量を減らすためにさらにジャンルを併合する
というもの。前者はかなり自然なので慣れよう。後者は半分全探索とかに似てる気がするので、計算量を減らせることを覚えておこう。
全体的な感想
Atcoder と比べて、方針が分かりやすいが実装が少し面倒になってる感じ。でもこれくらいの実装なら苦にせず書きたいところ。方針が分かりやすい分、ストレスが軽減されて良い。コードを書く練習としては、こっちを埋めた方が (自分には) 向いてるかもなぁ。
