Ccmmutty logo
Commutty IT
12 min read

緑コーダーがABC259のA~Eまで

https://cdn.magicode.io/media/notebox/blob_vHArof1

AtCoder Beginner Contest 259

ABC259のA~Eに関する解説(という名の自分用メモ書き)です。
今回も4完止まり…でした…うう…中々5完が出来ませんねぇ…。
今回のEも、解法まではうっすら方針見えてたのに…!
実装する実力がありませんでした…
次こそ!5完!したい!(N回目定期)

A - Weather Forecast

問題要約

高橋くんは、NN歳の誕生日を迎えました。この時の彼の身長はTTcmです。
高橋くんは、0歳の誕生日(生まれた当日)から、XX歳の誕生日までの間、毎年身長がDDcmずつ伸びました。   高橋くんは、XX歳の誕生日からNN歳の誕生日までの間、身長が変化していません。
高橋くんがMM歳の誕生日の時、身長は何cmだったかを求めなさい。

制約

  • 0M<N1000 \leq M < N \leq 100
  • 1XN1 \leq X \leq N
  • 1T2001 \leq T \leq 200
  • 1D1001 \leq D \leq 100
  • 高橋君の0歳の誕生日の時の身長は1cm以上である
  • 入力は全て整数

考察

  • 本番中に0歳の誕生日の時の身長は0cmだとよくわからない決めつけで脳が固まってしまい5分間溶かしました…猛省…
  • 入力の要素が多いと頭ごちゃごちゃになる…うう…
  • XX歳までは身長が伸びてた
    • この条件から、X歳未満か、それ以上かで場合分けしたいね
    • 勝手に、0歳~XX歳の誕生日までを「成長期」と呼ぶことにする
    • もしMMが成長期の年齢だった場合…
      • あと何年で成長期は終わる?
        • 成長期終わりの年齢 - MM歳 = 残りの成長期期間
      • 残りの成長期期間中は、毎年DDcm身長が伸びる
      • 成長期が終わった時、身長はTTcmになる
        • 成長期終わりの身長 - 残りの成長期期間 ×\times DDcm = MM歳の時の身長
    • MMが成長期終わった後の年齢だった場合…
      • 今と変わらずTTcm
python
# 入力
N, M, X, T, D = map(int, input().split())

# もし聞かれてるのが成長期の年齢だった場合…
if M < X:
    # 今の身長 - (成長期終わりの年齢 - 聞かれてる年齢) * 成長期に毎年伸びる身長
    print(T - (X - M) * D)

# もし聞かれてる年齢が成長期終わってた場合…
else:
    print(T)

B - Counterclockwise Rotation

問題要約

xx軸の正の向きが右、yy軸の正の向きが上であるようなxyxy座標平面において、
(a,b)(a,b)を原点を中心として反時計回りにdd度回転させた点を求めて下さい。

制約

  • 1000a,b1000-1000 \leq a,b \leq 1000
  • 1d3601 \leq d \leq 360
  • 入力は全て整数

考察

  • 中学?高校?の数学で見たような感じの問題
  • 原点を中心に、dd度回転させてあげたい
  • 単位円書いたり、sin=斜辺/高さとか、cos=斜辺/長さとか、その辺りを改めて押さえるための問題でした
  • 角度と原点までの距離を求めて、しっかり回転させてあげても良し
python
from math import atan2, radians, sin, cos

# 入力
a, b, d = map(int, input().split())

# x軸からの角度+回したい角度=移動させた後の角度
rad = atan2(b, a) + radians(d)

# 原点からの距離計算
r = (a * a + b * b) ** (1 / 2)

X = cos(rad) * r
Y = sin(rad) * r

print(X,Y)
  • 行列計算で済ませても良し
python
from math import radians, sin, cos

# 入力
a, b, d = map(int, input().split())

cosd = cos(radians(d))
sind = sin(radians(d))

X = cosd * a - sind * b
Y = sind * a + cosd * b

print(X, Y)
  • 複素数…!使えると格好良いなぁ…!!!
python
from math import radians, e

a, b, d = map(int, input().split())

c = complex(a, b)
d = radians(d)
ans = c * e ** (1j * d)

print(ans.real, ans.imag)

C - XX to XXX

問題要約

英小文字からなる文字列S、文字列Tが与えられます。
次の操作を0回以上好きな回数行う事で、S==Tとなるか判定して下さい。
  • S上の同じ文字が2文字連続している箇所の間に、その文字と同じ文字を1つ挿入する。
    • ...○○...→...○○○...

制約

  • SSTTはそれぞれ英小文字からなる長さ22以上2×1052 \times 10^5以下の文字列

