ABC に参加して、E完でした。

AtCoder Beginner Contest 141

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #63 Second Sum | ABC 140
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc141/tasks

A - Weather Prediction

問題概要: 天気は Sunny, Cloudy, Rainy の順で周期的に変化する。今日の天気 S が与えられる。明日の天気を求めよ。

A: 考察

「周期的に変化する」を実装できる形に言い換えられればOKです。言い換えは複数あります:

「Sunny の次は Cloudy であり、Cloudy の次は Rainy であり、Rainy の次は Sunny である」 (分かりやすい)
「Sunny, Cloudy, Rainy のうち今日が i 番目なら明日は (i+1) % 3 番目である」 (文字列を2回ずつ書かなくていい)
「Sunny, Cloudy, Rainy, Sunny のうち今日が i 番目なら明日は (i+1) 番目である」 (剰余をとらなくていい)
「Sunny, Cloudy, Rainy の繰り返しの前方から今日の天気でないものを除外したものの前から2番目」 (メソッドチェインで書ける)
など

3番目を選びました。いま思うと1つ目でよかった。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc141/submissions/7523239

ちなみに4つ目はこれ:

    ["Sunny", "Cloudy", "Rainy"]
        .iter()
        .cycle()
        .skip_while(|&&s| s != S)
        .nth(1)
        .unwrap()

B - Tap Dance

問題概要: L, R, U, D のいずれかの文字からなる文字列 S が与えられる。条件「S の奇数文字目がすべて RUD のどれかである」と「S の偶数文字目がすべて LUD のどれかである」の両方が成り立つかを判定せよ。

B: 考察

いわれた通りに実装する問題です。「RUD のどれかである」を「L でない」と言いかえると少し短く書けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc141/submissions/7520351

C - Attack Survival

問題概要: 大会の参加者が N 人いる。はじめ、どの参加者も K ポイントを持っている。Q 個の問題が出題されて、q 番目の問題には A(q) 番目の参加者が正解した。ある参加者が正解すると、他の各参加者のポイントが1ずつ減る。各参加者につき、最終的なポイントが 0 より大きいか否かを判定せよ。

C: 考察

参加者のポイントを配列に入れて、各問題につき正解者以外のポイントを1ずつ減らす、というループを書くと計算できますが、全体で O(N^2) 時間かかって間に合いません。

正解者以外のポイントを1ずつ減らすのは N-1 回もの処理が必要で、遅いです。代わりに、正解者のポイントを1増やしてから、全体のポイントを1減らすことを考えます。「全体のポイントを減らす」を最後にまとめて行うことにすると、問題1つあたり O(1) 時間で処理できるので、全体として O(N) 時間で処理できて高速です。

具体的にいうと、「参加者のポイントが入った配列」と「全体のポイントの減少」という2つの変数を持っておきます。各問題につき、正解者のポイント増加は前者に反映し、全体のポイント減少は後者に反映します。最後に、「全体のポイント減少」を前者の配列に反映させます。これで参加者のポイントを計算できます。

もう少し考えると、「全体のポイント減少」は最後に -Q になるのが分かります。そのため、参加者のポイントが元から K-Q だったことにして、各問題につき正解者のポイントを1増やす、という操作でもOKです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc141/submissions/7518118

D - Powerful Discount Tickets

問題概要: N 個の品物がある。i 番目の品物は A(i) 円で購入できる。いま M 枚の割引券を持っている。X 円の品物を購入するとき、Y 枚の割引券を使うと、代わりに floor(X/2^Y) 円で購入できる。すべての品物を1つずつ購入するとき、購入金額の総和の最小値を求めよ。

制約: N≤10^5, M≤10^5

D: 考察

例えば A=(2, 3, 5, 8), M=3 なら A(3)=5 に1枚、A(4)=8 に2枚の割引券を使ったときの 2 + 3 + 5/2 + 8/4 が最小です。

直感的には最高額の品物に割引券を使うのがベストです。

割引券1枚を A(i) に使うと決めたとき、その商品の価格が元から A(i)/2 だったことにして残りの処理をしてかまいません。

したがって、イメージとしては以下の繰り返しで計算できそうです。

M=0 なら A の合計を出して終わり
最高額の品物 A(i) をみつける
A(i) → A(i)/2, M → M-1 に置き換える
はじめにもどる

最高額の品物の検索に線形探索を使うと全体で O(N^2) になり間に合いません。

「最大値を見つける」検索が高速なデータ構造の1つにヒープ (優先度つきキュー) std::collections::BinaryHeap があります。これを使うと、検索と更新が O(log N) になり、全体で O(N log N) 時間に高速化します。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc141/submissions/7524807

E - Who Says a Pun?

問題概要: 長さ N の文字列 S が与えられます。空でない文字列 T であって、S に部分列として重複なく2回出現するものが存在するか判定し、存在するなら最大の長さを求めよ。

制約: N≤5×10^3

E: 考察

例えば ababa には ab が2回、重複なく出現するので T=ab が最長です。T=aba は中央の a が重複するのでダメ。

