あるぱかのブログ

AtCoder茶(レート566)

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）

8月ABC全休

atcoder.jp

 

A - Raise Both Hands

L,Rが与えられ、 Lのみ1ならばYes、 Rのみ1ならNo、両方とも同じ数値ならInvalidを返します。

3つのパターンの条件分けをすることでACできます。

#ABC370 A - Raise Both Hands
L, R = map(int, input().split())
if L==1 and R==0:
    print('Yes')
elif L==0 and R==1:
    print('No')
else:
    print('Invalid')  

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

B - Binary Alchemy

今所持している元素と次にもってくる元素を保持します。

所持している元素番号と次の元素番号を比較して、小さいほうを今所持しているほうに置き換えます。

これを指示された回数繰り替えします。

#ABC370 B - Binary Alchemy
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
now = 0
for i in range(N):
    nxt = i
    if now < nxt:
        now, nxt = nxt, now
    now = A[now][nxt]-1
print(now+1)  

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

C - Word Ladder

文字を置き換えることで辞書順にどのような影響があるかを考えます。

Sを左から見ていって S_iから T_iに置き換えることで辞書順が改善する場合は採用、悪化する場合は据え置きとします。

Sの右端までいったら今度は右から左に向かってみていき、 S_iと T_iが異なる場合は文字を置き換えていくこととします。

こうすることで置き換えた文字列を連結したときに辞書順が最善になります。

#ABC370 C - Word Ladder
S = input()
T = input()
N = len(S)
ans = []
now = []
for s in S:
    now.append(ord(s))
for i in range(N):
    if S[i] > T[i]:
        now[i] = ord(T[i])
        out = ''
        for j in range(N):
            out += chr(now[j])
        ans.append(out)
for i in range(N-1, -1, -1):
    if now[i] != ord(T[i]):
        now[i] = ord(T[i])
        out = ''
        for j in range(N):
            out += chr(now[j])
        ans.append(out)
print(len(ans))
for a in ans:
    print(a)

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

D - Cross Explosion

2次元盤面を作って愚直に試行するとTLEするので効率のいい方法を検討します。

盤面の縦方向の残存する壁位置を持った配列と、横方向の残存する壁位置を持った配列を保持することにします。

爆弾を投下する位置に壁がある場合は壁を破壊して終了。

無い場合は上下左右それぞれで一番近い壁を二分探索して破壊します。

二分探索するので配列は常に昇順を保っていたいのでSortedSetを使用します。

（sortedcontainersは配列内のランダムアクセスに弱い？のでtatyam Setを使います）

 #ABC370 D - Cross Explosion
---tatyam Setを貼り付け---
def bsleft(A, N): #自身以下の最大
    l = 0
    r = len(A)-1
    if A[r] <= N:
        return r
    if A[0] > N:
        return -1
    ans = 0
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] <= N:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
def bsright(A, N): #自身以上の最小
    l = 0
    r = len(A)-1
    if A[r] < N:
        return -1
    if A[0] >= N:
        return 0
    ans = r
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] >= N:
            ans = mid
            r = mid
        else:
            l = mid
    return ans
H, W, Q = map(int, input().split())
tate = [SortedSet([i for i in range(H)]) for _ in range(W)]
yoko = [SortedSet([i for i in range(W)]) for _ in range(H)]
wall = H*W
for _ in range(Q):
    r, c = map(int, input().split())
    r -= 1
    c -= 1
    if r in tate[c] or c in yoko[r]:
        wall -= 1
        tate[c].discard(r)
        yoko[r].discard(c)
    else:
        if tate[c]:
            lt = bsleft(tate[c], r)
            if lt >= 0:
                wall -= 1
                bb = tate[c][lt]
                tate[c].discard(bb)
                yoko[bb].discard(c)
        if tate[c]:
            rt = bsright(tate[c], r)
            if rt >= 0:
                wall -= 1
                bb = tate[c][rt]
                tate[c].discard(bb)
                yoko[bb].discard(c)
        if yoko[r]:
            ly = bsleft(yoko[r], c)
            if ly >= 0:
                wall -= 1
                bb = yoko[r][ly]
                yoko[r].discard(bb)
                tate[bb].discard(r)
        if yoko[r]:
            ry = bsright(yoko[r], c)
            if ry >= 0:
                wall -= 1
                bb = yoko[r][ry]
                yoko[r].discard(bb)
                tate[bb].discard(r)
