2021-05-04

ZONe2021 B問題友好の印数学問題の解説

ZONe2021 B問題の解説です。
中学の数学の座標の扱いを覚えていれば解ける問題です。

問題

あなたは今、高さ 1000 の非常に高いタワーの下にいます。タワーから距離 D 離れた位置の上空 H の高さに UFO がおり（入出力例 1 の図を参照してください）、あなたは UFO に電波を届けたいです。
タワーと UFO の間には遮蔽物が N 個あります。i 番目の遮蔽物はタワーから UFO の方向に向かって距離 $d_i$ の場所に位置していて、高さは $h_i$ です。
あなたはタワーを上って、あなたと UFO の間の直線上に遮蔽物が 1 つも無い状態にしたいです。上る必要のある最低の高さを求めてください。
なお、地面は凹凸のない水平面であり、タワー及び遮蔽物は地面と垂直に建っているものとします。
また、あなたと UFO の間の直線上にちょうど遮蔽物の上端があるとき、その遮蔽物には遮蔽されていないものとします。

解き方の方針

それぞれの遮蔽物の頂点座標とUFOの位置を直線で結んで、y切片（ $x = 0$ の時のyの位置）を求めます。y切片の最大値が答えです。

f:id:hrksb5029:20210502215810p:plain — 解き方のイメージ

UFOのx, y座標が $(D, H)$ 、遮蔽物のx, y座標が $(d, h)$ のとき、 $x=0$ の時のyは以下のように求められます。
まず傾きはyの増分をxの増分で割って $(H - h) / (D - d)$ になり、次の式が得られます。
$y = \frac{(H - h)}{(D - d)}x - b$
ここで $b$ を求めるにはxとyにそれぞれUFOの座標か遮蔽物の座標を代入します。
UFOの座標を代入すると以下のようになります。
$H = \frac{(H - h)}{(D - d)}D - b \\ \Leftrightarrow b = \frac{(H - h)}{(D - d)}D - H$

実装

単純に遮蔽物ごとにx=0の時のyの値を求めて、その最大値を答えとします。

N, D, H = map(int, input().split())
ans = 0
for i in range(N):
    d, h = map(int, input().split())
    b = (D*h - d*H) / (D - d)
    ans = max(ans, b)
print(ans)

2021-05-03

ZONe2021 D問題宇宙人からのメッセージの解説とふりかえり

ZONe2021 D問題を解説します。

atcoder.jp

問題

暗号文 S が与えられます。この暗号文は、以下の操作で解読することが出来ます。
T を空文字列とする。 $i = 1,2,\dots ,|S|$ について、順番に以下を行う。 ( $|S|$ は S の長さを表す)
S の i 文字目が R のとき、T を反転させる。
S の i 文字目が R でないとき、その文字を T の末尾に加える。
この操作の後、T の中に同じ文字が 2 つ連続で並んでいたら、その 2 文字を取り除く。この操作を出来る限り続ける。 (最終的に得られる文字列は取り除く順番によらないことが証明できる)
この操作で得られる文字列 T を出力してください。

難しいポイント

暗号文の長さが $1 \leq |S| \leq 5 \times 10^5$ なので、反転の操作をそのまますると計算量が文字の長さ分かかるので、タイムアウトします。
2文字連続する文字を除くのも実直に探索すると文字列の長さの分だけ計算量がかかるので、この操作も工夫が必要です。

解き方の方針

反転の操作はその場で操作するのではなくて、反転した状態かどうかをフラグで記録しておきます。
答えを出力手前で反転していれば、反転して出力します。
文字を末尾につける操作の時も、反転した状態の場合は末尾ではなくて先頭につけます。

2文字連続する文字を除く操作については、文字を加えるときに末尾の文字と加えようとしている文字が同じ場合は2文字続いてしまうので、末尾の文字を取り除きます。

操作対象のTはcollections.dequeで定義しておきます。先頭への追加がO(1)の計算量で済みます。

最近解いたC - IPFLに近い問題だと思いました。

実装方法

実装方法で特別なことはないです。
Tの長さが0のときは有無を言わせず文字を追加して、continueしてすぐに次のループに入ってます。
早期リターンのノリで for 文の中で早期continueする書き方が自分の好みです。
continueの後の処理を書くときに、全段のif文の条件式のことを考慮しなくて済みます。
ここだと長さ0のif文を最初に持ってきて処理してcontinueしているので、その後の処理では長さ0という条件を考慮に入れる必要はありません。

from collections import deque

S = input()
flip_flag = False
T = deque()

