自分用メモ

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

競プロ典型90問:028 - Cluttered Paper(★4)

問題

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

挑戦結果

  • 挑戦日:2021/10/07
  • 結果:解けた
  • 時間:30分ぐらい

考えたこと

  • いもす法というやつで解けるのでは?
  • はっきりとおぼえていなかったけど、縦と横で累積和を取るはず

公式解説

解説を読んだふりかえり

  • やっぱりいもす法で良かった
  • 実装で添字をミスっていて苦しんだけど、次回はスムーズにできるような気がする。

ソース

N = int(input())
# 紙を置く配列用のサイズ
M = 1000
# 2次元配列(いもす法)
A = [[0] * (M+2) for _ in range(M+2)]

# 下記のようにする。
# 左上:-1、右上:+1
# 左下:+1、右下:-1
for i in range(N):
    lx, ly, rx, ry = [int(x) for x in input().split()]
    A[lx][ly] += 1
    A[lx][ry] -= 1
    A[rx][ly] -= 1
    A[rx][ry] += 1

# 横向きに集計
for y in range(M+1):
    for x in range(M+1):
        A[x+1][y] += A[x][y]
# 縦向きに集計
for x in range(M+1):
    for y in range(M+1):
        A[x][y+1] += A[x][y]

# 各座標の枚数をカウントする
ans = [0] * (N+1)
for x in range(M+1):
    for y in range(M+1):
        ans[A[x][y]] += 1

# 結果の出力
for i in range(1, N+1):
    print(ans[i])

競プロ典型90問:027 - Sign Up Requests (★2)

問題

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

挑戦結果

  • 挑戦日:2021/10/07
  • 結果:解けた
  • 時間:3分

考えたこと

  • setに入れて、チェックするだけ

公式解説

解説を読んだふりかえり

  • 特になし。

ソース

N = int(input())
S = set()
for i in range(N):
    s = input()
    if not s in S:
        S.add(s)
        print(i+1)

競プロ典型90問:026 - Independent Set on a Tree(★4)

問題

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

挑戦結果

  • 挑戦日:2021/10/07
  • 結果:解けた
  • 時間:30分ぐらい

考えたこと

  • 木なのでどこかのノードから距離を求めてしまえば求まりそう
  • 距離0,2,4,6,・・・のノードは接続していない。
  • 距離1,3,5,7,・・・のノードも接続してない。
  • 距離が偶数 or 奇数のノードの集合で、数の多い方をN/2個並べればよい。

公式解説

解説を読んだふりかえり

  • 自分の考えも間違ってはなかったけど、二部グラフの性質として、2色(赤/緑)に塗り分けるほうがシンプルと思った。
  • 自分はbfsで実装したけど、2色で塗るdfsの実装のほうが遥かにシンプルだった。
  • 解説をみた翌日、解説の方針で実装し直してみた。
    • 再起の深さでREした。書きを追記した。
    • sys.setrecursionlimit(1000000)

ソース

最初に提出したもの

from collections import deque
N = int(input())
G = dict()
# グラフ用
for i in range(1,N+1):
    G[i] = set()
# インプットからグラフを作る
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    G[a].add(b)
    G[b].add(a)

# 開始位置からの距離
D = {}
# 展開予定
opened = deque()
# すでに展開済み
visited = set()
# 開始位置
opened.append(1)
D[1] = 0
while len(opened) > 0:
    c = opened.popleft()
    visited.add(c) 
    for next in G[c]:
        if not next in visited:
            opened.append(next)
            D[next] = D[c]+1 

# 距離が偶数同士はつながっていない、奇数同士はつながっていない
# どちらか(数が多い方)をN//2個列挙すれば、隣り合わない頂点になっている。
L0 = []
L1 = []
for i in range(1,N+1):
    if D[i]%2==0:
        L0.append(i)
    else:
        L1.append(i)
L = L0 if len(L0) >= len(L1) else L1