print(wall)

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

 

日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

rated

atcoder.jp

A - Glutton Takahashi

リンク：A - Glutton Takahashi (atcoder.jp)

概要：甘い料理を2連続食べるとギブアップします。すべての料理を食べきれるか判定してね。

"sweet"と"salty"の2種類が入力として与えられるので"sweet"が2連続で出現したときにギブアップします。

ここでは前回食べた料理をpreに記録し、今から食べる料理sと2つ続けて"sweet"が来たらギブアップしています。

（コンテスト中は食べられる料理の数を出力かと思って書いてた名残で変なことしてます）

#ABC364 A - Glutton Takahashi
N = int(input())
pre = input()
judge = True
if N <= 2:
    print('Yes')
    exit()
for _ in range(N-2):
    s = input()
    if pre == s == 'sweet':
        judge = False
        break
    pre = s
if judge:
    print('Yes')
else:
    print('No')  

提出リンク：A - Glutton Takahashi (atcoder.jp)

B - Grid Walk

リンク：B - Grid Walk (atcoder.jp)

概要：グリッド上を”LRUD"で与えられる指示の通り歩きます。最後の指示を終えた時の場所を教えてね

制約も厳しくないのでシミュレートします。

今いる位置を (s_i, s_j)として次に (s_i+dx, s_j+dy)に進むことにします。

指示が"U"（1つ上）なら (dx, dy)=(-1, 0)、"R"（1つ右）なら (dx, dy)=(0, 1)という風に次に進む向きを指示します。

進む先がグリッド外もしくは壁"#"ならその場にとどまるようにします。

進めるなら (s_i, s_j)を (s_i+dx, s_j+dy)に更新します。

i,jと x,yが上下どちらか混乱しないように注意が必要です。

#ABC364 B - Grid Walk
H, W = map(int, input().split())
si, sj = map(int, input().split())
si -= 1
sj -= 1
C = [input() for _ in range(H)]
X = input()
for i in range(len(X)):
    dx = 0
    dy = 0
    if X[i] == 'L':
        dy -= 1
    elif X[i] == 'R':
        dy += 1
    elif X[i] == 'U':
        dx -= 1
    elif X[i] == 'D':
        dx += 1
    if si+dx < 0 or H-1 < si+dx or sj+dy < 0 or W-1 < sj+dy:
        continue
    if C[si+dx][sj+dy] == '.':
        si += dx
        sj += dy
print(si+1, sj+1)  

提出リンク：提出 #56020261 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

C - Minimum Glutton

リンク：C - Minimum Glutton (atcoder.jp)

概要： N個の料理に甘さ A_iとしょっぱさ B_iが設定されています。甘さの合計が Xを超える、もしくはしょっぱさの合計が Yを超えるとギブアップします。料理を好きな順番で食べられる場合に食べる料理の数の最小値を出力してね。

甘さでギブアップする場合としょっぱさでギブアップする場合の2通りを考えて食べる料理の数を比較します。

甘さの配列 Aとしょっぱさの配列 Bを大きい順にソートして順に食べ、どちらかが閾値を超えたときに食べた数を出力します。

#ABC364 C - Minimum Glutton
N, X, Y = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
B = sorted(list(map(int, input().split())), reverse = True)
ama = 0
kara = 0
for i in range(N):
    ama += A[i]
    kara += B[i]
    if ama > X or kara > Y:
        break
print(i+1)  

提出リンク：提出 #56023754 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