考察

  • 本番終了後のTLで誤読として、「Tに文字追加できなかったんかーい」が見られました
    • 確かに、うーん…一応、操作内でSとしてるけど…外側の文章(英小文字からなる〜してください)に、捜査の対象がSだけ、とは書いてないのが…原因…?
    • サンプルでTへの文字追加操作ができないケースは無いですねぇ…
      • 入力例3として、S = aaabbbccc, T = aabbccみたいなのもあってもよかったかも…?
  • 出来ることは、Sに文字を追加すること、だけ
    • 好きなところに好きな文字を追加はできない。条件付き
  • 順番変えたりもできない
  • 削除もできない
  • ちっちゃいケースを考える
    • S=aaの時、操作を好きな回数行えるので、S = aa.....aaみたいな状態にできちゃう
    • 2個以上連続して同じ文字がある箇所は、好きなだけ文字数足せる!
    • 逆に、1個しか無い所(aaabaaaの、b)は、文字足せない…
    • 先頭から、文字の種類毎に見ていきたいですね
  • そう、ランレングス圧縮(RLE:Run Length Encoding)ならね。
  • 詳細はこのあたりで…
  • 文字列S、文字列TをそれぞれRLEで圧縮してあげて…
  • 先頭から順に見ていくと良いですね
    • 要素を1つずつ取り出して…
      • 文字が一緒で、文字の数も一緒の場合
        • 操作しなくてもそこは一致!ヨシ!
      • 文字が一緒で、Tの文字数のが多い時…
        • Sの文字数が1なら、操作できない!一致にできない!どうして…
        • Sの文字数が2以上なら、操作(文字追加)で一致にできる!ヨシ!
  • そもそも要素数が異なっていたら、どう操作を行っても一緒になりませんね…
python
from itertools import groupby

S = input()
T = input()


def rle(a):
    grouped = groupby(a)
    res = []
    for k, v in grouped:
        res.append((k, int(len(list(v)))))
    return res


s_L = rle(S)
t_L = rle(T)

# 要素の数が違ったらOUT!!!
if len(s_L) != len(t_L):
    print('No')
    exit()

ans = 'Yes'
# zipで纏めて1つずつ出してあげて
for s, t in zip(s_L, t_L):
    # 文字種、文字サイズをそれぞれ確認!
    s_char, s_cnt = s
    t_char, t_cnt = t

    # 文字種が違う!どうして…
    if s_char != t_char:
        ans = 'No'
    
    # Sの方が多い!どうして…
    if s_cnt > t_cnt:
        ans = 'No'
        
    # Sに足したい!けど足せない!どうして…
    if s_cnt == 1 and t_cnt != 1:
        ans = 'No'
        
print(ans)

D - Circumferences

問題要約

xyxy平面上にNN個の円が与えられます。
i=1,2,,Ni = 1,2,…,Nについて、ii番目の円は点(xi,yi)(x_i,y_i)を中心とする半径rir_iの円です。
NN個の円のうち、少なくとも1つ以上の円の円周上にある点のみを通って、点(sx,sy)(s_x,s_y)から点(tx,ty)(t_x,t_y)に行くことができるか判定してください。

制約

  • 1N30001 \leq N \leq 3000
  • 109xi,yi109-10^9 \leq x_i,y_i \leq 10^9
  • 1ri109 1 \leq r_i \leq 10^9
  • (sx,sy)(s_x,s_y)はN個の円のうち、少なくとも1つ以上も円の円周上にある
  • (tx,ty)(t_x,t_y)はN個の円のうち、少なくとも1つ以上も円の円周上にある
  • 入力は全て整数

考察

  • 制約ぼんやり見てみると…あら、円の数が控えめですわね、これ。O(N^2)も通りますわ。
  • スタート地点、ゴール地点が円周上に乗ってないこともなく…。
  • 其々の円同士が接してるor重なってるなら、円周同士の移動は可能…。
  • じゃあ後は、円同士が移動可能(接しているor重なってる)か否(離れてる)かをO(N^2)かけて判定して…
  • BFSなりなんなりで、スタート地点が所属してる円からゴール地点が所属してる円まで移動できるかの判定すれば良い!ね!
    • 黒ココアさんは手が先に動いてBFSで殴り通したんですが、UnionFindあたりをこの辺でさっと出せると格好良いですねぇ…
  • 円の衝突判定が若干難儀する、かもしれない…
    • サンプル2のように、円の内側に完全に入り込んでしまった場合は、円周同士は重ならない点に注意
python
from collections import deque

# 入力
N = int(input())
sx, sy, tx, ty = map(int, input().split())
start_s = set()  # スタート地点が円周上に乗ってる円の集合
goal_s = set()  # ゴール地点が円周上に乗ってる円の集合
circle_L = []  # 円情報保管庫

for i in range(N):
    x, y, r = map(int, input().split())
    circle_L.append([x, y, r])

    # スタート地点がこの円の円周上に存在するか判定
    if r * r == (x - sx) * (x - sx) + (y - sy) * (y - sy):
        start_s.add(i)

    # ゴール地点がこの円の円周上に存在するか判定
    if r * r == (x - tx) * (x - tx) + (y - ty) * (y - ty):
        goal_s.add(i)


# \円の交わり判定機〜/(CV:NOBUYO)
def cross_check(a, b):
    # aの方が大きい円にしたい
    if a[2] < b[2]:
        a, b = b, a

    xa, ya, ra = a
    xb, yb, rb = b

    # xの差とyの差で
    x = xa - xb
    y = ya - yb

    # 三平方の定理的に…ただし、ルート取っちゃうと小数で誤差出ちゃいそうなので…後で2乗するので勘弁して下さい…
    length = x * x + y * y

    # 円周が重なってるか判定!
    if (ra - rb) ** 2 <= length <= (ra + rb) ** 2:
        return True
    else:
        return False