# 出力
print(*L[0:N//2])

解説をみてから作り直した

from collections import deque

# 再起の深さを増やす
import sys
sys.setrecursionlimit(1000000)

N = int(input())
G = dict()
# グラフ用
for i in range(1,N+1):
    G[i] = set()
# インプットからグラフを作る
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    G[a].add(b)
    G[b].add(a)

# 木を1 or 0で塗る。(未探索の初期値は-1)
C = [-1] * (N+1)

# 深さ優先で再帰的に色を塗る
def dfs(n, c):
    C[n] = c
    for next in G[n]:
        if C[next] == -1:
            dfs(next, 1-c)

# 頂点1から色を塗る
dfs(1,0)
# 0で塗ったもの、1で塗ったもののうち、
# 個数が大きい方をN//2個表示すればOK
ans0 =[]
ans1 =[]
for i, c in enumerate(C):
    if i>0:
        if c==0:
            ans0.append(i)
        else:
            ans1.append(i)
ans = ans0 if len(ans0) >= len(ans1) else ans1
# 出力
print(*ans[:N//2])

競プロ典型90問:024 - Select +/- One(★2)

問題

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

挑戦結果

  • 挑戦日:2021/10/06
  • 結果:解けた
  • 時間:5分

考えたこと

  • 基本的に愚直に計算すれば良いと思った。
  • 操作を行う数は、A[i]とB[i]の差
  • これがK未満であればOKだけど、余ったら+/-を繰り返して消費しないといけないため、あまりは偶数でないとダメ。

公式解説

  • 見つからなかった

解説を読んだふりかえり

  • 見つからなかったのでなし。

ソース

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

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

ans = 'No'
if cnt <= K:
    if (K-cnt)%2 == 0:
        ans = 'Yes'
print(ans)

競プロ典型90問:022 - Cubic Cake(★2)

問題

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

挑戦結果

  • 挑戦日:2021/10/06
  • 結果:解けた
  • 時間:30分ぐらい

考えたこと

  • 一番小さい辺の長さで直方体を作る
  • これが間違っていて、WAを出した
  • 3辺の最小公倍数にカットすればよさそう

公式解説

解説を読んだふりかえり

  • もっと早くに最小公倍数に気がつけばよかった
  • 最小公倍数(gcd)は、python標準に含まれていて楽。

ソース

from math import gcd
A,B,C = [int(x) for x in input().split()]

d = gcd(A,B)
d = gcd(d,C)

ans = (A//d) + (B//d) + (C//d) - 3
print(ans) 

競プロ典型90問:018 - Statue of Chokudai(★3)

問題

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

挑戦結果

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

考えたこと

  • 俯角とはなにかを調べた
  • 数式一発な問題と思った
  • E869120 君の座標(x,y,z)の計算式を求めた
  • 高橋直大像との俯角に必要な三角形を求めた
  • 点1:高橋直大像 (X,Y,0)
  • 点2:E869120君の座標 (eX, eY, eZ)
  • 点3:E869120君をXY平面上に落とした場所 (eX, eY, 0)
  • 辺の長さから角度を求めるために、atan2を使用した

公式解説

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

解説を読んだふりかえり

  • ただ三角関数と書いてあった。数式作るだけなので、もっと早くときたいところ。
  • 3次元空間を脳内か紙面上で上手に描けないと駄目だな。

ソース

from math import sin, cos, pi, atan2, degrees, sqrt
T = int(input())
L,X,Y = [int(x) for x in input().split()]
Q = int(input())
E = []
for _ in range(Q):
    E.append(int(input()))

# t秒時点のE869120君の座標
def xyz(t):
    x = 0
    y = -L/2 * sin(2*pi*t/T)
    z = L/2 - L/2 * cos(2*pi*t/T)
    return x,y,z

# t秒時点の答え
def ans(t):
    eX,eY,eZ = xyz(t)
    return degrees(atan2(eZ, sqrt((X-eX)**2 + (Y-eY)**2)))


# print(xyz(0))
# print(xyz(T/4))
# print(xyz(T/2))
# print(xyz(3*T/4))

for e in E:
    print(ans(e))

競プロ典型90問:016 - Minimum Coins(★3)

問題

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

挑戦結果

  • 結果:できた
  • 時間:5分ぐらい

考えたこと

  • 三重ループで全列挙。ループのネスト条件をだんだん狭くするやつ。
  • サンプル問題が帰ってこなかった。
  • 最後は計算すればループが不要になることに気がついた
  • とはいえサンプル問題をPythonで動かすと数秒かかる。pypyなら通るか?

公式解説

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

解説を読んだふりかえり

  • 割とするっとはとけたけど、トライ&エラーが結構有った。最初から二重ループを思いつけると良かった。

ソース

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

cnt = 999999
for a in range(10000):
    for b in range(10000-a):
        if (N - (A*a + B*b)) % C == 0:
            c = (N - (A*a + B*b)) // C
            if c>=0:
                cnt = min(cnt, a+b+c)

print(cnt)