D - K-th Nearest

リンク：D - K-th Nearest (atcoder.jp)

概要：配列 Aに対して B_iから k番目に遠い点 A_jまでの距離を Q回出力してね

点もクエリの数も多いので毎回全探索はできないので効率的な探索を考える必要があります。

探索、 k番目ということで答えで二分探索を行うとよさそうです。

以下の方針で進めます。

  • 答えを dと仮定する。 B_i-dから B_i+dの間にある Aの要素数を調べて kに対する大小を比較する。
    • B_i-d以上となる最小の A_j、 B_i+d以下となる最大の A_kを二分探索で見つける。
  • 条件を満たすなら答えに記録して dを更新し次へ

44～45行目で探索の初期値として -1と 10^{9}を設定していますが、 d=-1のときは明らかに条件を満たさない、 d=10^{9}のときは明らかに条件を満たす、というところから決めています。

要素を探す二分探索の部分はPythonならbisectが使えると思います。

（私は自分で書いたものを使っていて、範囲外の返り値がヘタクソなので場合分けをしています。）

#ABC364 D - K-th Nearest
def lower(A, N): #超えない最大
    l = 0
    r = len(A)-1
    if A[r] <= N:
        return r
    if A[0] > N:
        return -1
    ans = 0
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] <= N:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
def upper(A, N): #超える最小
    l = 0
    r = len(A)-1
    if A[r] < N:
        return -1
    if A[0] >= N:
        return 0
    ans = r
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] >= N:
            ans = mid
            r = mid
        else:
            l = mid
    return ans
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(Q):
    b, k = map(int, input().split())
    if b < A[0]:
        print(A[k-1]-b)
    elif b > A[-1]:
        print(b-A[-k])
    else:
        l = -1
        r = 10**9
        ans = 10**9
        while l+1 < r:
            mid = (l+r)//2
            left = upper(A, b-mid)
            right = lower(A, b+mid)
            num = right-left+1
            if num >= k:
                ans = min(ans, mid)
                r = mid
            else:
                l = mid
        print(ans)  

提出リンク：提出 #56139183 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

 

AtCoder Beginner Contest 363

第363回は回文回

atcoder.jp

A - Piling Up

リンク：A - Piling Up (atcoder.jp)

概要：レート100上がるごとに^の数が増えます。次に^が増えるのはレートがいくつ上がったタイミングか数えてね

現在のレートを100で割った余りを見ることで解答できます。

100から上記の余りを引いた数を出力します。

#ABC363 A - Piling Up
R = int(input())
print(100 - R%100)  

提出リンク：提出 #55882677 - AtCoder Beginner Contest 363

B - Japanese Cursed Doll

リンク：B - Japanese Cursed Doll (atcoder.jp)

概要：髪が長い上位 P番目の人形の髪の長さが T以上になるのが何日後か教えてね

どの人形も髪が伸びる速さが同じということで、スタート時点で髪が長い順に並べ替えてみます。

ソートした後で上位 T番目の人が長さ Pになるために必要な日数を出力します。

既に長さ P以上の場合は0を出力するように場合分けしています。

#ABC363 B - Japanese Cursed Doll
N, T, P = map(int, input().split())
L = sorted(list(map(int, input().split())), reverse = True)
if L[P-1] >= T:
    print(0)
else:
    print(T-L[P-1])  

提出リンク：提出 #55882731 - AtCoder Beginner Contest 363

C - Avoid K Palindrome 2

リンク：C - Avoid K Palindrome 2 (atcoder.jp)

概要：文字列を並べ替えた時に長さ Kの部分文字列が回文にならないものだけを数え上げてね

制約が N \leq 10と小さいので全探索できそうです。

itertoolsのpermutationsで全ての並びを試して都度回文判定をすることで題意を満たせそうです

・・・が、Pythonのpermutationsでは1～2ケースでTLEしてしまいます。

