AtCoder Beginner Contest 150 D~F問題メモ

D - Semi Common Multiple

問題

  • 長さ NN の偶数列 a1,a2,...,aNa1,a2,...,aN
  • ある非負整数 XX が以下の条件を満たす時、XX を「半公倍数」と呼ぶ
    • 全ての k (1kN)k (1kN) に対して、X=ak×(p+0.5)X=ak×(p+0.5) となる整数 pp が存在する(ppkk ごとに別々でよい)
  • 整数 MM が与えられるので、1以上 MM 以下の半公倍数の個数を求めよ
  • 1N1051N105

解法

小数が出てくるとややこしいが、bi=ai2bi=ai2 として、X=bi×(2p+1)X=bi×(2p+1) としてしまえばいい。

これで、以下の2つを満たせばよいことがわかりやすくなる。

  • XX は全ての bibi の公倍数
  • XXbibi で割った商は全て奇数

なので、とりあえず全ての bibi の最小公倍数を求めて、それが bibi で割ると全て奇数となるか確認する。

1つでも偶数となるものがあれば、達成不可能。

全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。

2数 n,mn,m の最小公倍数は、最大公約数を gg として nmgnmg で求められる。3数以上なら、これを繰り返し適用しつづければよい。

ただし bibi が互いに素だと、最小公倍数は繰り返している内にとてつもなく大きくなってしまう。途中で MM 以上になった時点で MM 以下の半公倍数は不可能なので、0を出力して即終了する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from fractions import gcd
 
 
def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        a //= 2
        lcm *= a // gcd(lcm, a)
        if lcm > m:
            return 0
    for a in aaa:
        if int(lcm / a) == lcm / a:
            return 0
    return (m // lcm + 1) // 2
 
 
n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
 
print(solve(n, m, aaa))

E - Change a Little Bit

問題

  • 長さ NN の数列 C1,C2,...,CNC1,C2,...,CN が与えられる
  • 0と1からなる2つの異なる数列 S,TS,T を考える
  • SS の先頭から ii 番目の要素を、0から1、または1から0に変更するには、操作直前に SSTT が異なっている個数を DD として、コスト Ci×DCi×D かかる
  • f(S,T)f(S,T) を、SSTT に一致させるのに必要なコストの最小値とする
  • さて、(S,T)(S,T) の組み合わせは、2N×(2N1)2N×(2N1) 通りある
  • 全ての (S,T)(S,T) の組について f(S,T)f(S,T) を求め、その総和を求めよ
  • 1N2×1051N2×105

解法

処理の優先順位の考察

最初から異なっている要素数が kk 個の時、異なっている箇所にある CiCi のうち、

  • Ci1Ci1 を選び Ci1×kCi1×k のコストをかけて、異なっている要素を k1k1 個にする
  • Ci2Ci2 を選び Ci2×(k1)Ci2×(k1) のコストをかけて、異なっている要素を k2k2 個にする
  • CikCik を選び Cik×1Cik×1 のコストをかけて、異なっている要素が0になる

という操作を経て、SSTT が一致する。 なので、CiCi の小さい方から処理するのが最適である。

とりあえず CiCi を昇順にソートし、indexを0から振り直す。

i   0   1   2   3   4
C  25  52  67  72  79

(注: 解説pdfとは逆順で考えを進めている)

数え挙げ

1つずつ f(S,T)f(S,T) を求めるという視点から、各 CiCi が何回足されるかという視点に転換する。

CiCi について考える時、CiCi より小さい要素、CiCiCiCi より大きい要素に分けてそれぞれのパターン数を考える。

まず、CiCi より小さい要素は ii 個あるが、Si,TiSi,Ti が0,1のそれぞれどちらを取るかで1つあたり4通り、計 4i4i 通りある。 この部分は、最初に異なっていようと、ii 番目を変更する頃には先に操作されて同じになっているので、初期状態を気にしなくてよい。

CiCi が足される場合、要素 ii は異なっていることは確定。(0,1)(1,0)の2通りある。

CiCi より大きい要素は全部で Ni1Ni1 個あるが、コストに関わってくるので初期状態で異なっている箇所の数 kk を気にする必要がある。

kk を固定すると、パターン数は Ni1Ni1 個から kk 個を選ぶので、Ni1CkNi1Ck、 各要素に付き、同じ要素は(0,0)(1,1)、違う要素は(0,1)(1,0)でそれぞれ2パターンずつあるので 2Ni12Ni1

コストは1パターンあたり Ci(k+1)Ci(k+1)。(kk のカウントに ii 番目は入っていないため、1足す)

これを k=0Ni1 までの総和を取るので、コスト総計は 4i×2×2Ni1×Ni1k=0Ni1Ck×Ci×(k+1) となる。

しかし、このままでは1つの i を求める内部でさらに のループがあるため O(N2) となってしまう。

ここで、二項係数の総和の公式より、nr=0nCr(r+1)=2n1(n+2) となることを利用できる。

式変形による証明

よって上の式は、4i×2×2Ni1×2Ni2×(Ni+1)×Ci となり、 2の冪をまとめると上手い具合に合成されて 4N1×(Ni+1)×Ci となる。

よって、これを i=0N1 まで合計すれば、答えとなる。

1
2
3
4
5
6
7
8
9
n = int(input())
ccc = list(map(int, input().split()))
ccc.sort()
MOD = 10 ** 9 + 7
ans = 0
others = pow(4, n - 1, MOD)
for i, c in enumerate(ccc):
    ans = (ans + others * c * (n - i + 1)) % MOD
print(ans)

F - Xor Shift

問題

  • 長さ N の2つの非負整数列 A={a0,...,aN1}B={b0,...,bN1} が与えられる
  • 次の条件を満たす整数の組 (k,X) を全て列挙せよ
    • Ak 個左に回転させ、全要素に X をXORすると、B に一致する
  • 1N2×105
  • 0ai,bi<230

A  0  2  1
B  1  2  3

(k, X) = (1, 3) のとき、
A  2  1  0    左に1個回転
A' 1  2  3    X=3をXOR でBに一致させることができる

解法

共通の数 X をXORしても、隣り合う要素とのXORは変わらないことがとっかかりとなる。

つまり、C={a0a1,a1a2,...,aN1a0} とすると、A にどんな数をXORしても C は不変となる。

よって、AC と同様に BD も作ると、「C をいくつずらすと D に一致させることができるか?」とX を除外して k のみに限定して考えることができる。

これは、D を繰り返して2倍の長さにしたものを D として、D から C を探す処理に言い換えられる。

数列の各要素を文字と見なして、文字列検索アルゴリズムのローリングハッシュやKMP法を用いることができる。

一致するindex k が見つかれば、AkB0 を一致させればよいので、AkX=B0X=AkB0 より、その k に対しての X を求められる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solve(n, aaa, bbb):
    ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
    ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]
 
    ans = []
     
    # ローリングハッシュ
    m = 2147483647
    g = 1000000007
    s = 0
    for c in ccc:
        s = (s * g + c) % m
    t = 0
    for d in ddd:
        t = (t * g + d) % m
    u = pow(g, n, m) - 1
    for i in range(n):
        if s == t:
            ans.append((i, aaa[i] ^ bbb[0]))
        s = (s * g - ccc[i] * u) % m
    ans.sort()
    return ans
 
 
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in ans))

programming_algorithm/contest_history/atcoder/2020/0110_abc150.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0