# 円と円が接してるならedge張ってBFS!
edge_L = [[] for i in range(N)]

# 辺張るパート
for a in range(N - 1):
    for b in range(a + 1, N):
        if cross_check(circle_L[a], circle_L[b]):
            edge_L[a].append(b)
            edge_L[b].append(a)

# BFS!BFS!
que = deque(start_s)
checked_s = set(start_s)
while que:
    now = que.popleft()

    for next_node in edge_L[now]:

        if next_node not in checked_s:
            checked_s.add(next_node)
            que.append(next_node)

# 到達できましたー?
if len(goal_s & checked_s) == 0:
    print('No')
else:
    print('Yes')

E - LCM on Whiteboard

問題要約

NN個の整数a1,,aNa_1,…,a_Nが白板にかかれています。
ここで、aia_iは、素因数分解された情報として入力されます。
あなたはNN個の整数から、1つ選んで1に書き換えます。
書き換えた後のNN個の整数の最小公倍数として、あり得る値の個数を求めて下さい。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1mi1 \leq m_i
  • mi2×105\sum m_i \leq 2 \times 10^5
  • 2pi,1<<pi,mi1092 \leq p_{i,1} < … < p_{i,m_{i}} \leq 10^9
  • pi,jp_{i,j}は素数
  • 1ei,j1091 \leq e_{i,j} \leq 10^9
  • 入力は全て整数

考察

  • 最小公倍数(LCM)の求め方を考える
  • 入力の形式が若干、若干、本当に少しdさけ面倒くさい形だけど、一応素因数分解してくれてるようなので、その辺が使えないかなぁと…。
  • 素因数分解で出てきた各素数の、最大の指数eを指数としたものが因数となる数が、LCMになる
    • ほーん…何言ってるのかわからないから図示してみたらこうなった。
  • もすーん先生の解説がとてもわかり易かったです…!
  • 図後半に書いてみたようなテストケース:24,36,7を考えてみる
    • 全部入れた時のLCM:23×32×71=5042^3 \times 3^2 \times 7^1 = 504
    • X1X_1を1にした時のLCM:22×32×71=2522^2 \times 3^2 \times 7^1 = 252
    • X2X_2を1にした時のLCM:23×31×71=1682^3 \times 3^1 \times 7^1 = 168
    • X3X_3を1にした時のLCM:23×32×70=722^3 \times 3^2 \times 7^0 = 72
  • XiX_iを素因数分解した時に、指数が唯一、かつ、最大である素因数pを含む時XiX_iを1にするとLCMが変わる!
  • じゃあ1 N1~Nまでの整数に対して…
    • それぞれ分解された素数とその指数が、「他の整数を分解したパーツ」と見比べて「唯一、かつ、最大」であるかを判断
      • 唯一、かつ、最大の指数を持った素数がある場合、その整数を1にしたらLCMが小さくなるので!
  • 1 N1~Nまでの整数全体のLCMと変わらないものが入ってるケースに注意
    • 「1にしてもLCMが変化ない」整数とは…?
      • [12, 6, 3]のケースで考えてみる
        • 12を1にする→LCM:6
        • 6を1にする→LCM:12
        • 3を1にする→LCM:12
      • 上記ルールで判断していくと、「唯一かつ最大」の指数を持ってる数字って12しかないんだけども…
      • 取り得るLCMの数としては、「6と12」の2種類あるよね
        • 全体の素因数(どれも1にしない状態)も考えてみて、そんなパターンが1つでもあれば、+1するイメージ
python
from collections import defaultdict

# 入力
N = int(input())
L = [[] for i in range(N)]

# 其々の素因数の「最大」の指数を管理するためのdict
max_lcm_d = defaultdict(int)

# 其々の素因数と指数が「唯一」かを管理するためのdict
cnt_d = defaultdict(int)

# まだ入力…
for i in range(N):
    m = int(input())
    for j in range(m):
        p, e = map(int, input().split())

        # 指数最大値を更新
        max_lcm_d[p] = max(max_lcm_d[p], e)

        # 辞書のキーにタプルで突っ込んじゃって、カウント
        cnt_d[(p, e)] += 1

        # 整数a毎に、素因数と指数のペアで管理
        L[i].append((p, e))

ans = 0
max_cnt = 0

# 整数を1にした時…
for prime_L in L:

    # その整数に含まれる素因数と指数を1つずつ見ていくよ!
    for k, v in prime_L:

        # 唯一、かつ、最大のものがあれば、この整数を1にした時LCMが変化する!
        if max_lcm_d[k] == v and cnt_d[(k, v)] == 1:
            ans += 1
            break

    # 1つも変化する要素が無い場合、LCMは「1にする操作を行わない」時と変わらないので、その状態をキープ
    else:
        max_cnt |= 1

# その状態になってるなら取り得る値の個数に+1されて出力!
print(ans + max_cnt)

Discussion

コメントにはログインが必要です。