Z アルゴリズムを使うと、T が S の先頭に出現するケースでの最大長を O(N) 時間で求められます。T が S に出現しないケースは、S[i..] に Z アルゴリズムを適用すればよいです。i は全探索して、全体として O(N^2) 時間で解けます。

筆者の回答 (Rust, AC):https://atcoder.jp/contests/abc141/submissions/7528446

Z アルゴリズムは一種の DP です。解説 (英語):

Z Algorithm - Codeforces

(F を書くのに疲れたので丸投げ)

F - Xor Sum 3

問題概要: N 個の整数が与えられる。i 番目の整数は A(i) である。これらの整数のうちいくつかを赤に、残りを青に塗る。ただし、すべてを赤に塗ることはできない。「赤に塗ったすべての整数の XOR」と「青に塗ったすべての整数の XOR」の和の最大値を求めよ。

制約: N≤10^5, A(i) < 2^60

F: 考察

XOR はビットごとに見るという定跡があるので、1ビットのケースを考えます。

このケースは以下の３通りがあります。

1 が出現しない (すべて 0)
- 最大値は 0 です
1 が奇数回出現する
- 1 を奇数 + 偶数にしか分けられず、偶数側の XOR は 0 になるため、最大値は 1 になります
1 が偶数回 (2回以上) 出現する
- 1 を奇数 + 奇数に分ければ両色の XOR が 1 になるので、最大値を 2 にできます

奇数回出現するビット (そのビットが立っている A(i) が奇数個あるようなビット) は、整数をどのように分けても赤か青の一方だけに立ちます。そのため、A(i) からそのビットを落としておき、最後にまとめて足すことにしてよいです。

そうすると、どのビットも偶数回 (または0回) 出現するようになります。A(i) 全体の XOR は 0 です。「赤に塗ったすべての整数の XOR」と「青に塗ったすべての整数の XOR」は等しくなります。

    (A を適当に並び替えて前からいくつかを赤、残りを青に塗るとき)

    A(1) ^ A(2) ^ ... ^ A(N) = 0
    ~~~~~~~~~~~   ~~~~~~~~~~
         X            Y

    X ^ Y = 0 ⇔ X = Y

結局、残る問題は「整数のいくつかを選んで XOR を最大にすること」です。部分集合の XOR を最大化するという単純な問題は、間違いなくすでに誰かが解いているので、インターネット検索によりアルゴリズムが見つかることが予想できます。

subset xor maximize - Qwant Search (検索エンジン Qwant による検索結果)
Find the maximum subset XOR of a given set - GeeksforGeeks (それっぽいアルゴリズムが書かれているページ)

上記のアルゴリズムと解説をよく読むと正しいことが分かるので、Rust で実装すればOKです。読んでたらコンテストが終わってましたが……

提出 (Rust, AC): https://atcoder.jp/contests/abc141/submissions/7545579

さて、XOR は上位のビットを立てられるなら立てるのが最善です。先に最終目標をいうと、A を変形して「あるビットを立てている数が最大1個だけ」になるようにしたいです。これらの整数の XOR が「A からいくつかの整数を選んで XOR を取ったもの」の最大値になるように、うまく変形します。例 (入力例2):

具体的な手順としては、以下の条件を維持しながら、変数 index, k を最後まで進めることを考えます。

0 ≤ index ≤ N (位置)
0 ≤ k ≤ 60 (ビット数)
条件1: 上位 k ビットの各ビットにつき、そのビットが立っている整数は最大1個だけ
条件2: A の前から index 個の整数は、上位 k ビットのいずれかが 1
条件3: A の前から index 個の整数以外は、上位 k ビットがすべて 0

処理の途中の状態をみてみましょう:

k=6, index=2

このビットは1が重ならない
vvvv vv
0100 0010 <
0000 0111 < この2つは上位ビットを持つ
0000 0011
0000 0011

次に上から k+1 番目の重複を除くことを考えます。前から index+1 番目以降の要素のうち k+1 番目のビットがないか、1つしかないならそれでいいです。そうでなければ、適当に1つ (ここでは最大値) 選びます。

k+1 番目のビットを持つ他の要素にここで選んだ要素を XOR する (A[i] ^= A[j] とする) ことで、このビットを消します。このとき、条件3のおかげで上位ビットは変化しません。

選んだ整数を index+1 番目に移動させると、k, index をそれぞれ1増やしても条件が維持されることになり、残りの部分も処理できます。

最終的に変更後の A に含まれるすべての整数の XOR をとったものが、変更前の A からいくつかの要素を選んで XOR をとったものの最大値になります。

もしかしたら「こんな操作をすると A の XOR は全く無関係な値になってしまうのではないか」と疑うかもしれません。

途中で行なった A[i] ^= A[j] の形の変更操作をまとめて考えると、A[i] → A[i] ^ A[j] のように各要素は他のいくつかの要素との XOR に変化します。

変更後の A のすべての XOR をとると、変更前の A の各要素が1回以上出現するような式になります。ここに偶数回出現する要素は対消滅し、奇数回出現するものは1つだけ残ります。全体としては「変更前の A からいくつかの要素を選んだ XOR」に相当するわけです。