−目次

AtCoder Regular Contest 124 A,B,C,D,E問題メモ
- A - LR Constraints
  - 問題
  - 解法
- B - XOR Matching 2
  - 問題
  - 解法
- C - LCM of GCDs
  - 問題
  - 解法
- D - Yet Another Sorting Problem
  - 問題
  - 解法
- E - Pass to Next
  - 問題
  - 解法

AtCoder Regular Contest 124 A,B,C,D,E問題メモ

AtCoder Regular Contest 124

A - LR Constraints

問題

$N$ 枚のカードに $1～K$ の整数を書き込む（同じ数字を複数のカードに書き込んでもよい）
書き込み方に $K$ 個の制約が与えられる。 $i=1～K$ 番目の制約は、以下のいずれか一方の形をしている
- $i$ が書かれたカードのうち最も左にあるものは、 $N$ 枚のうち $k_i$ 番目
- $i$ が書かれたカードのうち最も右にあるものは、 $N$ 枚のうち $k_i$ 番目
制約を全て満たす書き込み方の個数を $\mod{998244353}$ で求めよ
$1 \le N,K \le 1000$

解法

まず全制約をチェックし、同じ位置に違う数字を書き込むような指示がある、つまり $k_i$ に重複があるような入力はアウト。
0を出力して終了。

以下、制約で指示された箇所は全て異なるとする。

$N$ が小さいので、「左から $i$ 番目に書き込める整数の種類は何通り？」というのを各カードについて求めてやる。

答えは、それを全て掛け合わせた数となる。

例えば制約1が「 $1$ が書かれたカードのうち最も左にあるものは $5$ 番目」だと、以下のようになる。

1～4番目のカードには“1”は書き込めない
5番目は“1”確定
6番目以降は1を書き込める

なので、 $N$ 要素の配列を用意して、5番目以降に全て +1 してやるとよい。

続いて制約2が「 $2$ が書かれたカードのうち最も右にあるものは $8$ 番目」だと、今度は8番目以前に全て +1 してやる。

N=10
[  0  0  0  0  0  0  0  0  0  0  ]

制約1の処理後  ↓
[  0  0  0  0  1  1  1  1  1  1  ]

制約2の処理後  ↓
[  1  1  1  1  2  2  2  2  1  1  ]

最後に、制約で指定された $K$ 箇所は配列の値にかかわらず書き込み方は1通りなので、1で上書きする。

[  1  1  1  1  1  2  2  1  1  1  ]

この配列の数字を全て掛け合わせればよい。

+1するところで最後に累積和を取るようにすれば、 $O(N)$ 。

Python3

B - XOR Matching 2

再帰で実装したらPythonで1ケースTLEになって、「PyPyは再帰遅いし、なおさらダメだろうなあ」なんて25分くらいまごついた後、ダメ元でPyPyで提出したら普通に通った。なんてこったい。

再帰がそんなに深くならないことがわかっているなら、PyPyでも臆せず試した方がいいね。

問題

非負整数のみからなる長さ $N$ の数列 $a=(a_1,a_2,...,a_N)$ と $b=(b_1,b_2,...,b_N)$
以下の条件を満たす非負整数 $x$ を「よい数」と呼ぶ
条件
- $b$ を並べ替えると全ての $i=1～N$ について $a_i \ \oplus \ b_i = x$ にできる
- （ $\oplus$ は排他的論理和）
よい数を小さい順に列挙せよ
$1 \le N \le 2000$
$0 \le a_i,b_i \lt 2^{30}$

解法

上のbitから順に処理して、再帰的に $a,b$ を分割していく。

$f(p,q,r)$ を、「数列 $p,q$ の場合のよい数の集合、ただし $x$ の（2進数で） $r$ 桁目より上については既に一意に求まっているので $r$ 桁目以下を確認する」とする。

$f(a,b,30)$ が答え。

まずは $p,q$ において $r$ 桁目（ $2^{r-1}$ ）のbitが立っている/立っていない整数を数える。

$p$ において、 $r$ 桁目が立っている整数を抜き出した数列を $p^1$
$p$ において、 $r$ 桁目が立っていない整数を抜き出した数列を $p^0$
$q$ において、 $r$ 桁目が立っている整数を抜き出した数列を $q^1$
$q$ において、 $r$ 桁目が立っていない整数を抜き出した数列を $q^0$

$x$ の $r$ 桁目を立てない場合、「 $p^1$ のどれかと $q^1$ のどれか」また「 $p^0$ のどれかと $q^0$ のどれか」をペアにする必要があるので、これらが同数である必要がある。

つまり、 $|p^1|=|q^1| \& |p^0|=|q^0|$ である必要がある（条件①）