for s in S:
    # フラグを反転させるだけ
    if s == 'R':
        flip_flag = not flip_flag
        continue
    # 長さ0なら最後に追加する
    if len(T) == 0:
        T.append(s)
        continue
    # 反転した状態で操作する
    if flip_flag:
        # 付け足すことで同じ文字が連続しそうなら削除する
        if T[0] == s:
            T.popleft()
        else:
            T.appendleft(s)
    # 反転してない状態で操作する
    else:
        # 付け足すことで同じ文字が連続しそうなら削除する
        if T[-1] == s:
            T.pop()
        else:
            T.append(s)

# 最後に反転した状態なら反転させる
if flip_flag:
    T.reverse()
print("".join(T))

C問題が400点でD問題が300点の理由がわかった気がします。
文字列操作の練習として、私にはちょうどいい問題のような気がしました。

2021-05-02

ZONe2021 C問題 MAD TEAM の解説とふりかえり

残念ながら解けなかったC問題 MAD TEAMを解説してふりかえります。

atcoder.jp

問題の概要

N 人のメンバー候補がいて、それぞれの人は、パワー・スピード・テクニック・知識・発想力の 5 種類の能力値を持っています。
N 人のメンバー候補から総合力が最大になるように3名を選ぶ問題です。
総合力は、それぞれの能力についてメンバーの中の最大値をとって、その5つの能力値の中で最小の値です。

難しいポイント

Nが最大で3000なので、単純に全ての組み合わせでチェックすると ${}_{3000}C_{3} = 4495501000$ なので、タイムアウトします。
私は当てずっぽうで、それぞれの能力で1番目、2番目、3番目の能力値を持っているメンバーを選んで、その中で全通り調べましたが、それは誤った答えになりました。
他にも、それぞれの能力値が最大の値（答え）となり得るかチェックする方法を考えましたが、それでも組み合わせを調べないといけなくなり、ループの中で最大3000の中で2つを選ぶ組み合わせを調べるのも、 ${}_{3000}C_{2} = 4498500$ となり、タイムアウトになります。
組み合わせを使わないように工夫が必要です。

解き方の方針

公式解説を読んで目から鱗が落ちました。

最小値の最大値のような形の問題では、答えを二分探索し、「答えが $x$ 以上になるか？」という判定問題に持ち込むと簡単になることがあります。

そういう発想があったとは。。。

値の範囲が $1 \leq A_i, B_i, C_i, D_i, E_i \leq 10^9$ なので、答えとなる最大値を $x$ として、 $x$ の値を1から $10^9 + 1$ の範囲で二分探索します。
この $x$ を置くことで、 $x$ より大きいか、小さいかという基準だけが必要な情報になります。
全ての能力値をx以上なら 1 あるいは未満なら 0で圧縮することができます。
そうすると1人のメンバーの能力値のパターンとしては、 $2^5 = 32$ 種類だけになります。
$x$ 以上の能力値を持っているメンバーで全通りの組み合わせを見て、全ての能力で $x$ 以上の場合、二分探索の判定をTrueにします。
総合力として、能力値の中の最小値をとってるので、どこかの能力値が $x$ を下回っているとFalse、全ての能力値が $x$ を上回っているから、能力値は更新されることになります。

判定がTrueということは $x$ 以上の値ばかりなので、探索範囲の下限を中央値にして次のループに入ります。

実装方法

公式解説の実装を説明します。
atcoder.jp

二分探索の実装については@hamkoさんの記事がおすすめです。
qiita.com

実装のポイントは二分探索の判定関数です。

まずはメンバーの能力を探索している $x$ 以上かどうかの2進数で表現します。
$x = 18$ で、あるメンバーの能力が $(A, B, C, D, E) = (6, 19, 20, 5, 1)$ のとき、
18より大きいところに1を立てます。
Aの値に対して $2^0$ 、Bの値に対して $2^1$ 、Cの値に対して $2^2$ 、Dの値に対して $2^3$ 、Eの値に対して $2^4$ を割り当てたとすると、 $00110_{(2)} = 6$ になります。

for a in A:
    s.add(sum(1 << i for i in range(5) if a[i] >= x))

総合力として、能力値の中の最小値をとってるので、どこかの能力値が $x$ を下回っているとFalse、全ての能力値が $x$ を上回っているから、能力値は更新されることになります。
全ての能力値が $x$ を上回っているということは、各メンバーの能力を OR でとって、全てのビットに1が立っていればTrueになります。
全てのビットに1が立っているということは、 $2^5 - 1 = 31$ に等しいかどうか判定します。

