解説つき！競ってわかる　はじめてpythonプログラミング

競プロの情報発信と備忘録を兼ねている

ABC243C

AtCoder Python

ABC243C の解説

atcoder.jp

 

解答コード 

https://atcoder.jp/contests/abc243/submissions/30091837

 

 

問題

2次元平面座標で，同じy座標を移動する点同士が衝突するかどうかを判定する問題です．

 

解説

いつも通り，無言で投下する概要図です．

f:id:nodashin_jpn:20220313114147j:plain

ABC243C_overview

点はx方向にしか移動できないので，y座標の値が異なれば衝突しません．
このことから，同じy座標の値の点同士を評価すれば良いことがわかります．

では，同じY座標同士をまずグループ化します．
yの制約が10^9 なので，その分だけ配列を作成するのは，合理的ではありません．
これを実現する方法は２つあると思います．
1) 最初にyでソートする．
2) 辞書型でまとめる     <- 今回はこっち

今から，Y座標ごとに点をまとめます．
このとき，その点が「L向きなのかR向きなのか」もまとめてあげるとスッキリします．すなわち，座標と向き（L or R）を同時に処理します．

上記の内容を実現するために，一旦標準入力を全部読み取ります．

N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]
S = input()

 

収納するためのdict と向きを定義します．向きを定義した意味は後程わかります．

Y = {}
d = {'R': 0, 'L': 1}

 

それでは，あらかじめ読み取っておいた標準入力を順番に処理していきます．
各y座標の値ごとに長さ2の二次元配列を用意して，
index=0にR向きのx座標を
index=1にL向きのx座標を入れます．

for i in range(N):
    x, y = coords[i]
    drct = d[S[i]]
    if y not in Y:
        Y[y] = [[], []]  # [[x Right], [x Left]]
    Y[y][drct].append(x)

 

最後に，各y座標ごとに
R向きでx座標が最小の点と，L向きでx座標が最大の点が衝突できるかを
大小関係をもとに判断します．

ans = 'No'
for r, l in Y.values():
    if l and r:
        r_min = min(r)
        l_max = max(l)
        if r_min < l_max:
            ans = 'Yes'
            break
print(ans)

 

以上，ABC243Cの解法でした．

 

＜参考解説リンク＞

 

 

 

ABC242C別解: 行列による解法

ABC242C の別解

atcoder.jp

 

解答コード

提出_1: TLE．(N-1)回の行列の内積
提出_2: ギリAC．対称性を利用して行列サイズを小さくする
提出_3: AC．(N-1)回の内積を効率よく計算　　<-本記事はこれ

 

解説

すでにDP（動的計画法）で求める方法は解説いたしました <リンク>．

今回のDPの計算を行列で表すと，

w = np.array(
    [[1, 1, 0, 0, 0, 0, 0, 0, 0],  # (0, 1) 番目の和
     [1, 1, 1, 0, 0, 0, 0, 0, 0],  # (0, 1, 2) 番目の和
     [0, 1, 1, 1, 0, 0, 0, 0, 0],  # (1, 2, 3) 番目の和
     [0, 0, 1, 1, 1, 0, 0, 0, 0],  # (2, 3, 4) 番目の和
     [0, 0, 0, 1, 1, 1, 0, 0, 0],  # (3, 4, 5) 番目の和
     [0, 0, 0, 0, 1, 1, 1, 0, 0],  # (4, 5, 6) 番目の和
     [0, 0, 0, 0, 0, 1, 1, 1, 0],  # (5, 6, 7) 番目の和
     [0, 0, 0, 0, 0, 0, 1, 1, 1],  # (6, 7, 8) 番目の和
     [0, 0, 0, 0, 0, 0, 0, 1, 1]]) # (7, 8) 番目の和

こんな行列になります．
実行してみると，もちろん前解説のdpを再現しています．

dp = np.array([1]*9)
print(dp)
for i in range(3):
    dp = w@dp
    print(dp)
# [ 1,  1,  1,  1,  1,  1,  1,  1,  1]
# [ 2,  3,  3,  3,  3,  3,  3,  3,  2]
# [ 5,  8,  9,  9,  9,  9,  9,  8,  5]
# [13, 22, 26, 27, 27, 27, 26, 22, 13]

 

つまりこの問題は，Nが与えられたら，上の行列の(N-1)乗をして，上の行列の要素内の和を求めなさい．というように言い換えることができます．

しかし，行列の計算って遅いんです．

実際にすると提出_1のように，TLEになりました．

そこで，対称性を用いて計算量を減らすと，なんとかACになります（提出_2）．

悩むこと一晩...

そしてついに，よくよく考えたら，行列のN乗を計算するときに，繰り返し自乗法で冪乗の計算の高速化と同様にすれば，早いじゃんっ！って気が付きました．

その関数がこちらです．正則行列をn乗します．途中でmodで割ります．ただそれだけです．

import numpy as np

def pow_array(A, n, mod):
    B = np.eye(len(A), dtype='object')
    while n:
        if n%2:
            B = (B@A) %mod
        A = (A@A) %mod
        n //= 2
    return B

