Ccmmutty logo
Commutty IT
・0 pv・6 min read

ABC226 茶色コーダーが解けたところまで

AtCoder競技プログラミング
https://picsum.photos/seed/5b2e7432baec496e9e84ec3ba9529634/1200/630

AtCoder Beginner Contest 226

ABC226の問題を、本番で自分が解けた所までの解説です。
Dまでで1時間切り。このペースを常に安定してアウトプットしたいものです。

A - Round decimals

Difficulty: 14

問題文

小数第三位までで表すことのできる実数XXが、小数第三位まで入力されます。
XXを小数第一位で四捨五入した結果として得られる整数を出力してください。

制約

  • 0≤X<100 0 \leq X < 100
  • XX は小数第三位までで表現可能である。
  • XX は小数第三位まで与えられる。

考察

Xを四捨五入したい

  • 堅実に条件分け
    • 小数点の1つ右にある数字が0~4なら…
      • 小数点より左の数字をそのまま出力
    • 小数点の1つ右にある数字が5~9なら…
      • 小数点より左の数字に1足したものを出力
  • ライブラリとか使って一発で小数(float)から整数(int)へ四捨五入！ドン！
    • Pythonの場合は丸め誤差とか色々あるから要注意
      • 小数点以下が0.5の時、挙動が不安定になったりとかとか
        • 一応、0.00050.0005を足すことで回避するなんていう小技もある

パターン1：堅実に条件分け

python
# strとして入力。後で小数点以下の一番左の桁が欲しいため
X = list(map(int,input().split('.')))

# S[1]：小数点以下の数字
# 小数点以下が500未満（=1~4)ならそのまま整数部を出力
if int(X[1]) < 500:
    print(X[0])
# そうじゃないなら、整数部に1足したものを出力
else:
    print(int(X[0])+1)

パターン2：標準ライブラリでテクニカルに

python
# 入力
X=float(input())

# 0.500の時に発生する誤差を木にして、0.001未満の小さな数を足した上でroundしたものを出力
print(int(round(S+0.0005,0)))

パターン3：ライブラリだけでゴリ押し

python
from decimal import Decimal,ROUND_HALF_UP

# 入力
X = input()

print(Decimal(X).quantize(Decimal('0'), rounding=ROUND_HALF_UP))

B - Counting Arrays

Difficulty: 192

問題文

11 から NN までの番号がついた NN 個の数列が与えられます。
数列 ii は、長さが LiL_i で j(1≤j≤Li)j (1 \leq j\leq L_i) 番目の要素が ai,ja_{i,j}であるような数列です。
数列 ii と数列 jj は、 Li=LjL_i=L_jかつすべての k(1≤k≤Li)k (1 \leq k \leq L_i)に対して ai,k=aj,ka_{i,k}=a_{j,k}が成り立つ時に同じであるとみなします。 同じ数列は 11 種類として数えるとき、数列 11 から数列 NN の中に全部で何種類の数列がありますか？

制約

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Li≤2×105(1≤i≤N)1 \leq L_i \leq 2 \times 10^5(1\leq i \leq N)
  • 0≤ai,j≤109(1≤i≤N,1≤j≤Li)0 \leq a_{i,j} \leq 10^9 ( 1\leq i \leq N, 1 \leq j \leq L_i)
  • すべての数列の要素の個数の和、すなわち ∑i=1NLi\sum_{i=1}^{N} L_iは2×1052 \times 10^5を超えない。
  • 入力は全て整数である。

数列の比較？なんか問題文難しいね？

  • 実際公式放送でも難しい話してる
    • ハッシュテーブルとか平衡二分探索木とか…
  • LL(長さ)も含めて全部一括で文字列として見てあげて、setに突っ込んでいけば重複排除できる…！（力技）
python
# 入力、セット用意
N = int(input())
s = set()

# ループ内で配列化せずにstrのままsetに無理やり突っ込んでいく
for i in range(N):
    s.add(input())

# 長さ＝種類数
print(len(s))

C - Martial artist

Difficulty: 539

グラフとして捉える

  • 技NNにを覚えるために必要な技は、AN,1,AN,2…AN,KNA_{N,1},A_{N,2}\dots A_{N,K_N}
  • ゲームのスキルツリー的なイメージで、NからAN,1,AN,2…AN,KNA_{N,1},A_{N,2}\dots A_{N,K_N}にそれぞれ辺を張る
    • 次はAN,1,AN,2…AN,KNA_{N,1},A_{N,2}\dots A_{N,K_N}から、それらの技を覚えるために必要な技に辺を張って…
    • 繰り返すと、必要な技の一覧が出てきますね。後はBFSやDFSと同様の流れで、「NNから到達可能な点」の技を覚えるのに必要な時間の和を求める