for member1 in s:
    for member2 in s:
        for member3 in s:
            if member1 | member2 | member3 == 31:
                return True
return False

全体のコードは以下のようになりました。

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]


def check(x):
    s = set()
    for a in A:
        s.add(sum(1 << i for i in range(5) if a[i] >= x))
    for member1 in s:
        for member2 in s:
            for member3 in s:
                if member1 | member2 | member3 == 31:
                    return True
    return False


ok = 0
ng = 10**9 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

圧縮の工夫はとてもためになりました。
そして今の私の実力では何時間悩んでも思いつかなかったと思います。
判定をTrueにする条件も感動しました。
学びの多い問題だったので復習します。

2021-04-30

ABC114 C問題 755を3進数を使って解く

ABC114 C問題 755 を公式解説とは異なる実装方法の解説をします。
公式解説の深さ優先探索を使った書き方の方が簡潔で美しいです。
私の書き方は愚直な感じでスマートではありません。

atcoder.jp

問題

整数 N が与えられます。
1 以上 N 以下の整数のうち、七五三数は何個あるでしょうか？
ここで、七五三数とは以下の条件を満たす正の整数です。
十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

難しいポイント

Nが最大で $10^9$ なので、1からNまで何も考えずに七五三数かどうか判定して、数を数えるのはPythonでは制限時間には収まらないです。
あと方針が決まっても実装方法もいくつか思いつくので迷いが生じる気がします。

解き方の方針

数字7, 5, 3が一回ずつ現れる数字はそれほど多くなさそうというところに着目します。
9桁それぞれで7か5か3を選ぶ場合の数を考えても全部で $3^9 = 19683$ 通りです。
ビット全探索の発想を応用して、3進数で全探索して、N以下という条件と7, 5, 3が1回ずつ出現する条件の両方を満たす数を数えます。

実装方法

3進数で、2を7、1を5、0を3に見立てて、全部列挙して七五三数なのか、N以下なのか確認して、数を数えていきます。

3進数を列挙するときにproductメソッドを使いました。
以下の場合は、0, 1, 2から4桁の全ての場合の数を列挙してくれます。

from itertools import product
product(range(3), repeat=4)
# (0, 0, 0, 0), (0, 0, 0, 1) ... (2, 2, 2, 2)

3進数を10進数への変換も必要です。
例えば、210 だったら753に変換します。
3進数の数字を配列としてみた時に、インデックス0は2です。これは7に変換して $10^2$ をかけます。
配列の長さ - インデックス数 - 1 が10進数で何乗するかの値になります。
3桁の場合を列挙すると以下のようになります。
3 - 0 - 1 = 2 -> $10^2 = 100$
3 - 1 - 1 = 1 -> $10^1 = 10$
3 - 2 - 1 = 0 -> $10^0 = 1$

コードは以下のようになりました。

from math import log10
from itertools import product
N = int(input())

# Nの桁数を求める
max_keta = int(log10(N)) + 1

ans = 0

# 1桁からNの桁数までループする
for keta in range(1, max_keta + 1):
    search_list = product(range(3), repeat=keta)
    for sl in search_list:
        # 3進数で 2 -> 7, 1 -> 5, 0 -> 3 とする
        # 7か5か3が1回以上含まれていなかったら次のパターンへ行く
        if not (2 in sl and 1 in sl and 0 in sl):
            continue
        # 210 だったら 753 に変換する
        # len = 3 のとき index 0 だったら 10^2 をかけて足す
        # len - index - 1 で 3 - 0 - 1 = 2, 3 - 1 - 1 = 1, 3 - 2 - 1 = 0
        number = 0
        TRANS = [3, 5, 7]
        for j, n in enumerate(sl):
            number += 10**(len(sl) - j - 1) * TRANS[n]
        if number <= N:
            ans += 1

print(ans)

公式解説を読んで、深さ優先探索で再帰的に処理する方法に慣れないといけないなと思いました。

2021-04-25

ABC199 C問題 IPFL を解く

ABC199 C問題 IPFLを解説しつつ、ふりかえります。

atcoder.jp

問題

長さ 2N の文字列 S があります。
この文字列に対して Q 個のクエリが与えられます。
i 番目のクエリでは 3 つの整数 $T_i, A_i, B_i$ が与えられるので、以下の処理をします。
$T_i = 1$ のとき : S の $A_i$ 文字目と $B_i$ 文字目を入れ替える
$T_i = 2$ のとき : S の前半 N 文字と後半 N 文字を入れ替える( $A_i, B_i$ の値は用いない)
例えば S が FLIP のときにこのクエリを処理すると、S は IPFL となる。
これら Q 個のクエリを与えられた順に全て処理した後の S を出力してください。