これを書けば，あとは単純です．入力の読み込みとMODを代入，初期の行列を定義して...

MOD = 998244353
N = int(input())
w = np.zeros([9, 9], dtype='int')
for i in range(9):
    for j in (i-1, i, i+1):
        if 0<=j<=8:
            w[i][j] = 1

(N-1)乗を計算して，合計を出力します．

w = pow_array(w, N-1, mod=MOD)
ans = w.sum()%MOD
print(ans)

 

ライブラリのnumpyのndarrayで計算してますが，
もしかするとnumpyを使用しないで，
内積計算をpythonのリストとforで行えば，
多少処理が速くなるかもしれません．

以上，ABC242Cの別解でした．

 

＜参考解説リンク＞
・ユーザ解説 by MMNMM

 

 

ABC242D

AtCoder Python

ABC242D の解説

atcoder.jp


解答コード

https://atcoder.jp/contests/abc242/submissions/29888966

 

問題

文字列を規則的に変換し続ける問題です．
A -> BC
B -> CA
C -> AB

t 回変換したとのk文字目を出力します．

 

解説

t回目の変換をした後のk文字目が問われるので，
k文字目はt-1回の時点では何番目の文字だったのか？
t-2回目の時点では何番目だったのか?
t-3回目の時点では
（中略）
0回目の時点では何番目の文字だったのか？
を探します．

0回目の時点での文字が分かれば，
それをt回変換させることで，答えを導き出します．

概要図です．

f:id:nodashin_jpn:20220306113855j:plain

ABC242D_overview

 

コードにします．

事前に変換操作に使用する辞書を定義します．

d = {'A': 'BC', 'B': 'CA', 'C': 'AB'}

このとき，変換は次のように行うことができます．

print(d['A'])
# BC

 

標準入力を読み取ります．

S = input()
Q = int(input())

 

Q回のクエリが与えられるので，forでQ回処理をします．
kを0-indexにするため，1だけ引きます．

for _ in range(Q):
    t, k = map(int, input().split())
    k -= 1

 

ここから，一旦議論箇所を絞るため，TLEになるコードを書きます．

for の中で，さらに以下のような処理を記述します．
t=tからt=0に向かって，何番目の文字を変換したのか辿ります．

    L = []  # indexを2で割った余りの数を記録しておく
    for i in range(t):
        L.append(k%2)  # 変換後は何文字目?
        k //= 2  # 変換前は何文字目?


t=0の時の文字の番号がわかるので，後はそれをt回変換することで，
処理をシミュレートできます．

    L = L[::-1]  # t=0の方から逆順で処理
    s = S[k]  # t=0のとき[k]文字目だった
    for l in L:  # t回変換する

        s = d[s][l]  # 変換した後の[l]文字目である
    print(s)

 

しかし，このままではTLEします．
なぜならt回の操作が非常に大きいからです．

この問題の変換操作は，1回の操作で文字列の長さが2倍になります．
つまり，t=0の時の1文字目はt=60回目で2^60 = 約10^18の長さになります．

よって，tが大きい時，t=0になるまでに，途中で[0]文字目になります．
その後は，先頭の文字しか追う必要しかありません．
先頭の文字だけ着目すると，
'A'を変換し続けると
'A' -> 'B' -> 'C' -> 'A' -> 'B' -> ...
と3回ごとにループすることから，愚直にシミュレートする必要がないことがわかります．

 

上記の内容を踏まえてコードにします．

事前に文字xを0, 1, 2回変換するとどうなるかを定義しておきます．

X = {
    'A': ['A', 'B', 'C'],
    'B': ['B', 'C', 'A'],
    'C': ['C', 'A', 'B']
    }

 

for 以下の内容は次のようになります．
0文字目になった段階で何番目の文字かを計算するプロセスを中断します．
ただし，中断した分の不足する変換回数分を算出します．
3回の変換で，もとの文字に戻るので，3で割ります．

for _ in range(Q):
    t, k = map(int, input().split())
    k -= 1
    L = []
    x = 0
    for i in range(t):
        L.append(k%2)
        k //= 2
        # 0文字目になれば，もうシミュレートする必要はない．
        if k == 0 and L[-1] == 0:
            # 残り何回変換するか．ただしMOD 3
            x = (t - i - 1)%3
            break
    L = L[::-1]
    # t=0の文字をx回(MOD 3)変換した文字
    s = X[S[k]][x]
    for l in L:
        s = d[s][l]
    print(s)

 

以上，ABC242Dの解法でした．

 

 

＜参考解説リンク＞

 

 

 

ABC242C

AtCoder Python

ABC242C の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc242/submissions/29881684

 

問題

桁DPの問題です．

 

解説

概要図です．

f:id:nodashin_jpn:20220306070445j:plain

ABC242_overview

とりうる数字が1から9であることに注意してください．

一番大きい位の桁から順番に処理していくと（逆でも構いません），
図で千の位で9をとりうる場合の数は1つのみです．
他の数字についても，それぞれの数字をとる場合の数は，それぞれ1です．

