あるぱかのブログ

AtCoder茶(レート566)

東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

atcoder.jp

A - Who Ate the Cake? 

リンク:A - Who Ate the Cake? (atcoder.jp)

概要:2人の証言をもとに3人のうちだけがケーキをたべたか特定して教えてね

人1,2,3のうち言及されていない人を出力します。

特定不可能( A=B)のときは-1を出力します。

特定できるときは 6-A-Bを出力すればOKです。

#ABC355 A - Who Ate the Cake?
A, B = map(int, input().split())
if A == B:
    print(-1)
else:
    print(6 - (A+B))  

提出リンク:提出 #53827194 - 東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

B - Piano 2

リンク:B - Piano 2 (atcoder.jp)

概要:配列 A Bを足してソートした配列 Cの中で Aの要素が2つ以上連続するかどうか判定してね

色々やり方があるとは思いますが、私は A,Bそれぞれについて (A_i, 0) (B_i, 1)の形で要素を取り出して Cに加えました。

ソートした Cを順番に見ていって C_{i,1}=C_{i+1,1}=0である場所が1つでもあればYesというふうに実装しました。

#ABC355 B - Piano 2
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = []
for i in range(N):
    C.append((A[i], 0))
for i in range(M):
    C.append((B[i], 1))
C = sorted(C)
for i in range(N+M-1):
    if C[i][1] == C[i+1][1] == 0:
        print('Yes')
        exit()
print('No')  

提出リンク:提出 #53839679 - 東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

C - Bingo 2

リンク:C - Bingo 2 (atcoder.jp)

概要:左上から昇順で数字が並んだビンゴがあるので何ターン目にビンゴできたか教えてね

制約はビンゴの1辺のマス数 N=3\times10^{3}、読み上げる数字の数 T=min(N^{2},2\times10^{5}です。

ポイントはビンゴの判定方法になりそうです。

マス目上を何らかの方法で探索してビンゴ判定するためには毎ターン O(N^{2})必要になりそうなので N^{2}マスをあらかじめ作成して読み上げた数字を入れて都度都度ビンゴ判定は無理そうです。

結局のところビンゴになったかどうか判定すべきなのは今読み上げられた数字のマス目の上下(+斜め)になるので、これに絞ればあれば毎ターン O(1)で判定できそうに思います。

数字が左上から昇順で並んでいるため、今読み上げられた数字が縦横どこにあるかは簡単に計算できます。

判定方法として横1列目、横2列目、・・・、縦1列目、縦2列目・・・、斜め下方向、斜め上方向に入った数字を管理する空のリストを作っておき、数字が入ったときにリストの長さが Nになったかどうか見ることにしました。

#ABC355 C - Bingo 2
N, T = map(int, input().split())
A = list(map(int, input().split()))
if N > T:
    print(-1)
    exit()
yoko = [[] for _ in range(N)]
tate = [[] for _ in range(N)]
naname = [[] for _ in range(2)]
for t in range(T):
    a = A[t] - 1
    i = a // N
    j = a % N
    tate[i].append(a)
    yoko[j].append(a)
    if i == j:
        naname[0].append(a)
    if i == N-1-j:
        naname[1].append(a)
    if len(tate[i]) == N:
        print(t+1)
        exit()
    if len(yoko[j]) == N:
        print(t+1)
        exit()
    if len(naname[0]) == N:
        print(t+1)
        exit()
    if len(naname[1]) == N:
        print(t+1)
        exit()
print(-1)  

提出リンク:提出 #53866236 - 東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

D - Intersecting Intervals

リンク:D - Intersecting Intervals (atcoder.jp)

概要:区間 l_i,r_i N回与えられるので区間が重なる組み合わせ数を出力してね

区間 l_iでソートした後に二分探索すればいいことに開始80分くらいで気づいて急いで実装しました。

ABC353-Cと同じようなことですね。

 N = int(input())
pos = []
for i in range(N):
    l, r = map(int, input().split())
    pos.append((l, r))
pos = sorted(pos)
count = 0
for i in range(N-1):
    l1 = pos[i][0]
    r1 = pos[i][1]
    left = min(i+1, N-1)
    right = N-1
    while left+1 < right:
        mid = (left + right) // 2
        l2 = pos[mid][0]
        r2 = pos[mid][1]
        if l2 > r1:
            right = mid
        else:
            left = mid
    if pos[left][0] <= r1:
        if pos[right][0] <= r1:
            count += right - i
        else:
            count += left - i
print(count)  

提出リンク:提出 #53888965 - 東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

結果

初めての4完でした。

D問題が茶diff中位くらいな気がするので運がよかったです。

鉄則本や典型90問のおかげで典型問題はだいぶ立ち向かえるのになったので、最近はAtcoderDailyTrainingにバーチャル参加してA問題相当~D問題相当を時間を意識して解く取り組みをしています。

過去問で問題文を典型手法に落とし込む部分の練習と、考察時間を短くする練習になりそうです。