条件を満たす場合、 $f(p,q,r)$ の結果は $f(p^1,q^1,r-1)$ と $f(p^0,q^0,r-1)$ の積集合（両方に入っている数）となる。
ただし、いずれかが空の場合は空でないもう一方だけの結果がそのまま結果となる。

$x$ の $r$ 桁目を立てる場合も似た感じで、「 $p^1$ のどれかと $q^0$ のどれか」また「 $p^0$ のどれかと $q^1$ のどれか」をペアにする必要があるので、これらが同数である必要がある。

つまり、 $|p^1|=|q^0| \& |p^0|=|q^1|$ である必要がある（条件②）

条件を満たす場合、 $f(p,q,r)$ の結果は $f(p^1,q^0,r-1)$ と $f(p^0,q^1,r-1)$ の積集合となる。
ただし、いずれかが空の場合は空でないもう一方だけの結果がそのまま結果となる。

条件①と②を両方満たす場合、組み合わせ方が2通りあるので、両方やった結果の和集合となる。

末端条件としては、以下の3通り（1つめは別に不要だが、計算量削減として）

$|p|=|q|=1$ の時、結果は $p_1 \oplus q_1$ のみからなる集合
$r=-1$ の時、 $p,q$ の要素は全て同じで、結果は $p_1 \oplus q_1$ のみからなる集合
条件①も②も満たさない場合、空集合

Python3

C - LCM of GCDs

問題

赤い袋と青い袋と $N$ 個のカードパックがあり、はじめどちらの袋も空
1つのカードパックには $2$ 枚のカードが封入されており、それぞれ整数 $a_i,b_i$ が書かれている
それぞれのカードパックについて、好きな方のカードを赤い袋に、他方を青い袋に入れる
全てのカードを袋に入れ終えた後、以下で得点を求める
- 赤い袋に入ったカードに書かれた整数全体の最大公約数を $X$ とする
- 青い袋に入ったカードに書かれた整数全体の最大公約数を $Y$ とする
- $X$ と $Y$ の最小公倍数を得点とする
得点の最大値を求めよ
$1 \le N \le 50$
$1 \le a_i,b_i \le 10^9$

解法

約数は少ないことを利用しての2乗全探索。

「赤い袋の最大公約数 $X$ 」「青い袋の最大公約数 $Y$ 」を決め打つ。
$X,Y$ の候補としては、それぞれ $a_1,b_1$ の約数に含まれる数としてよい。

$(X,Y)$ のペアを全通り試して、「 $a_i,b_i$ のうち一方が $X$ の倍数、他方が $Y$ の倍数」が全ての $i=1～N$ で成り立てば、得点 $lcm(X, Y)$ を得られることは確定する。

このような数の中で、最大値が答え。

なお、 $10^9$ 以下で約数の個数が最も多いのは $735134400=2^6 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17$ で、1344個。

それ以外の「 $N$ 以下で約数の個数が最も多い数」は、以下に高速な求め方が紹介されている。

高度合成数を高速に列挙する2つのアルゴリズム - Qiita

Python3

        
          
          
              
              from collections import defaultdict
from math import gcd
 
 
def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]
 
 
def prime_factorize(x, primes=None):
    """ xを素因数分解、辞書型で返す """
    # primes: sqrt(x)までの素数リスト
    #   省略時は奇数を試し割り（2だけ別処理）
    #   単発なら不要だが、複数のxで行う場合は事前計算した方がよい
 
    factors = defaultdict(int)
    if primes is None:
        if x & 1 == 0:
            b = (x & -x).bit_length() - 1
            factors[2] = b
            x >>= b
        primes = range(3, x, 2)
    for p in primes:
        if p * p > x:
            break
        if x % p == 0:
            factors[p] = 1
            x //= p
            while x % p == 0:
                factors[p] += 1
                x //= p
    if x != 1:
        factors[x] = 1
    return factors
 
 
def restore_divisors(prime_factorized):
    result = {1}
    for p, c in prime_factorized.items():
        new_result = set()
        for d in result:
            for i in range(c + 1):
                new_result.add(d * p ** i)
        result = new_result
    return result
 
 
n = int(input())
if n == 1:
    a, b = map(int, input().split())
    print(a * b)
    exit()
 
primes = get_primes(10 ** 5)
aaa = []
bbb = []
for i in range(n):
    a, b = map(int, input().split())
    aaa.append(a)
    bbb.append(b)
 
x_candidates = restore_divisors(prime_factorize(aaa[0], primes))
y_candidates = restore_divisors(prime_factorize(bbb[0], primes))
 