コンテスト後のtwitterを見るとmore_itertoolsの中のdistinct_permutationsを使うことでACできるようです。

こちらは重複のない順列のみを生成できるみたいです。

from more_itertools import distinct_permutations
def kaibun(s):
    n = len(s)
    judge = True
    for i in range(n//2):
        if s[i] != s[-1-i]:
            judge = False
            break
    return judge
N, K = map(int, input().split())
S = input()
ans = 0
for p in distinct_permutations(S):
    now = ''.join(p)
    judge = True
    for i in range(N-K+1):
        if kaibun(now[i:i+K]):
            judge = False
    if judge:
        ans += 1
print(ans)  

提出 #55870168 - AtCoder Beginner Contest 363

D - Palindromic Number

リンク：D - Palindromic Number (atcoder.jp)

概要：回文になっている数字、回文数を小さい順に並べた時 N番目の数字を教えてね

制約が大きいので探索では不可能そうなので法則を探してみます。

0を除外すると1桁の回文数は1~9の9個、2桁は11～99の9個、3桁は101～191、201～292、・・・で90個、というように桁が2個上がるごとに9、90、900、・・・と増えていくようです。

このことから Nをうまいこと処理すれば何桁の回文数になるかが分かりそうです。

次に回文数の上位の桁をみると11、12、・・・のように昇順に並んでいることがわかります。

目的となる桁数より小さい桁数で作れる回文数の総数を出しておけば、出力したい数字が何らかの方法で生成できそうです。

  • 桁数を1～40（制約内では最大35桁）で増やしながら目的の回文数の桁数に合致するか確認する。しなければ既にみた回文数の数ということでseenを加算する。
  • 桁数が分かったので回文数の上位の数を作る。
  • 桁数が奇数が偶数かに応じて適切な回文数を作って出力する。
#ABC363 D - Palindromic Number
N = int(input())
if N == 1:
    print(0)
    exit()
N -= 1
seen = 0
for i in range(1, 40):
    d = 9*pow(10, (i-1)//2)
    if N <= seen+d:
        break
    seen += d
t = str(pow(10, (i-1)//2) + (N-seen-1))
if i%2 == 0:
    ans = t + t[::-1]
else:
    ans = t + t[::-1][1:]
print(ans)  

提出リンク：提出 #55884327 - AtCoder Beginner Contest 363

 

トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

atcoder.jp

A - Buy a Pen

リンク：A - Buy a Pen (atcoder.jp)

概要：赤、青、緑の3本のペンのうち1本を除外して最も安いものの金額を出力してね

Cで除外する対象の色が与えられるので、これを除いた2つの最小値を出力します。

Cは'Red'、'Blue'、'Green'のいずれかであるので、3パターンの分岐を書く必要があります。

#ABC362 A - Buy a Pen
R, G, B = map(int, input().split())
C = input()
if C == 'Red':
    print(min(G,B))
if C == 'Blue':
    print(min(R,G))
if C=='Green':
    print(min(R,B))  

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

B - Right Triangle

リンク：B - Right Triangle (atcoder.jp)

概要：三角形の頂点の座標が与えられるので、この三角形が直角三角形かどうか判定してね

直角の判定ということでベクトルの内積を使います。

3つの頂点を仮に頂点a、頂点b、頂点cとして、 \vec{ab}・\vec{ac}=(x_b-x_a) \times (x_c-x_a)+(y_b-y_a) \times (y_c-y_a)=0であれば頂点aは直角であることが判定できます。

#ABC362 B - Right Triangle
from itertools import combinations
X = []
Y = []
for _ in range(3):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
X += X[:2]
Y += Y[:2]
for i in range(3):
    xa, xb, xc = X[i:i+3]
    ya, yb, yc = Y[i:i+3]
    if (xb-xa)*(xc-xa) + (yb-ya)*(yc-ya) == 0:
        print('Yes')
        exit()
print('No')  

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

C - Sum = 0

リンク：C - Sum = 0 (atcoder.jp)

概要：整数列 Xの各要素について値の取りうる範囲を (L_i,R_i)で与えるので、うまいこと決めて sum(X)=0にしてね

初期解決めてうまいこと値変えたいけどうまい方法が思いつかず仕舞。

頭から貪欲に決めていくことでいいみたいです。

初期解は全要素の最小値（もしくは最大値）として、合計値を0に近づけるように努力させればいいです。

  • sum(L) \gt 0もしくは sum(R) \lt 0ならば明らかに条件を満たさないのでNoを出力する
  • 初期解を Lとして、各要素について L_i～R_iの中で合計を0にできるものがあるなら採用する。なければ R_iに更新して次の要素へ
#ABC362 C - Sum = 0
N = int(input())
L = []
R = []
for _ in range(N):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
if sum(L) > 0 or sum(R) < 0:
    print('No')
    exit()
ans = L[:]
now = sum(ans)
for i in range(N):
    d = min(R[i]-L[i], -now)
    ans[i] += d
    now += d
print('Yes')
print(*ans)  

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

D - Shortest Path 3

リンク：D - Shortest Path 3 (atcoder.jp)

概要：頂点と辺に重みがある単純連結無向グラフで経路の重みの最小値を教えてね

最短経路問題ということでダイクストラ法を使います。

頂点の重みは Aで、辺の重みは bで与えられます。

辺だけでなく頂点にも重みがあるので、頂点 u_iから辺 iを通って頂点 v_iに行くときの重みを w = b_i + A_vとします。

出力するときは始点の重みを足し忘れずに。

ここまで分かってABC340くらいでつくったダイクストラ法を投げると2ケースでTLEしました。

たぶんダイクストラ法の中身で無駄な処理をしているんだと思います。

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

公式解析からダイクストラ法をもらってきてその他はそのままでACできました。もったいない。

#ABC362 D - Shortest Path 3
from heapq import heappush, heappop
def dijkstra(G, s):
    INF = 10**18
    dist = [INF] * len(G)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, v = heappop(pq)
        if d > dist[v]:
            continue
        for u, weight in G[v]:
            nd = d + weight
            if dist[u] > nd:
                dist[u] = nd
                heappush(pq, (nd, u))
    return dist
N, M = map(int, input().split())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    u, v, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, b+A[v]]) 
    G[v].append([u, b+A[u]])
d = dijkstra(G,0)
ans = []
for i in range(1, N):
    ans.append(d[i]+A[0])
print(*ans)  

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

 

デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

unrated

最近ABC奇数回に出られないがち

A - Insert 

リンク：A - Insert (atcoder.jp)

概要：整数列 Aの K番目の要素の直後に Xを入れた整数列を出力してね

整数列 Aを、 A_Kまでと A_{K+1}からの2つに分けます。

この2つの間に Xを入れて出力します。

1-indexed(問題文)と0-indexed(コード)に注意が必要です。

#ABC361 A - Insert 
N, K, X = map(int, input().split())
A = list(map(int, input().split()))
B = A[:K] + [X] + A[K:]
print(*B)  

提出リンク：提出 #55347050 - デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

B - Intersection of Cuboids

リンク：B - Intersection of Cuboids (atcoder.jp)

概要：3次元空間内の2つの立方体が重なっているか判定してね

3Dゲームの当たり判定といきなり言われて面喰いました。

3次元で考えると想像しにくいので、まずは簡単のため1次元で考えてみます。

区間 (a,b)と区間 (c,d)について、 a ＜ c＜bもしくは a＜d＜bのとき2つの区間の共通部分が正の値となります。

（ a=dのように等号のときは端のみ重なるので共通部分は0になります）

これを3次元に拡張することで正解できます。

#ABC361 B - Intersection of Cuboids
a, b, c, d, e, f = map(int, input().split())
g, h, i, j, k, l = map(int, input().split())
judge = True
if j <= a or g >= d:
    judge = False
if k <= b or h >= e:
    judge = False
if l <= c or i >= f:
    judge = False
if judge:
    print('Yes')
else:
    print('No')  

提出リンク：提出 #55347181 - デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

C - Make Them Narrow

リンク：C - Make Them Narrow (atcoder.jp)

概要：数列 Aから K要素消したときの最大値と最小値の差 A_{max}-A_{min}を最小化してね

問題文では順序を保ってとありますが実際は順序を保つ必要は無いです。

（最大値と最小値にしか興味がないため）

Aをソートした上で両端から合わせて K要素を消す、つまり N-Kの連続した要素を残すことで正解できます。

まとめると以下の方針となります。

  • Aをソートする
  • A_iから A_{i+(N-K)}を取り出して最大値( A_{i+(N-K)})と最小値( A_i)の差を計算し、最小値を保持する
#ABC361 C - Make Them Narrow
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
d = N-K-1
i = 0
ans = 10**18
while i+d < N:
    now = B[i+d] - B[i]
    ans = min(ans, now)
    i += 1
print(ans)  

提出リンク：提出 #55347712 - デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

D - Go Stone Puzzle

リンク：D - Go Stone Puzzle (atcoder.jp)

概要：2つ連続した空きマスを使って碁石を並べ替えて目的の並びを作ってね

ハノイの塔っぽい問題です。

制約が N \leq 14なので何やっても間に合いそうな気がするので何らかの方法で全探索します。

まず Sに'..'を付け足して初期状態を作り、実際に入れ替え操作をします。

入れ替えの関数として下図のように A_xから2要素と A_yから2要素をスワップするものを用意しておくといいです。

全探索の方法はBFSで、スワップした回数と文字列を保持するようにします。

まとめると

  • Sに'..'を付け足して初期状態を作る
  • '..'と任意の連続2文字を入れ替える操作を行い、入れ替えた回数と文字列を記録するBFSを行う
  • 探索の中で目的の文字列と一致した場合は入れ替え回数を出力して終了
  • すべて探索し終えても目的の文字列が現れなかった場合は-1を出力
#ABC361 D - Go Stone Puzzle
#解説
from collections import deque
def f(s,x,y):
    if x < y:
        new = s[:x] + s[y:y+2] + s[x+2:y] + s[x:x+2] + s[y+2:]
    if x > y:
        new = s[:y] + s[x:x+2] + s[y+2:x] + s[y:y+2] + s[x+2:]
    return new
N = int(input())
S = input() + '..'
T = input() + '..'  
q = deque()
q.append((0,S))
seen = set()
seen.add(S)
while q:
    t, s = q.popleft()
    if s == T:
        print(t)
        exit()
    for i in range(N+1):
        p = s.index('.')
        if i < p-1 or p+1 < i:
            nxt = f(s,p,i)
            if nxt in seen:
                continue
            else:
                seen.add(nxt)
                q.append((t+1,nxt))
print(-1)  

提出リンク：提出 #55349389 - デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

 

AtCoder Beginner Contest 360

久々に気持ちよく勝った（？）ので書きます

atcoder.jp

A - A Healthy Breakfast

リンク：A - A Healthy Breakfast (atcoder.jp)

概要： R,M,Sからなる文字列で R,Mの順番を見て何かしら出力してね

  • 文字列に対してindex()でその文字の位置を調べる
  • index('R')とindex('M')を比べてindex('R')のほうが小さい（Rのほうが左にある）場合はYesを出力する
#ABC360 A - A Healthy Breakfast
S = input()
if S.index('R') < S.index('M'):
    print('Yes')
else:
    print('No')  

提出リンク：提出 #55046050 - AtCoder Beginner Contest 360

B - Vertical Reading

リンク：B - Vertical Reading (atcoder.jp)

概要：文字列 Sを分割して拾ってつくった文字列が文字列 Tと一致するか調べてね

A～D問題の中で一番苦戦した。

計算量気にせず書いてあることを実装すればOKだけどfor文がややこしくなって大変だった。

以下の順にfor文をネストする。

  • 文字列 Sを w文字ごとに区切ることを決める（関数fを定義して実際に区切りました）
  • 区切った文字列で c文字以上の文字列を見ることに決める
  • 区切った文字列を順番に見ていって c文字目を拾い集める
#ABC360 B - Vertical Reading
def f(s, n):
    ans = []
    while len(s) >= n:
        ans.append(s[:n])
        s = s[n:]
    if s != '':
        ans.append(s)
    return ans
S, T = map(str, input().split())
N = len(S)
for w in range(1, N):
    now = f(S, w)
    for c in range(w):
        s = ''
        for i in range((N+w-1)//w):
            try:
                s += now[i][c]
            except:
                break
        if s == T:
            print('Yes')
            exit()
print('No')      

提出リンク：提出 #55081290 - AtCoder Beginner Contest 360

C - Move It

リンク：C - Move It (atcoder.jp)

概要：同じ箱に入っている荷物を一番重いものが残るように操作してね

典型ど真ん中みたいな問題で安心。BよりCのほうが正答率高いの面白い。

全ての箱に1つずつ荷物を残すということで、箱の中にある荷物を軽い順に取り出す貪欲をやります。

  • defaultdictにlistを持たせて箱の番号と中身の重さを管理
  • 箱の中身の個数によって処理を変えるのが面倒なので、すべて取り出して一番重いものを戻す処理にする
#ABC360 C - Move It
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
W = list(map(int, input().split()))
box = defaultdict(list)
for i in range(N):
    box[A[i]].append(W[i])
ans = 0
for key in box:
    if len(box[key]) > 1:
        ans += sum(box[key])
        ans -= max(box[key])
print(ans)  

提出リンク：提出 #55063033 - AtCoder Beginner Contest 360

D - Ghost Ants

リンク：D - Ghost Ants (atcoder.jp)

概要：蟻が数直線上をトコトコするのですれ違う組数をカウントしてね

以下の処理を二分探索を使って高速に処理します。

自身を越える最小値と、自身を越えない最大値を探索するコードをライブラリ化しておくと便利です（ABC353-C、ABC355-Dで出たのに今回のコンテスト後やっとライブラリ化しました）。

本番中は丹精込めた手打ちで盛大にバグらせてWA。

  • 右向きと左向きでグループ分けする
  • 右向きグループに着目して、初期の座標と終了時（初期+2T）の間にいる左向きの蟻の数をカウントする
def upper(A, N): #超えない最大
    l = 0
    r = len(A)-1
    if A[r] <= N:
        return r
    if A[0] > N:
        return -1
    ans = 0
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] <= N:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
def lower(A, N): #超える最小
    l = 0
    r = len(A)-1
    if A[r] < N:
        return -1
    if A[0] >= N:
        return 0
    ans = r
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] >= N:
            ans = mid
            r = mid
        else:
            l = mid
    return ans
N, T = map(int, input().split())
S = input()
X = list(map(int, input().split()))
right = []
left = []
for i in range(N):
    if S[i] == '1':
        right.append(X[i])
    else:
        left.append(X[i])
right = sorted(right)
left = sorted(left)
ans = 0
for i in range(len(right)):
    l = lower(left, right[i])
    r = upper(left, right[i]+2*T)
    if l >= 0 and r >= 0 and l <= r:
        ans += (r-l+1)
print(ans)  

提出リンク：提出 #55112663 - AtCoder Beginner Contest 360

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

都合により不参加

atcoder.jp

A - Sanitize Hands

リンク：A - Sanitize Hands (atcoder.jp)

概要：宇宙人の手を消毒しよう！

いくつか方針が考えられますが、私は以下で解きました。

  • 宇宙人の手の本数で累積和をつくる
  • 累積和を順に見ていって消毒液のほうが多い場合は答えを更新する
  • その地点の一つ前を出力する

他にはwhile文で消毒液を消費していって量がマイナスになったら答え出力とかできそうです。

#ABC357 A - Sanitize Hands
N, M = map(int, input().split())
H = list(map(int, input().split()))
s = 0
ruiseki = [0]
for i in range(N):
    s += H[i]
    ruiseki.append(s)
ans = 0
for i in range(N+1):
    if ruiseki[i] <= M:
        ans = max(i, ans)
print(ans)  

提出リンク：提出 #54457944 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

B - Uppercase and Lowercase

リンク：B - Uppercase and Lowercase (atcoder.jp)

概要：文字列 Sの小文字と大文字の数を比較してね

pythonではisupper・islowerで大文字・小文字を判定できます。

またS.upper()で文字列 Sを大文字に変換できます。

#ABC357 B - Uppercase and Lowercase
S = input()
small = sum(map(str.islower, S))
large = sum(map(str.isupper, S))
if small > large:
    ans = S.lower()
else:
    ans = S.upper()
print(ans)  

提出リンク：提出 #54458028 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

C - Sierpinski carpet 

リンク：C - Sierpinski carpet (atcoder.jp)

概要：独特な模様のカーペットをつくろう

再帰で解けそうな気がしましたが辛くなったので周期性を探しました。

レベル1のときは中心(1,1)だけ白になります。

レベル2のときは中心(4,4)まわりの3×3マスが白くなります。

レベル3のときは中心(13,13)まわりの9×9マスが白くなります。

中心座標を見ると1, 1+3, 1+3+9,……のように3進数が見えてきます。

方針として以下のようにしました。

  • n=1, 2,……の順にみる。
  • 中心点のためにs =  \displaystyle \sum_{k=1}^{n} 3^{k}を計算する。また前回の値をpreとして保持しておく。
  • 中心点まわりの(-pre, +pre)の範囲を白く塗る。

これが灰diffってマジですか・・・いや問題文通りの実装なんだけども

#ABC357 C - Sierpinski carpet
N = int(input())
if N == 0:
    print('#')
    exit()
carpet = [[0 for _ in range(3**N)] for _ in range(3**N)]
s = 0
for n in range(1, N+1):
    pre = s
    s += 3**(n-1)
    for i in range(s, 3**N, 3**n):
        for j in range(s, 3**N, 3**n):
            for dy in range(-pre, pre+1):
                for dx in range(-pre, pre+1):
                    carpet[i+dx][j+dy] = 1
for i in range(3**N):
    out = ''
    for j in range(3**N):
        if carpet[i][j] == 0:
            out += '#'
        else:
            out += '.'
    print(out)  

提出リンク：提出 #54481731 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

D - 88888888

リンク：D - 88888888 (atcoder.jp)

概要：整数 Nを N個つなげた数 V_Nを998244353で割った数を出力してね

V_Nは等比級数の和として表すことができます。

具体的には Nの桁数を kとすると V_N = N \times \dfrac {10^{k \times N}-1}{10^{k}-1}で表せます。

また \dfrac {a}{b}mod(M)は a(mod(M)) \times b^{M-2}(mod(M))で表すことができます。

鍵となるのは 10^{k \times N}の高速な計算だと思います。

pythonではpow()で繰り返し二乗法による高速な計算が使え、またpow()の第3引数を使うと都度modをとってくれます。

方針をまとめると下記になります。

  • V_Nを等比級数の和として表現する
  • フェルマーの小定理より割り算modを掛け算の形で計算する
  • pow()で桁数の多いべき乗計算を高速に行う。同時にmodをとる
#ABC357 D - 88888888
N = int(input())
k = len(str(N))
mod = 998244353
a = pow(10, k*N, mod)-1
b = pow(10**k - 1, mod-2, mod)
ans = (N*a*b)%mod
print(ans)  

提出リンク：提出 #54461153 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）