競プロ参戦記 第22回 「最大の論理積」 / ドワンゴコン5 [ABC]
ドワンゴ主催のプログラミングコンテストに参加しました。B完でした。Cまで考察を書いていきます。
第5回 ドワンゴからの挑戦状 予選
問題一覧：
A - Thumbnail
問題概要：数列 A が与えられる。平均値にもっとも近い最初の要素を求めよ。
考察：実際に平均値を求めて、平均値との差が最小である要素を線型探索すればOK。
「平均値との差が最小である要素の線型探索」は 前回の記事のB問題の考察 で詳細に書いたので参考にしてください。
B - Sum AND Subarrays
問題概要：数列 A が与えられる。数列の連続部分列を K 個選び、総和の論理積を最大化せよ。
考察： N ≤ 1000 なので部分列の総和は全列挙できます。
総和の論理積の最大値について考えます。論理積をとることで値は大きくならないので、なるべく大きい値を選ぶべきです。つまり、なるべく高いビットを持つ K 個の総和を選べたら最適です。これは貪欲法でできます。
i は 64 から 0 まで動くとし、いま総和をいくつか選んだとします (最初は全部の総和を選んだ状態から始める)。最終的な論理積に「i 番目のビット」を立たせるには、いま選んでいる総和の中に「i 番目のビットが立っているもの」が K 個以上あればよいです。
もしあれば、それらの総和を選んで再帰的に進めば最適になります。というのも、下位ビットを立たせるために i 番目のビットを諦めるという選択は誤りだからです。
C - k-DMC
問題概要：文字列 S が与えられる。 D, M, C と並んでいる部分のうち、D と C の距離が k 以下であるものを数えよ。
考察： **解けませんでした。**
問題の考えかたとして《似た問題はないか》《条件を減らしたらどうなるか》というのを考えていました。以前、似た問題をやったことがあって、それはたしか k に関する条件がないものでした。
もし k に関する条件がなければ、つまり k = |S| なら、 M の位置を全列挙しつつ、その左側にある D の個数と C の個数を掛け合わせていく、という数え方ができます。
一方 k = 3 なら普通の文字列検索なので、線型探索して DMC の並びが出現する位置を数えればいいです。
k = 4 のときは /D.MC/ か /DM.C/ を探すことになります。k = 5 でも同様に /D(..M|.M.|M..)C/ です。
このことから、d を 3 から k まで動かして、 D-C の幅がちょうど d である (D, M, C) 組を探す、という案が出てきます。これは文字列のある範囲に出現する M の個数を累積和でもっておけば、 D-C の間にある M の個数を O(1) で数えられるので、全体として O(N^2) です。 **TLE**
もう1つの案は、 k = |N| で数えてから条件にそぐわないものを引いていく、つまり D-C 間の距離が k **以上** であるものを数える、という手法です。このあたりを考えている間に時間切れになりました。わりとダメそう。
追記：解説生放送を聞いてACしました。半分受け売りですが改めて考察を書きます。
考察：
1回の入力で複数の k が与えられますが、個数が 75 と少ないので計算量への影響は無視できます。それぞれ独立に処理します。
文字 C を基準に DMC の組み合わせを数えることにします。つまり、文字列中に出現する文字 C をすべて調べて、それを使ってできる DMC の組み合わせの個数を高速に計算する、という手法です。
やや天下り的ですが、文字列上の区間を考えます。この区間内の DMC の組み合わせに注目します。区間が持つ情報を状態として持っておき、区間の変動 (伸び縮み) に応じてそれらの情報も適切に更新することにします。
区間が持つ状態とは、その区間に含まれる文字 D の個数と、文字 M の個数、それから DM の組み合わせの個数です。
はじめ、区間は位置 0、幅 0 で、これを幅 k になるまで伸ばしていきます。区間に要素を足すときの状態の更新は次のようにします。
加わったのが 'D' なら「D の個数」を増やし、 'M' なら「M の個数」を増やす、というのはもちろんです。
ここで、 'M' が加わったら **「DM の個数」は「D の個数」だけ増えます** 。たしかに。
また、加わったが 'C' だったら「DM の個数」だけ「DMC の個数」を増やします。
さて、もし区間幅が k を超えたら、不正な DMC の組み合わせを数えてしまうことになります。そうならないように、幅 k の区間を伸ばした後は、先頭の要素を取り除いて縮めます。しゃくとり法のように。
ここでの状態更新は上記の逆をします。'D' が消えたときに「DM の個数」が「M の個数」だけ減るわけです。
この記事が気に入ったらサポートをしてみませんか？