yukicoder contest 398 解説

2023-07-21 に開催された、VRC競プロ部作問による yukicoder contest 398 の解説です。
yukicoder contest 398: https://yukicoder.me/contests/447

Transcript

1. yukicoder contest 398 解説 2023-07-21 VRC競プロ部 https://yukicoder.me/contests/447
2. yukicoder contest 398 短評 A ★1.5 No.2385 Parse Integer with Radix : 基数変換 First AC : 00:01:34 Shirotsume さん B ★2.0 No.2386 Udon Coupon (Easy) : DP入門編 First AC : 00:01:41 uwi さん C ★3.0 No.2387 Yokan Factory : 二分探索+ダイクストラ First AC : 00:04:25 maspy さん D ★3.0 No.2388 At Least K-Characters : 文字の種類の遷移でDP First AC : 00:13:17 potato167 さん E ★3.0 No.2389 Cheating Code Golf : 解いた問題の集合でbitDP First AC : 00:13:15 Rubikun さん F ★3.5 No.2390 Udon Coupon (Hard) : 最大効率の割引の最低使用回数を考察しつつDPまたは全探索 First AC : 00:07:06 n_vip さん G ★4.0 No.2391 SAN 値チェック : 級数こねこね First AC : 00:12:17 hos.lyric さん スコア一位: 01:33:11 1577pt Rubikun さん、 全完時間では 00:41:05 1463pt hos.lyric さん yukicoder contest 398 解説 2023-07-21 VRC競プロ部 2
3. 問題 A. Parse Integer with Radix ★×1.5 あなたは、 進法・ 進法・ 進法・ 進法のいずれかの形式で表現された非負整数を処理して、 進数 に変換するプログラムを作成することになりました。 個のクエリが与えられます。 番目のクエリでは、非負整数 を表現する文字列 が与えられるので、 を 進法で出力してくだ さい。文字列 は、以下のいずれかの形式で与えられます。 進法の場合： は " 0b " から始まり、 を文字種 { 0 , 1 } からなる 進法で表現したものが続きます。 進法の場合： は " 0o " から始まり、 を文字種 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } からなる 進法で表現したもの が続きます。 進法の場合： は を文字種 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } からなる 進法で表現したものです。 進法の場合： は " 0x " から始まり、 を文字種 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , a , b , c , d , e , f } からな る 進法で表現したものが続きます。 進数の { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , a , b , c , d , e , f } は、それぞ れ 進数で を表します。 制約: は整数 は基数プレフィクスを除くとゼロサプレス yukicoder contest 398 解説 2023-07-21 VRC競プロ部 3
4. 解説 A. Parse Integer with Radix ★×1.5 (1/2) 文字列操作と基数変換の問題です。各文字列の先頭部を見て、何進法で書かれた文字列であるかを条 件分岐し、基数の変換方法を理解しているかを問う問題でした。 文字列の先頭から処理する方法だと、このように書くことができます。 (コード例: Python3/PyPy3) for _ in range(int(input())): S, b, N = input(), 10, 0 if S[:2] == "0b": S, b = S[2:], 2 elif S[:2] == "0o": S, b = S[2:], 8 elif S[:2] == "0x": S, b = S[2:], 16 for c in S: if c >= "0" and c <= "9": N = N * b + (ord(c) - ord("0")) elif c >= "a" and c <= "z": N = N * b + (ord(c) - ord("a") + 10) print(N) yukicoder contest 398 解説 2023-07-21 VRC競プロ部 4
5. 解説 A. Parse Integer with Radix ★×1.5 (2/2) Python や Ruby では、文字列から整数に変換する関数/メソッドに の引数 (文字列先頭の基数プレ フィクスに応じて基数を自動認識) を指定したり、 eval を使って整数を作ったりするワンライナー もありました。以下の5つのような1行コードでもACすることができます。 Python3 / PyPy3: for _ in range(int(input())):print(int(input(),0)) for _ in range(int(input())):print(eval(input())) exec("print(eval(input()));"*int(input())) Ruby: gets.to_i.times{puts gets.to_i(0)} gets.to_i.times{puts eval gets} yukicoder contest 398 解説 2023-07-21 VRC競プロ部 5
6. 問題 B. Udon Coupon (Easy) ★×2 あるうどん屋では、「うどん札」をいくつか使うことで、割引を受けることができます。 割引の受け方は、以下の 種類です。 「うどん札」を 枚使って、 円の割引を受ける 「うどん札」を 枚使って、 円の割引を受ける 「うどん札」を 枚使って、 円の割引を受ける これらの割引は、「うどん札」があれば何度でも受けられますが、使った「うどん札」は消費されま す。 さて、みどりさんは「うどん札」を使って、できるだけたくさんの割引を受けたいと考えました。 「うどん札」が 枚ある時、割引額の合計の最大値 を出力してください。 制約: 入力は全て整数 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 6
7. N = int(input()) A, B, C = map(int,input().split()) dp = [0] * (N + 10) for i in range(N): dp[i + 1] = max(dp[i + 1], dp[i]) dp[i + 3] = max(dp[i + 3], dp[i] + A) dp[i + 5] = max(dp[i + 5], dp[i] + B) dp[i + 10] = max(dp[i + 10], dp[i] + C) print(dp[N]) 解説 B. Udon Coupon (Easy) ★×2 (1/2) DP (動的計画法, Dynamic Programming) で解く事がで きます。 (コード例: Python3/PyPy3) 「配るDP」を用いる場合、 DP[うどん券の枚数]=総割引額 を管理する配列を ～ 番目までの 個、 で初期化して用意し、 整数 を から まで順に、 を と比べて、より大きい値に更新 を と比べて、より大きい値に更新 を と比べて、より大きい値に更新 を と比べて、より大きい値に更新 のように更新を掛けていくことで、「少なくとも 番目までは最善の総割引額が作れている」 という状態を作り続けることができます。計算量は です。 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 7
8. N = int(input()) A, B, C = map(int,input().split()) dp = [0] * (N + 1) for i in range(N + 1): dp[i] = max( dp[i - 1] if i >= 1 else 0, dp[i - 3] + A if i >= 3 else 0, dp[i - 5] + B if i >= 5 else 0, dp[i - 10] + C if i >= 10 else 0, ) print(dp[N]) 解説 B. Udon Coupon (Easy) ★×2 (2/2) もう一つ、「貰うDP」と呼ばれる方法もあります。 (コード例: Python3/PyPy3) ～ 番目までのDP配列で「うどん券の枚数」 ごとの「最善の総割引額」が完成しているとして、 のように更新していくようなやり方です。 負の配列インデックスをアクセスするなどの、おかしな挙動を招かないよう、考察や実装に注意をし ましょう。計算量は です。 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 8
9. 問題 C. Yokan Factory ★×3 あなたはようかん工場を所有しており、様々なサイズのようかんを生産しています。 工場の他に 箇所のようかん倉庫があって、倉庫を経由してようかんを輸送しています。倉庫間 は 本の双方向に行き来できる道路で繋がっています。 道路 は 倉庫 と倉庫 を繋いでいて、移動するには所要時間 がかかります。 また、道路の幅は です。 品質管理の観点から、総所要時間が を超えるようなようかんの輸送はできません。また、輸送 時に通る道路の幅を超えるような大きさのようかんを輸送することはできません。 あなたは倉庫 から倉庫 まで輸送できるようなようかんを作ろうと考えています。このとき、 輸送できるようかんはなるべく大きいほうが嬉しいです。 輸送時の総所要時間が を超えないように倉庫 から倉庫 まで運ぶことのできる、ようかんの 大きさの最大値を求めてください。 制約: 入力はすべて整数 すべての について、 すべての倉庫は連結 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 9
10. 解説 C. Yokan Factory ★×3 「時間内に運ぶことのできる『ようかん』の大きさを ～ の範囲で二分探索」 「指定された大きさの『ようかん』を運ぶ最短経路の 所要時間を調べるダイクストラ法」 の組み合わせで解くことができます。計算量は です。 (コード例: PyPy3) import heapq N, M, X = map(int,input().split()) G = [[] for _ in range(N + 1)] for _ in range(M): u, v, a, b = map(int,input().split()) G[u].append((v, a, b)) G[v].append((u, a, b)) def d(m): H = [(0, 1)] F = [False] * (N + 1) D = [X + 1] * (N + 1) D[1] = 0 while H: t, i = heapq.heappop(H) if i == N: return t <= X if F[i]: continue F[i] = True for j, a, b in G[i]: t2 = t + a if m > b or t2 > X or D[j] <= t2: continue D[j] = t2 heapq.heappush(H, (t2, j)) return False l, r = -1, 10 ** 9 + 1 while r - l > 1: m = (l + r) // 2 l, r = (m, r) if d(m) else (l, m) print(l) yukicoder contest 398 解説 2023-07-21 VRC競プロ部 10
11. 問題 D. At least K-characters ★×3 英小文字からなる長さ の文字列 が与えられます。 英小文字からなる長さ 以下の文字列であって以下の条件を満たす文字列の個数を、 で割ったあまりを出力してください。 辞書順で よりも真に小さい 文字列中に 種類以上の文字が出現する 制約: は整数 は英小文字からなる長さ の文字列 yukicoder contest 398 解説 2023-07-21 辞書順とは？ つの文字列 が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で であると言います。 かつ は の 番目から 番目までの部分文字列と一致する。 が存在し、 について、 と の 文字目は等しく、 の 文字目は の 文 字目よりアルファベット順で真に小さい。 かつ のとき、 は よりも辞書順で真に小さい（ ）と言います。 “ “ VRC競プロ部 11
12. 解説 D. At least K-characters ★×3 : の先頭から 番目の文字 : の先頭から 番目までの連続部分文字列 : に含まれる文字種の集合 : の集合に含まれる要素の数 長さ で、辞書順で より真に小さく、 種類の文字を含む文字列の個数 とする動的 計画法を考えます。 のとき、 への遷移は以下のようなものが考えられます。 となる文字列に、 種類の文字を加えた文字列を作る : 通り となる文字列に、 種類の文字を加えた文字列を作る : 通り のとき、 に、 より真に小さな文字 を加えた文字列を作る より小さく にある文字の種類の数だけ に加える より小さく にない文字の種類の数だけ に加える より真に小さな文字列の数は、以下の2つの和になります。計算量は文字の種類数を として です。 となる の合計 かつ が成り立つ 整数 の数 の時、 となるため は より真に小さな文字列ではない事に注意 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 12
13. N, M, K = map(int, input().split()) S = input() ORDA, kbits, kbc, result = ord('a'), 0, 0, 0 dp = [0] * 28 for i in range(M): ndp = [0] * 28 for j in range(1, 27): ndp[j] = ((27 - j) * dp[j - 1] + j * dp[j]) % 998244353 if i < N: ci = ord(S[i]) - ORDA cib = 1 << ci same = (kbits & (cib - 1)).bit_count() ndp[kbc] += same ndp[kbc + 1] += ci - same if (kbits & cib) == 0: kbits |= cib kbc += 1 if kbc >= K: result += 1 for j in range(K, 27): result += ndp[j] dp = ndp if kbc >= K: result -= 1 print(result % 998244353) コード例 D. At least K-characters ★×3 (PyPy3) ORDA : 英小文字 a のASCIIコード kbits : の2進数表現 kbc : ci : より真に小さい英小文字の 数 cib : の2進数表現 same : に含まれ、 よ り真に小さい英小文字の数 ci - same : に含まれない、 より真に小さい英小文字の数 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 13
14. 問題 E. Cheating Code Golf ★×3 VR Code Golf Contestでは、 問の問題に対してプログラムのソースコードをそれぞれ提出し、問題を正解 することができたソースコードの短さを競います。 このコンテストでは、全ての問題の合計で 回まで不正解の提出をしてよいです。不正解の提出の回数の合 計が 回を超えると、以降は全ての問題に対して提出することができなくなります。 また、一度正解した問題に対して再提出をすることはできません。 文字のソースコードで問題を正解した場合、その問題に不正解の提出をした回数にかかわらず、提出者は得 点 を得ることができます。 羊くんは、このコンテストで乱択を用いた不正を行うことにしました。 羊くんは、 問目 の問題に対して、乱択を用いずに確率 で正解できる 文字のソースコード と、乱択を用いて確率 で正解できる 文字のソースコードを持っています。 ここで、乱択を用いたコードが正解となるか不正解となるかは各提出ごとに独立に決められます。また、 回 提出するごとに正解か不正解かを確認することが出来ます。 以下の条件を満たすように提出するソースコードを決めていったとき、得られる得点の合計の期待値を求めて ください。 乱択を用いた提出が全て不正解になったとしても、全問正解できる。 上記を満たす方法のうち、得られる得点の合計の期待値が最大になる。 制約: 入力は全て整数 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 14
15. 解説 E. Cheating Code Golf ★×3 それぞれの問題を既に正解した/していない事を示す 通りの集合の状態と、あと何回不正解でき る状態かを、 DP (動的計画法) の一種である bit DP にて解きます。 ( に含まれる問題を正解しておらず、あと 回まで不正解の提出をしてもよいとき、 に 含まれる問題を全て正解して得られる得点の合計の期待値の最大値) とおきます。 このとき、答えは です。 DPの遷移は、以下のようになります。 は、 から を除いた集合を示します。(差集合) 計算量は になります。 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 15
16. N, M = map(int, input().split()) ABP = [[1./v for v in map(int,input().split())] for _ in range(N)] dp = [-float('inf')] * 4096 full_bit = (1 << N) - 1 for _ in range(M + 1): ndp = dp.copy() ndp[0] = 0. for i in range(1, N + 1): bi = (1 << i) - 1 while bi <= full_bit: s = 0. pi = bi while pi > 0: pbit = pi & -pi pidx = (pbit - 1).bit_length() dpi = bi ^ pbit a, b, p = ABP[pidx] s = max(s, ndp[dpi] + a, (ndp[dpi] + b) * p + dp[bi] * (1. - p)) pi &= pi - 1 ndp[bi] = max(ndp[bi], s) x = bi & -bi y = bi + x bi = ((bi & ~y) >> x.bit_length()) | y dp = ndp print(dp[full_bit]) コード例 E. Cheating Code Golf ★×3 (PyPy3) pi & -pi : pi を2進数表記 した時の最も下の 1 が立 った桁を取り出す dpi = bi ^ pbit : bi に対 し、 pbit の 1 が立った 桁をビット反転した値を dpi とする pi &= pi - 1 : pi を2進数 表記した時に、最も下の 1 が立った桁を 0 に変える x = bi & -bi y = bi + x bi = ((bi & ~y) >> x.bit_length()) | y : bi を2進数表記した時 に、 1 が立っている桁の 数が同じで、かつ bi より も大きい中で最小の整数を 生成 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 16
17. 問題 F. Udon Coupon (Hard) ★×3.5 あるうどん屋では、「うどん札」をいくつか使うことで、割引を受けることができます。 割引の受け方は、以下の 種類です。 「うどん札」を 枚使って、 円の割引を受ける 「うどん札」を 枚使って、 円の割引を受ける 「うどん札」を 枚使って、 円の割引を受ける これらの割引は、「うどん札」があれば何度でも受けられますが、使った「うどん札」は消費されま す。 さて、みどりさんは「うどん札」を使って、できるだけたくさんの割引を受けたいと考えました。 「うどん札」が 枚ある時、割引額の合計の最大値 を求めてください。 制約: 入力は全て整数 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 17
18. 解説 F. Udon Coupon (Hard) (1/3) とします。 (割引額/使用枚数 の効率が最大のものの一つを とする) 総割引額 を最大化した時の 個目の割引を使った回数を とします。 以下の考察より、貪欲に置き換えることで として考えても良い事が分かります。 であれば を 増やして を 減らしても総割引額 は悪化しない 消費枚数の増減は 番目・ 番目ともに 枚、割引額は 増加・ 減少 であれば を 増やして を 減らしても総割引額 は悪化しない 消費枚数の増減は 番目・ 番目ともに 枚、割引額は 増加・ 減少 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 18
19. 解説 F. Udon Coupon (Hard) (2/3) yukicoder contest 398 解説 2023-07-21 VRC競プロ部 19
20. 解説 F. Udon Coupon (Hard) (3/3) 以下の2通りの実装例を紹介します。前者は計算量 、後者は計算量 です。 より、 枚のうどん券がある時の最善の割引額 をDPで求めたものと、残り 回だけ 番目の割引に使った割引額を合計 を求める yukicoder contest 398 解説 2023-07-21 VRC競プロ部 20
21. 枚 だけ DP で (PyPy3) N = int(input()) A1, B1 = map(int,input().split()) A2, B2 = map(int,input().split()) A3, B3 = map(int,input().split()) if A2 * B1 < A1 * B2: A1, B1, A2, B2 = A2, B2, A1, B1 if A3 * B1 < A1 * B3: A1, B1, A3, B3 = A3, B3, A1, B1 c1min = max(N // A1 - A2 - A3, 0) dplen = N - c1min * A1 r = 0 dp = [0] * (dplen + 1) for i in range(dplen + 1): dp[i] = r = max( dp[i - A1] + B1 if i >= A1 else 0, dp[i - A2] + B2 if i >= A2 else 0, dp[i - A3] + B3 if i >= A3 else 0, r, ) print(r + c1min * B1) を全探索 (Python3/PyPy3) N = int(input()) A1, B1 = map(int,input().split()) A2, B2 = map(int,input().split()) A3, B3 = map(int,input().split()) if A2 * B1 < A1 * B2: A1, B1, A2, B2 = A2, B2, A1, B1 if A3 * B1 < A1 * B3: A1, B1, A3, B3 = A3, B3, A1, B1 print( max( t // A1 * B1 + p + q for p, s in zip(range(0, A1 * B2, B2), range(N, -1, -A2)) for q, t in zip(range(0, A1 * B3, B3), range(s, -1, -A3)) ) ) コード例 F. Udon Coupon (Hard) (PyPy3) yukicoder contest 398 解説 2023-07-21 VRC競プロ部 21
22. 問題 G. SAN 値チェック ★×4 正整数 が与えられます。 あなたは実数 を持っています。はじめ、 となっています。あなたは以下の操作を が 以上である間繰り返します。 以上 以下の実数を 個一様ランダムに選んで から引く。 このとき操作回数の期待値を と置くと、長さ の有理数列 であって を満たすものが一意に存在します。ただし、 はネイピア数です。 に対して、 を求めてください。 制約: は整数 yukicoder contest 398 解説 2023-07-21 有理数 の定義 は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 で表 した時、 となることも証明できます。よって、 を満たす整数 が一意に定まります。この を答えてください。 “ “ VRC競プロ部 22
23. 解説 G. SAN 値チェック 回操作をしてもまだ が 以上である確率を に対して足し合わせた値が です。 回操作をしてもまだ が 以上である確率は、 次元空間で以下を満たす点 の集合の体積に等しいです。 さて、この体積を包除原理で求めましょう。 という条件は固定して、 に対して包除原理を適用します。 個の index がこの条件を満たさないとすると、条件は以下のように置き換わります。 この部分の体積は です。これは という 個の点が 以上 以下の部分にこの順番に 並んでいるということから分かります。 よって、これを を動かすことで であることが分かります。 よって、 です。この値を計算することでこの問題を で解くことが出来ます。 yukicoder contest 398 解説 2023-07-21 VRC競プロ部 23
24. N = int(input()) MOD = 998244353 fact = 1 for i in range(1, N + 1): fact = fact * i % MOD rev = pow(fact, MOD - 2, MOD) for i in range(N + 1): print(pow(-i, N - i, MOD) * rev % MOD) rev = rev * (N - i) % MOD コード例 G. SAN 値チェック (Python3/PyPy3) fact : rev : yukicoder contest 398 解説 2023-07-21 VRC競プロ部 24
25. VRC競プロ部 案内 主に土曜23時頃~ (AtCoder Beginner Contest (ABC) 開催日) ABC感想会 AtCoder Beginner Contest にリアルタイムで参加 した人たちで集まって、 VRC競プロ部 Group+ イ ンスタンスにてわいわいと感想会をやっていま す。初めての方は Discord / VRChat Group に参加 しておいた方がスムーズだと思います。 Discord: https://discord.gg/VDQMrAb VRChat Group (要ログイン): https://vrc.group/PROCON.7592 主に日曜夜 (コンテストがない週): テーマ別勉強会 2023-06開催 SECCON Beginners CTF 2023 に VRC-procon チームで参加 (20位) yukicoder contest 398 解説 2023-07-21 VRC競プロ部