精進（2024/4/1） - あるぱかのブログ

AtCoder Beginner Contest 341 D - Only one of two
AtCoder Beginner Contest 344 D - String Bags

最近のABCからD問題を解く

AtCoder Beginner Contest 341 D - Only one of two

リンク：D - Only one of two (atcoder.jp)

概要：正整数 $N, M$ のうち一方のみで割り切れる正整数の小さいほうから $K$ 番目を出力してね

この問題では以下の3つの考え方を使用します。ひとつひとつはそれほど難しくない概念ですが組み合わさることで緑diffの問題になるのすき。

・ユークリッドの互除法

・包除原理（ベン図的なアレ）

・答えで二分探索

まず、「 $N, M$ のどちらか一方でのみ割り切れる」、という文言を「 $N, M$ のいずれかで割り切れる数から $N, M$ の両方で割り切れる数を引く」と読み替えます。

さらに「 $N, M$ の両方で割り切れる数」は「 $N, M$ の最小公倍数で割り切れる数」と表現できます。

最小公倍数を高速に求めるためにユークリッドの互除法を使います。

（アルゴリズムの詳しい説明は他所にいくらでもあるのでそちらに任せます）

ユークリッドの互除法により求めることができる最大公約数を $gcd(N, M)$ と表すと最小公倍数は $\dfrac{N \times M}{gcd(N, M)}$ で計算できます。

例として $N=6,M=21$ とすると $gcd(6,21)=3$ 、最小公倍数＝ $\dfrac{6 \times 21}{3}=42$ と計算でき正しいことがわかります。

下記の提出コードでは自分で関数gcdを定義していますが、標準ライブラリmathの中に関数gcdが存在するのでfrom math import gcdで使っても構わないですしそのほうが処理も早いです。

（なんなら最小公倍数を求めるlcmという関数もあります）

次にベン図的なアレの考え方について、

$X$ 以下の正整数で $N,M$ のいずれか一方のみで割り切れる数の個数は下の図から $\lfloor \dfrac{X}{N} \rfloor + \lfloor \dfrac{X}{M} \rfloor - 2 \times \lfloor \dfrac{X}{gcd(N,M)} \rfloor$ で表すことができます。

（ $\lfloor \dfrac{X}{gcd(N,M)} \rfloor$ 部分が重なっているため2回引いている）

最後に二分探索ですが、二分探索の中点 $\dfrac{L+R}{2}$ が答えであると仮定して上記で求めた数が $K$ より多いか少ないかを考えることで効率的に探索を行うことができます。

#ユークリッドの互除法をgcdとして関数定義
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
N, M, K = map(int, input().split())
L = 1
R = 10**19
#最小公倍数
x = N*M // gcd(N, M)
#二分探索
while L< R:
    mid = (L+R) // 2
    #包除原理
    ans = mid//N + mid//M - 2*(mid//x)
    if ans < K:
        L = mid+1
    else:
        R = mid
#ループを抜けるとL=R=答えになっている
#print(L, mid, R)
print(R)

提出リンク：提出 #51700930 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

AtCoder Beginner Contest 344 D - String Bags

リンク：D - String Bags (atcoder.jp)

概要：袋から文字列を取ったり取らなかったりして目的の文字列 $T$ をつくってね

取ったり取らなかったりということで動的計画法を使います。動的計画法は必殺技っぽいのですき。いまのところ一番好きなアルゴリズムかもしれない。

何袋目まで見たか、何文字目まで完成したかで表を作って中身にはコストを記入します。

ターゲット文字列は最大100文字、袋から1回取り出すごとにコスト1なのでコストの最大値は100、ということで二次元配列 $dp$ を10,000くらいで初期化したのちに $dp_{0,0}=0$ として初期状態とします。

入力例1の場合では下図のようになります。

$dp$ の遷移式は以下のようになります。

とりあえず $dp[i][j]=dp[i-1][j]$ で上書きする。（今見ている袋について操作を行わなかった状態）

そのあとで $T[j-ls:j] = S[k]$ ならば $dp[i][j]=min(dp[i-1][j-ls]+1, dp[i][j])$

（袋から取り出した文字列 $S[k]$ の長さを $ls$ として）

この $dp_i$ の初期化と最小値上書きの順番で3時間くらい悩みました。

入力例1については下図のように遷移していきます。

$dp[2][4]$ は袋1からab、袋2からcdを取り出しても到達できますが、袋1からabcdを取り出した場合のほうがコストが小さいのでそちらが採用されています。

最終的な解答は以下になります。

鉄則本で勉強した影響で動的計画法だけは1-indexedで書くクセがつきました。

#ABC344 D - String Bags
T = input()
N = int(input())
n = len(T)
#dpを10,000で初期化
dp = [[10000 for i in range(n+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    A, *S = map(str, input().split())
    A = int(A)
    for j in range(n+1):
        #操作を行わなかったとしてdp[i]をdp[i-1]で上書き
        dp[i][j] = dp[i-1][j]
        for k in range(A):
            ls = len(S[k])
            #条件を満たす場合にコストの更新
            if j-ls >= 0 and T[j-ls:j] == S[k]:
                dp[i][j] = min(dp[i][j], dp[i-1][j-ls]+1)
if dp[-1][-1] < 10000:
    print(dp[-1][-1])
else:
    print(-1)

提出リンク：提出 #51942668 - トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）