自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型90問:014 - We Used to Sing a Song Together(★3)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_n

挑戦結果

  • 結果:できた
  • 時間:3分

考えたこと

  • 小学生も学校も、左から順番にペアを組むのが最短になりそうと思った

公式解説

https://twitter.com/e869120/status/1382478816627478530/photo/1

解説を読んだふりかえり

  • なんとなく正しそうという状態で解いてしまったが、証明を読んで見ればそうかと思った。

ソース

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

A.sort()
B.sort()
sum = 0
for i in range(N):
    sum += abs(A[i] - B[i])

print(sum)

競プロ典型90問:012 - Red Painting(★4)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_l

挑戦結果

  • 結果:できなかった
  • 時間:30分ぐらい

考えたこと

  • 囲碁っぽくやること。TLEした・・・。

公式解説

  • UnionFindを思い出したし、以前にライブラリ化もしていた。

解説を読んだふりかえり

  • UnionFindでやったらサクッとできた。
  • ただし、UnionFindの高速化はやってないので、どこかで対応したほうが良さそう。

ソース

H, W = [int(x) for x in input().split()]
Q = int(input())

############################################
# Union Find 
# N = 100
N = (H+2) * (W+2)
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
############################################

# 盤面が赤になっているか
B = [False] * N
# 2次元を1次元に変換
def rc2p(r,c):
    return (W+2)*r + c

# 1のクエリ(色を塗る)
def query1(r,c):
    pU = rc2p(r+1,c)
    pD = rc2p(r-1,c)
    pR = rc2p(r,c+1)
    pL = rc2p(r,c-1)
    p = rc2p(r,c)
    B[p] = True
    if B[pU]: unite(p,pU)
    if B[pD]: unite(p,pD)
    if B[pR]: unite(p,pR)
    if B[pL]: unite(p,pL)

# 2のクエリ(判定)
def query2(r1,c1, r2,c2):
    ans = "No"
    p1 = rc2p(r1,c1)
    p2 = rc2p(r2,c2)
    if same(p1,p2) and B[p1] and B[p2]:
        ans = "Yes"
    print(ans)

# メイン部分
for _ in range(Q):
    q = input().split()
    if q[0]=="1":
        query1(int(q[1]), int(q[2]))
    else:
        query2(int(q[1]), int(q[2]),int(q[3]), int(q[4]))

競プロ典型90問:010 - Score Sum Queries(★2)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_j?lang=ja

挑戦結果

  • 結果:解けた
  • 時間:20分ぐらい

考えたこと

  • 愚直は計算量がNGなんだろうと思った。累積和なことは思いついた。
  • クラスがあるからどう扱えばいいかと思ったけど、それぞれ累積和を持てば良さそう気がついた

公式解説

https://twitter.com/e869120/status/1380652465834532865

解説を読んだふりかえり

  • 特になし。★2なのでサクッとときたい。

ソース

N = int(input())
C, P = [], []
for _ in range(N):
    c, p = [int(x) for x in input().split()]
    C.append(c)
    P.append(p)
Q = int(input())
L, R = [], []
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    L.append(l)
    R.append(r)

# 累積和をクラス別に計算する
ruiseki1 = [0] * (N+1)
ruiseki2 = [0] * (N+1)
for i in range(N):
    ruiseki1[i+1] = ruiseki1[i] + (P[i] if C[i]==1 else 0)
    ruiseki2[i+1] = ruiseki2[i] + (P[i] if C[i]==2 else 0)

# print(ruiseki1)
# print(ruiseki2)

for i in range(Q):
    l, r = L[i], R[i]
    ans1 = ruiseki1[r] - ruiseki1[l-1]
    ans2 = ruiseki2[r] - ruiseki2[l-1]
    print(f"{ans1} {ans2}")

競プロ典型90問:008 - AtCounter(★4)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_h

挑戦結果

  • 結果:解けた
  • 時間:30分ぐらい

考えたこと

  • DPっぽいことは最初から感じた
  • 遷移の条件に苦労した

公式解説

https://twitter.com/e869120/status/1379927227739987972?s=20

解説を読んだふりかえり

  • DPの作り方は解説と同じで良かった。少しDPに慣れてきたか。
  • ただ、時間もかかったし、理解度がまだ足りてない感じはする。

ソース

N = int(input())
S = input()
MOD = 10**9 + 7
# 先頭に足して1-originにする。末尾も範囲チェックを楽にする都合で追加
ATCODER = "_atcoder_"
S = "@" + S + "@"