ans = 0
for x in x_candidates:
    for y in y_candidates:
        for a, b in zip(aaa, bbb):
            if a % x == 0 and b % y == 0:
                continue
            if a % y == 0 and b % x == 0:
                continue
            break
        else:
            ans = max(ans, x * y // gcd(x, y))
 
print(ans)

            

        
      

D - Yet Another Sorting Problem

問題

$(1,2,...,N+M)$ を並べ替えた順列 $p_1,p_2,...,p_{N+M}$ が与えられる
以下の操作を好きな回数行える
操作
- $p$ の先頭 $N$ 個から1つ、末尾 $M$ 個から1つを好きに選び、この2数をswapする
$p$ を昇順に並べ替えるために必要な最小の操作回数を求めよ
$1 \le N,M \le 10^5$

解法

まず、本問題のような制約のない、単なる順列を昇順に並べ替える操作手順の求め方を考える。

これは過去にも何度か出題されているが、以下で求められる。

$i→p_i→p_{p_i}→...$ と辿っていって $i$ に戻るまでを1つのループとする
このループの要素だけを正しい位置にするには、(ループサイズ-1) の操作回数が必要となる
全てのループに対しての合計が答え

今回の場合は、swapしたい2数がともに先頭 $N$ 個や末尾 $M$ 個に含まれると困る。

サンプル1
 N     M
      ②←┐
①  ／    │   ⑤→③や③→②が直接swapできない
  ↙  ⑤  │
④─↗↓  │
      ③─┘

このようなループ（連結成分）は、いくつかのパターンに分けられる。

理想型

まず、制約を気にしなくて済む「理想型」を定義する。

理想型とは、「ループサイズが偶数」「ループが $N$ 側と $M$ 側を交互に訪れる」形とする。

この場合、好きな位置でswapを開始して連鎖させていけば(ループサイズ-1)回で整列可能となる。
（下図のように線を引いた場合、→を遡るように連鎖させていく）

 N       M
③──→②
  ↖  ／
    ×
  ↙  ＼
④──→①

$N$ 側と $M$ 側をともに訪れる

同じ側を結ぶ辺がある場合、「その直前で、 $N$ 側と $M$ 側を結ぶ辺」からswapさせる。

すると、1個は正しい位置で固定され、後には「ループサイズが1個減り、同じ側を結ぶ辺の個数も1個減ったループ」が残る。

これを繰り返せば、いつかは理想型に落ち着く。

 N     M        ④→⑤をswap      ⑤→③をswap
      ②←┐            ②←┐            ②
①  ／    │  →  ①  ／    │  →  ①  ↗
  ↙  ⑤  │        ↙  ④  │        ↙  ④
④＿↗↓  │      ⑤        │      ③
      ③─┘        `-→③─┘            ⑤

1回毎に1つループサイズが減り、最終的に理想型になるので、この場合も操作回数は(ループサイズ-1)となる。

どちらか片方にしか訪れない

ループ内だけでは1手も操作できないので、訪れない側の適当な1頂点を媒介とする必要がある。

 N     M
      ④←┐
①    ↓  │
      ⑤  │
②    ↓  │
      ③─┘

試してみると、(ループサイズ+1) の操作回数が必要となる。

両側をペアにする

「片側しか訪れないループ」が両側に存在する場合、それらをペアとすることで、操作回数を減らせる。

両側から適当な1つずつをswapしてみると、

  N     M        ①と④をswap
       ④←┐        ↙~~①←┐
 ②    ↓  │  →  ②        │
↑↓   ⑤  │      ↓    ⑤  │
 ①    ↓  │      ④＿↗↓  │
       ③─┘            ③─┘

「ループが $N$ 側と $M$ 側をともに訪れる」場合にすることができる。

この場合の操作回数は、最初の1回を含めて(ループサイズ)回となる。両側を独立に整列する場合の(ループサイズ+2)回と比較して、2回分操作回数を減らせる。

従って、このようなペアは作れるだけ作るのが得となる。

Python3

E - Pass to Next

問題

$N$ 人がいて、各人ははじめ $a_1,a_2,...,a_N$ 個のボールを持っている
一度だけ、以下の操作を行う
- 各人が自分の持っているボールの範囲（ $0$ 以上 $a_i$ 以下）で整数 $c_i$ を1つ決める
- 一斉に、人 $i$ は $c_i$ 個のボールを人 $i+1$ に渡す
  - 人 $N$ は人 $1$ に渡す
操作後に各人が持っているボールの個数を数列 $x=(x_1,x_2,...,x_N)$ とする
$x$ としてあり得る数列全てについて、 $\displaystyle \prod_{i=1}^Nx_i$ を計算し、その総和を $\mod{998244353}$ で求めよ

解法

二項係数とか使った上手な発想の転換か？と思ったら、想定解法は多項式を切り崩しながら展開していくというなかなかの力業だった。

各 $x_i$ の取り得る範囲を直接的に求めるのは、お隣との関係も絡んでくるためややこしい。
各人が次に渡した個数 $c_i$ なら $0 \le c_i \le a_i$ で独立なので、なるべくこちらで考えたい。

$c=(c_1,c_2,...,c_N)$ の組合せは $(a_1+1)(a_2+1)...(a_N+1)$ 通り。

重複除外

$c$ を決めれば $x$ は一意に決まるが、逆は成り立たない。
$c$ が異なっても結果として出来る $x$ が同じになってしまう場合がある。
総和を取るのはあくまで「異なる $x$ 」に対してなので、あり得る $c$ 全てについて考えると重複が発生してしまう。

a  3 4 5    3 4 5
c  1 3 2    0 2 1
    ↓       ↓
x  4 2 6    4 2 6

たとえばある $c$ から $c_1$ を1増やしつつ $x$ を変えずに保とうとすると、連鎖的に全ての $c_i$ を1増やすしかないことがわかる。

逆に言うと、 $x$ が同じになる $c$ は、全ての項に同じ数を足したり引いたりしたもの同士、ということがわかる。

ならばこれ以上減らせない状態、つまり $0$ が少なくとも1つ含まれるような $c$ だけを考えれば、 $x$ は一意に決まる。

「①: $c_i$ が $0～a_i$ の範囲を取るケース」から「②: $c_i$ が $1～a_i$ の範囲を取るケース」を除けば、「少なくとも1つが $c_i=0$ のケース」のみが残り、それが答えとなる。

数式化

$c$ を固定したとき、 $x$ の総積を $c$ を使って書くと、以下のようになる。

$f(c)=(a_1-c_1+c_N)(a_2-c_2+c_1)(a_3-c_3+c_2)...(a_N-c_N+c_{N-1})$

この $c$ を全通り試して総和を取るので、答えは以下の式で表せる。前半が①で、後半が②に相当する。

$\displaystyle \sum_{c_1=0}^{a_1} \sum_{c_2=0}^{a_2} ... \sum_{c_N=0}^{a_N} f(c) - \sum_{c_1=1}^{a_1} \sum_{c_2=1}^{a_2} ... \sum_{c_N=1}^{a_N} f(c)$

Σを1つずつ外す

①について考える。

手が付けがたい形をしているが、実は各 $c_i$ が関係する項は2つずつしかない。
$c_1$ についてだけ着目して後は定数とみると、

$\displaystyle \sum_{c_1=0}^{a_1} (a_1-c_1+c_N)(a_2-c_2+c_1)(関係ない項)$

となる。

この形なら2次多項式の総和なので、自然数の累乗の和の公式を適用するなどすればΣを1個外すことが出来る。

つまり、 $a_1$ に実際の値を代入すると、以下のような式における係数 $p,q,r,s$ の具体的な値を求めることが出来る。

$((a_2-c_2)(p \cdot c_N + q) + (r \cdot c_N + s))(関係ない項)$

じゃあ、これを元に次に $c_2$ を変数とみなすと、

$\displaystyle \sum_{c_2=0}^{a_2} ((a_2-c_2)(p \cdot c_N + q)+(r \cdot c_N + s))(a_3-c_3+c_2)(関係ない項)$

少し複雑だがこれも $c_2$ に関する2次式であることに変わりは無いので $c_2$ のΣも外せ、 $c_3$ を同様の式で表せるようになる。

$((a_3-c_3)(p' \cdot c_N + q') + (r' \cdot c_N + s'))(関係ない項)$

$p',q',r',s'$ の値は、1つ前の $p,q,r,s$ と $a_i$ にのみ依存し、 $O(1)$ で計算できる。

これを $N-1$ 回繰り返していけば、（ $p,q,r,s$ は上書き更新していくとして）最終的に以下のような形になる。

$\displaystyle \sum_{c_N=0}^{a_N} (a_N-c_N)(p \cdot c_N + q)+(r \cdot c_N + s)$

これは今まで定数とみていた $c_N$ が変数となるためちょっと遷移が異なるが、それても2次式の総和で計算できるのは変わらない。これで、①のパターンの答えを $O(N)$ で計算できた。

②のパターンも遷移式は異なるが同様に計算できるので、①から引いてやれば答えとなる。

参考
- Collect[Sum[((a-i)*(p*K+q)+(r*K+s))(i+T),{i,0,a}], {T,K}] - Wolfram|Alpha
- Sum[(a-i)*(p*i+q)+(r*i+s),{i,0,a}] - Wolfram|Alpha

Python3

−目次

AtCoder Regular Contest 124 A,B,C,D,E問題メモ

A - LR Constraints

問題

解法

B - XOR Matching 2

問題

解法

C - LCM of GCDs

問題

解法

D - Yet Another Sorting Problem

問題

解法

理想型

NN 側と MM 側をともに訪れる

どちらか片方にしか訪れない

両側をペアにする

E - Pass to Next

問題

解法

重複除外

数式化

Σを1つずつ外す

$N$ 側と $M$ 側をともに訪れる