つぎに，百の位で9をとる可能性があるのは，千のくらいが (8, 9) のどちらかの時です．この時，千の位でとりうる数字の場合の数を足すと，百の場合の数が求まります．

（百の位が9の場合の数） = （千の位が9の場合の数）+ （千の位が8の場合の数）

同様に百の位が5を取る可能性があるのは，千の位が (4, 5, 6) のどれかの時です．
百の位が1を取る可能性があるのは，千の位が (1, 2) のどれかの時です．

ここで，1と9とる時を考えるときとりうる前の桁の数字は2通り，
1 <- (1, 2)
9 <- (8, 9
それ以外のときは，3通りであることに注意が必要であることがわかります．

それでは実装します．

標準入力を読み取り，MODの値をコピペしておきます．

MOD = 998244353
N = int(input())

 

dpの２次元配列の定義します．初期値は1です．
配列のサイズは（桁数，9）にしました（概要図の表と同じです）．
横方向はゼロインデックスなので，index=0は数字の1を示します．

dp = [[0]*9 for _ in range(N)]
dp[0] = [1]*9

 

続いて，forで桁方向（縦方向）に処理，
1つの桁について1から9までの横方向に足し算の処理をします．

for i in range(N-1):
    for j in range(9):
        dp[i+1][j] = sum(dp[i][max(0, j-1):min(j+2, 9)])%MOD
ans = sum(dp[-1])%MOD
print(ans)

j=0とj=8とる時（数字の1と9）を考えるときとりうる前の桁の数字は2通りなので，
j <- (j-1, j, j+1)
としてしまうと，
0 <- (-1, 0, 1)
になってしますので，
最大と最小を用いて，
0 <- (0, 1)
8 <- (7, 8)
になるよう，0より小さい数字は取らない，9以上の数字は取らないようにしています．

 

以上，ABC242Cの解法でした．

 

 

＜参考解説リンク＞

 

 

 

再帰関数を使用せずにUnion-Findをpythonで書いた

ABC157D-Friend Suggestions を解いてる最中に，Union-Findを使用したが，
PyPy3 で提出すると再帰関数が遅いことをうっかりしてTLEを出してしまった．

じゃあ，Python3で出せば良いじゃんと思うかもしれないが...

再帰の上限設定忘れ ->  RE（ちーーん）
となるのが，お決まりのパターン．

とまあ，こんな感じで，仮にpython3で提出するにしても，
sys.setrecursionlimit() の変更も必要なので，めんどくさい．

 

そこで，Union-Findの再帰関数部分を再帰関数にしなければ，TLEにはならないので，
変更しました（提出コード）．

Union-Findがご入用の際には，ご活用くださいまし．

class UnionFind():
    """
    再帰関数を使用しないので，PyPy3で提出しやすい
    """

    def __init__(self, n):

        self.n = n
        self.parents = [-1]*n

    def unite(self, x, y):
        """unite y -> x"""

        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        self.parents[py] = px
        return

    def find(self, x):

        dq = []
        while self.parents[x] != -1:
            dq.append(x)
            x = self.parents[x]
        else:
            while dq:
                y = dq.pop()
                self.parents[y] = x
        return x

 

ABC238D

AtCoder Python

ABC238D の解説

atcoder.jp


解答コード

https://atcoder.jp/contests/abc238/submissions/29106574

 

問題

2つの数字 a, s が与えられて
x AND y = a
x + y = s
を満たす（x, y）の組みが非負整数で存在するかどうかを調べる問題です．

 

解説

模範解答がどのような仕組みで計算されているのかを解説していこうと思います．

概要と例1（a=1, s=8）についてです．

f:id:nodashin_jpn:20220208205203j:plain

ABC238D_ex1

ANDが aになる必要があることから，aが1になっている桁のみで，すでに和が2aになることがわかります．

このとき，aが1になっていない桁のみで，x + y = s-2a になれば，条件を満たすことになります．

 

うまくいかない例を示します．

f:id:nodashin_jpn:20220208205320j:plain

ABC238D_ex2

a = 1, s = 7のとき，s-2a = 5 は，bitで 0101になりますが，
この 0101 の1の位が1であることは，
x AND y = a を満たしながら，x + y = 7 を満たすには，
1の位が片方が1の組み合わせである必要があることを示しています．

しかし，x AND y = 1 を満たすには，1の位は共に1である必要があるため，
同時に満たすことができません．

すなわち，このような解は存在しないことを意味します．

 

上記の内容をコードにします．

 

標準入力を読み取ります．

T = int(input())

 

T回ループを回して，題意を満たすための条件を満たすかどうかを判定すればよいです．

for _ in range(T):
    a, s = map(int, input().split())
    # 非負整数の組みをもつことより
    flg1 = s - 2*a >= 0
    # 片方のみ1になる必要ある桁（s-2a）と両方1になる必要がある桁（a）の論理和はゼロ
    flg2 = (s - 2*a)&a == 0
    if flg1 and flg2:
        print('Yes')
    else:
        print('No')

 

以上，ABC238Dの解法でした．

 

 

＜参考解説リンク＞

1) 【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！ - Qiita