python
from collections import deque

# 入力
N = int(input())
need_d = dict()
study_time = [0]*(N+1)

# 習得にかかる時間を配列で、習得に必要な技をdictで管理。
for i in range(N):
    L = list(map(int, input().split()))
    study_time[i+1] = L[0]
    need_d[i+1] = set(L[2:])

time = study_time[N]
que = deque()
studied_s = set()
que.append(N)

# BFSと同じように、timeを足していく
while que:
    next_waza = que.popleft()
    for i in need_d[next_waza]:
        if i not in studied_s:
            que.append(i)
            studied_s.add(i)
            time += study_time[i]

print(time)

D - Teleportation

Difficulty: 706

問題文

AtCoder 国は無限に広がる直交座標の上にあります。 AtCoder 国には NN 個の街があり、 1,2,…,N1,2,…,N と番号が付けられています。街 ii は地点 (xi,yix_i,y_i)にあり、2 つの異なる番号の街が同じ座標にあることはありません。
AtCoder 国には転移魔法(以下、魔法と表記)があります。魔法は整数の組 (a,ba,b) によって識別されていて、地点 (x,yx,y) にいるときに魔法 (a,ba,b) を使うと (x+a,y+bx+a,y+b) にワープすることができます。
すぬけ君は、任意の整数の組 (a,ba,b) を選んで魔法 (a,ba,b) を覚えることができる大魔術師です。また、すぬけ君は何種類でも魔法を覚えることができます。 魔法を使って街と街の間を移動したくなったすぬけ君は、全ての相異なる街の組 (i,ji,j) について次の行動を取れるようにいくつかの魔法を覚えることにしました。
覚えた魔法のうち 11 種類の魔法のみ を選ぶ。その後、選んだ魔法 のみ を繰り返し使って街 ii から 街 jj に移動する。 すぬけ君が上の条件を満たすように魔法を覚えるとき、少なくとも何種類の魔法を覚えればよいですか？

制約

  • 2≤N≤5002 \leq N \leq 500
  • 0≤xi≤109(1≤i≤N)0 \leq x_i \leq 10^9(1 \leq i \leq N)
  • 0≤yi≤109(1≤i≤N)0 \leq y_i \leq 10^9(1 \leq i \leq N)
  • i≠ji \neq jならば(xi,yi)≠(xj,yj)(x_i,y_i) \neq (x_j,y_j)である。

考察

地点(0,0)から地点(x,y)に行く方法を考える
  1. そのまま(x,y)の魔法を覚える
    • １回の魔法で地点(x,y)に行けるね
  2. (x/2,y/2)の魔法を覚える
    • 2回の魔法で地点(x,y)に行けるね
    • 制約より、x,yともに２で割り切れる必要がある
      • (x/2,y/2)にも(x,y)にも行けるので汎用性が高い
  3. (x/3,y/3)の魔法を覚える
    • 3回の魔法で地点(x,y)に行けるね
    • 制約より、x,yともに3で割り切れる必要がある
      • (x/3,y/3)にも(2x/3,2y/3)にも、(x,y)にも行けるので汎用性がもっと高い
xxとyyの最大公約数でそれぞれを割った魔法を覚えると汎用性が高く、覚える魔法が少なくて済みそう！
  • xxとyyのどちらかが０の場合、条件分岐が必要
    • 0で割っちゃうようなことになっちゃいます
後は制約
  • N≤500N \leq 500より、地点i,地点jを全探索O(N^2)でも余裕で間に合いますね
python
import math

# 入力
N = int(input())
# X,Yをそれぞれ別の配列で管理
X_L = []
Y_L = []
magic_S = set()

for i in range(N):
    X, Y = map(int, input().split())
    X_L.append(X)
    Y_L.append(Y)


# a地点、b地点を全探索
for a in range(N):
    for b in range(N):
        # 同じ場所から同じ場所ならスキップ
        if a == b:
            continue
        # a地点を(0,0)とした時に、b地点の座標を出す
        from_X = X_L[a]
        from_Y = Y_L[a]
        to_X = X_L[b]
        to_Y = Y_L[b]
        x = to_X - from_X
        y = to_Y - from_Y
        
        # 最大公約数で割る。x,yが０の時にパターン分岐。
        if x != 0 and y != 0:
            gcd_num = math.gcd(x, y)
            x = x // gcd_num
            y = y // gcd_num
            magic_S.add((x, y))
        elif x == 0:
            magic_S.add((0, abs(y) / y))
        elif y == 0:
            magic_S.add((abs(x) / x, 0))

# 魔法の数を数えて終わり！
print(len(magic_S))

Discussion

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