難しいところ

ダメダメな私は計算量がだめかもと思いつつ、dequeとか使って素直に問題の通りの処理を実装して、時間制限を超えました。
クエリの数が最大で $3 \times 10^5$ 、文字の長さが最大で $4 \times 10^5$ になるので、 $T_i =2$ の前半と後半の入れ替え処理で素直にループすると無理なんですよね。。。
そして最後まで良い知恵が思いつきませんでした。。。

解く時のイメージ

前半と後半を入れ替える処理は、偶数回入れ替えたら、元の文字列になります。
問題なのは、前半と後半が入れ替わった時に、インデックス指定で文字を入れ替える時です。
なので、その処理の時だけ前半後半の入れ替えが発生しているかどうかを勘案して、インデックスをひねってから文字を入れ替えます。
あとは最後に入れ替わっているかの状態を見て、前半と後半を入れ替えてから文字列を出力する、あるいはそのまま出力します。

具体的な解き方

まずは、前半と後半を入れ替える処理についてはフラグで文字列の状態を管理します。なので、 $T_i =2$ の時はこのフラグを反転させるだけにします。
例えば、奇数回入れ替えが発生してたら、フラグをTrueにします。

文字を入れ替える処理の時は、この前半後半の入れ替えが発生していることを考慮します。
インデックスが前半にあったら、長さが2Nなので、Nだけ足します。
インデックスが後半にあったら、Nだけ引きます。
例えば、4文字の長さだったら、前半と後半の入れ替えで、インデックスは0 -> 2、1 -> 3、2 -> 0、3 -> 1になります。
その後に指定されたインデックスの位置の文字を入れ替えます。

その操作をクエリの数だけ繰り返して、最後に入れ替えフラグを見て、入れ替わっているようなら前半と後半を入れ替える処理をします。
ここはループの外なので計算量のオーダーが文字列の長さと等しくても大丈夫です。

以下のコードになりました。

N = int(input())
S = list(input())
Q = int(input())

flip_flag = False

for i in range(Q):
    t, a, b = map(int, input().split())
    if t == 1:
        # 前半後半が反転しているケース
        if flip_flag:
            # aとbのインデックスが前半にあるか判定してNを足すか引くか決める
            a_idx = a - 1 - N
            if a - 1 < N:
                a_idx = a - 1 + N
            b_idx = b - 1 - N
            if b - 1 < N:
                b_idx = b - 1 + N
            S[a_idx], S[b_idx] = S[b_idx], S[a_idx]
            continue
        # 前半後半が反転していないケース
        S[a - 1], S[b - 1] = S[b - 1], S[a - 1]
        continue
    # t == 2の時は前半後半が反転しているかどうかの状態を変更するだけ
    flip_flag = not flip_flag

# 最後に前半後半が反転しているかどうかで、反転させるか決める
if flip_flag:
    newS = "".join(S[N:] + S[:N])
    S = newS

ans = "".join(S)
print(ans)

2021-04-20

ABC156 C問題 Rallyの解説

ABC156 C問題 Rallyを解説します。

atcoder.jp

問題

数直線上に N 人の人が住んでいます。
i 番目の人が住んでいるのは座標 $X_i$ です。
あなたは N 人全員が参加する集会を開くことを考えています。
集会は数直線上の任意の整数値の座標で開くことができ、座標 P で集会を開くとき、
i 番目の人は集会に参加するために $(X_i − P)^2$ の体力を消費します。
N 人が消費する体力の総和としてありえる値の最小値を求めてください。

解き方のイメージ

NとXの制約は最大で100です。
集会を開く座標の範囲も最悪のケースで1から100までの間になります。
集会を開く座標Pを固定した時に、Pとそれぞれの住人の座標の差分の二乗の合計を求めるのも最大で100回です。
なので全探索しても計算量は最大で10000回なので、余裕で解けることがわかります。

Pの探索する範囲は、Xの最小値と最大値の間でよいので、その範囲でループさせます。

全体のコードはこのようになりました。

N = int(input())

# ソートしておいて、Xの最小値と最大値を取りやすくする
x_arr = sorted(list(map(int, input().split())))
# 答えの初期値はすごく大きい数にする
ans = 10**9 + 7
# Xの最小値と最大値の間でPを変動させる
for p in range(x_arr[0], x_arr[-1] + 1):
    total = 0
    for x in x_arr:
        total += (x - p) ** 2
    # 累積和を比較して最小のものを答えにする
    ans = min(ans, total)