# DPテーブルは大きめに確保
# dp[i][j]のとき、
# Sのi文字目まで使用していて、"atcoder"のj文字目までカバーしているパターン数
dp = [[0] * (len(ATCODER)+10) for _ in range(N+10)]
# Sを0文字目まで使っていて、"atcoder"の0文字目までカバーしているのが1パターン。
dp[0][0] = 1

# 配るDP
for i in range(N+1):
    for j in range(7+1):
        # 遷移①:使える文字数が増えても、既存パターン数はOK
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        # 遷移②:使える文字が増えて、atcoderの次の文字とマッチする場合
        if ATCODER[j+1] == S[i+1]:
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD

print(dp[N][7])

競プロ典型90問:007 - CP Classes(★3)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_g

挑戦結果

  • 結果:解けた
  • 時間:10分ぐらい

考えたこと

  • 愚直はTLEする
  • $A$はソートすれば二分探索で近いクラスを見つけられる。見つけたら前後のどちらか($A_i$と$A_{i+1}$)が最も近いクラスなので、それの近い方のクラスに入れればOK。

公式解説

https://twitter.com/e869120/status/1379565222541680644

解説を読んだふりかえり

  • スルッと解けたので、特になし。

ソース

import bisect
# インプット
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [int(input()) for _ in range(Q)]
# 二分探索(bisect)用にソートしておく
A.sort()
INF = float('inf')
for bval in B:
    diff = INF
    # A[aidx] <= bval < A[aidx+1] を二分探索で探すので、近い方を選択採用すればOK
    aidx = bisect.bisect_left(A, bval)-1
    diff = abs(A[aidx] - bval)
    if aidx+1 < len(A):
        diff = min(diff, abs(A[aidx+1] - bval))
    print(diff)

競プロ典型90問:006 - Smallest Subsequence(★5)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_f

挑戦結果

  • 結果:できなかった
  • 時間:30分ぐらい

考えたこと

  • 全列挙を再帰的に作ることはできると思ったけど、計算量的にどう考えても無理だった。
  • 貪欲に求める方法も考えたけど、思いつかなかった。

解説を読んだふりかえり

  • 貪欲な方法を思いつかなかったし、その上、事前計算が必要だったようで無理だった。
  • なんかもう一度解いても解ける気がしてないけど、辞書式最小は前から貪欲法は覚えておこう

公式解説

https://twitter.com/e869120/status/1379202843622576130?s=20

ソース

from string import ascii_lowercase
N,K = [int(x) for x in input().split()]
S = input()
INF = float('inf')

# 事前の計算用のテーブル
C = [[INF] * N for _ in range(len(ascii_lowercase))]
L = [INF] * len(ascii_lowercase)
# 後ろから、文字がある場所を計算
for i,ch in reversed(list(enumerate(S))):
    L[ord(ch)-ord('a')] = i
    for a in ascii_lowercase:
        aidx = ord(a)-ord('a')
        C[aidx][i] = L[aidx]

ans = ""
idx = 0
# Sのidx文字目を候補にするかどうか
# 一番若い文字をピックアップできるかどうかは、ピックアップした後続に文字数があればOK
while (idx < N and len(ans)<K):
    for j,ch in enumerate(ascii_lowercase):
        if N-C[j][idx] >= K-len(ans):
            ans += ch
            idx = C[j][idx]
            # print(ans)
            break
    idx+=1

print(ans)

競プロ典型90問:004 - Cross Sum(★2)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_d

挑戦結果

  • 結果:解けた
  • 時間:15分ぐらい

考えたこと

  • 愚直に計算するとTLEなんだろうと思った
  • 事前に縦と横で集計しておくと、$縦合計+横合計-A[i][j]$ で$B[i][j]$が求まると気がついた

解説を読んだふりかえり

  • デバッグで思ったより時間がかかってしまった
  • 愚直にやった場合の計算量も計算してみようと思った。

ソース

H, W = [int(x) for x in input().split()]
A = [[int(x) for x in input().split()] for _ in range(H)]
# 縦と横の合計
sumH = [0] * W
sumW = [0] * H
# 横についての合計
for i in range(H):
    for j in range(W):
        sumW[i] += A[i][j]
# 縦についての合計
for j in range(W):
    for i in range(H):
        sumH[j] += A[i][j]
# 縦方向の合計+横方向の合計 - A[i][j]
for i in range(H):
    L = []
    for j in range(W):
        L.append(str(sumH[j] + sumW[i] - A[i][j]))
    print(" ".join(L))