print(ans)

2021-04-19

js2021 D問題 Nowhere P 数学問題を解説

js2021 D問題 Nowhere P を噛み砕いて解説します。

atcoder.jp

問題

2 以上の整数 P が与えられます。これはあなたの嫌いな数です。
整数の列 $A_1, A_2, ..., A_N$ が以下の条件を満たすとき、この列を とても良い列と呼びます。
1 以上 N 以下のどの整数 i についても、 $A_1 + A_2 + ... + A_i$ は P の倍数でない
各要素が 1 以上 P−1 以下であるような長さ N の整数列は全部で ${(P−1)}^N$ 個存在しますが、このうち とても良い列はいくつあるでしょうか？
ただし、答えは非常に大きくなることがあるので、答えを $(10^9 + 7)$ で割った余りを出力してください。

解き方のイメージ

まずNやPの制約が最大で $10^9$ になってる時点で全探索はないなと考えます。
何かしら工夫が必要なのですが、「何かしらの工夫」を見つけるために、程よく小さめなNやPのケースを手を動かして考えてみます。
サンプルにある N = 3, P = 3で考えてみます。
N = 3なので、 $A_1 + A_2 + A_3$ が3の倍数でないものがとても良い列になります。
$A_1$ を選ぶとすると、P = 3なので、1 か2のどちらかになります。
次に、 $A_2$ を選ぶ時に、 $A_1 + A_2$ が3で割り切れないように選びます。
$A_1 = 1$ の時は $A_2 = 1$ 、 $A_1 = 2$ の時は $A_2 = 2$ です。
次に $A_3$ を選ぶときも $A_1 + A_2 + A_3$ が3で割り切れないように選びます。
$A_1 + A_2 = 1 + 1 = 2$ の時は $A_3 = 2$ で $A_1 + A_2 + A_3 = 1 + 1 + 2 = 4$ です。
$A_1 + A_2 = 2 + 2 = 4$ の時は $A_3 = 1$ で $A_1 + A_2 + A_3 = 2 + 2 + 1 = 5$ です。
Nの数を増やして、N = 4, P = 3だとしても、次の $A_4$ の選び方はそれぞれの分岐で1通りしかないことがわかります。
$A_1 + A_2 + A_3 = 1 + 1 + 2 = 4$ の時は $A_4 = 1$ で $A_1 + A_2 + A_3 + A_4 = 1 + 1 + 2 + 1 = 5$ です。
$A_1 + A_2 + A_3 = 2 + 2 + 1 = 5$ の時は $A_4 = 2$ で $A_1 + A_2 + A_3 + A_4 = 2 + 2 + 1 + 2 = 7$ です。

N = 3, P = 4 で考えます。
$A_1$ は特に制約はなく1〜3の間で好きに選べます。
$A_2$ は $A_1 = 1$ の時、4の倍数にならないように $A_2 = 1 or 2$ の2通りの中から選びます。
もちろん $A_1 = 2$ の時、4の倍数にならないように $A_2 = 1 or 3$ の2通りから選びますし、
$A_1 = 3$ の時も4の倍数にならないように $A_2 = 2 or 3$ の2通りから選びます。
次に $A_3$ の選び方を考えます。
$A_1 + A_2 = 1 + 1 = 2$ の時、4の倍数にならないように $A_3 = 1 or 3$ の2通りから選びます。
他の分岐も同じです。全部4の倍数にならないように3 - 1通りの2通りから選ぶことになります。
N = 3までの分岐の樹形図を描きました。

これまでのサンプルを踏まえてとても良い列の場合の数を考えると、
最初の選び方は $(P - 1)$ 通り、そのあとは $(P - 2)$ 通りを $N - 1$ 回繰り返します。

なので、答えは $(P - 1) \times (P - 2)^{N - 1}$ です。

$10^9 + 7$ で割った余りが求められています。

$10^9 + 7$ の計算は@drkenさんの以下の記事を参考にしました。
qiita.com

コードは以下のようになりました。

N, P = map(int, input().split())
MOD = 10**9 + 7


# a^n modを計算する
def modpow(a: int, n: int, m: int):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % m
        a = a * a % m
        n = n >> 1
    return res


ans = ((P - 1) % MOD) * modpow((P - 2), (N - 1), MOD)
print(ans % MOD)