ABC133-B - Good Distance を解く

ABC133-B - Good Distance

D次元空間上に N個の点がある

i 番目の点と j 番目の点の距離が整数となるような組み合わせは

いくつあるかを求める（ i < j ）

2点間の距離を求める公式は与えられているのでそれを利用する

N の制約は 2 <= N <= 10 とかなり小さいので

組み合わせを全通り試せばいい

このとき、ダブルカウントしないように注意する必要がある

整数であることの確認については色んな方法があるが

今回は以下のようにキャストによる小数点以下の切り捨てと

等号演算子を利用して行う

# 整数の場合
>>> a=1.0
>>> b=int(a)
>>> 
>>> a==b
True

# 整数でない場合
>>> a=1.1
>>> b=int(a)
>>> 
>>> a==b
False

以上を踏まえて書いたコードを以下に示す

提出したコード

import math

# 入力
N,D=map(int,input().split())

l=[]
for i in range(N):
  l.append(list(map(int,input().split())))

c=0
for i in range(N):
  for j in range(i+1,N):

    # 距離の計算
    a=0
    for k in range(D):
      a+=pow(l[i][k]-l[j][k],2)

    a=math.sqrt(a)

    # 整数の判定
    b=int(a)
    if a==b:
      c+=1

# 出力
print(c)

提出結果はACでした

ABC132-B - Ordinary Number を解く

ABC132-B - Ordinary Number

{ 1 , 2 , ... , n }  の順列  { p1 , p2 , ... , pn }  がある

pi - 1 , pi , pi + 1（ 1 < i < n ） の 3 つの数の中で

pi が 2 番目に小さくなるような pi はいくつ存在するかを求める

端から順番に 3 つずつ見ていき

条件を満たすパターンをカウントしていく

「pi - 1 , pi , pi + 1 の 3 つの数の中で、pi が 2 番目に小さい」という条件は

「pi は 3 つの数の中で最小値でもなく、最大値でもない」と言い換えられる

今回はこれを利用して判定を行う

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
n=int(input())
l=list(map(int,input().split()))

c=0
for i in range(1,n-1):
  # pi-1, pi, pi+1
  a=[l[i-1],l[i],l[i+1]]

  # 2番目に小さい場合 +1
  if min(a)<l[i] and l[i]<max(a):
    c+=1

# 出力
print(c)

提出結果はACでした

ABC131-B - Bite Eating を解く

ABC131-B - Bite Eating

N 個のリンゴがあり、リンゴ i の「味」は L + i - 1 で定義される

このリンゴを材料として作ったアップルパイの味はリンゴの味の総和になる

ここで、N 個のリンゴから 1 つリンゴを取り除き

N - 1 個のリンゴでアップルパイを作る

N - 1 個のリンゴで作ったアップルパイの味と

N 個のリンゴで作ったアップルパイの味の差の絶対値が最小となるときの

N - 1 個のリンゴで作ったアップルパイの味を求める（ややこしい…）

まずは、N個のリンゴで作ったアップルパイの味を計算する

これは「味」の定義である L + i - 1 を使ってリンゴ1つ1つの味を求めて

総和を取ればいい

次に、取り除く1つのリンゴはN通りあるので

全てのパターンについて N - 1 個のリンゴで作ったアップルパイの味を計算する

各アップルパイについて

N 個のリンゴで作ったアップルパイの味の差の絶対値を求める

最小値を更新したときの N - 1 個のリンゴで作ったアップルパイの味も

出力のため、随時更新しておく必要がある（これが少し面倒）

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N,L=map(int,input().split())

# リンゴの味を保持するリスト
l=[]
for i in range(N):
  l.append(L+(i+1)-1)

# N個のリンゴを材料として作った場合の味
s=sum(l)

# アップルパイの味の差の絶対値の最小値（巨大な数で初期化）
p=10**10

# N-1個のリンゴを材料として作った場合の味との比較
ans=0
for x in l:
  if p>abs(s-(s-x)):
    p=abs(s-(s-x))
    ans=s-x

# 出力
print(ans)

提出結果はACでした

ABC130-B - Bounding を解く

ABC130-B - Bounding

数直線を N + 1 回ボールが以下のように跳ねる

・1回目は 座標 D1 = 0 でボールが跳ねる

・i 回目は 座標 Di = Di-1 + Li-1（2 <= i <= N + 1）で跳ねる

座標 X 以下で跳ねる回数は何回かを求める

カウンタを用意し、与えられた漸化式を使用して跳ねた地点の座標を求める

それが X 以下であった場合はカウンタを + 1 加算する、というやり方で

座標 X 以下で跳ねた回数を求めることにする

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N,X=map(int,input().split())
l=list(map(int,input().split()))

# 跳ねる回数（D1での1回を加算済）
c=1

# 跳ねる座標
D=0

for x in l:
  # 次の座標を求める
  D=D+x

  # 座標がX以下であればカウント
  if D<=X:
    c+=1

# 回数を出力
print(c)

提出結果はACでした

ABC129-B - Balance を解く

ABC129-B - Balance

1 から N の番号がついた N 個の重りがある

番号が T 以下の重りのグループ と

番号が T より大きい重りのグループ の2グループに分ける（1 <= T < N）

それぞれのグループの重りの和の S1, S2 としたとき

S1, S2 の差の絶対値の最小値を求める問題

サンプルを1つ見てみよう

入力例1

3

1 2 3

この場合は、{ 1 } , { 2, 3 } のグループ分けの場合と

{ 1, 2 } , { 3 } のグループ分けの場合の2通りのグループ分けが考えられる

前者の差の絶対値は 4 で 後者の差の絶対値は 0 となるため

小さい方である 0 が答えとなる

こういったグループ分けはリストのスライスを使用することで実現できる

>>> print(l)
[1, 2, 3, 4, 5]
>>> 
>>> for i in range(1,len(l)):
...     print(l[:i],l[i:])
... 
[1] [2, 3, 4, 5]
[1, 2] [3, 4, 5]
[1, 2, 3] [4, 5]
[1, 2, 3, 4] [5]

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())
l=list(map(int,input().split()))

# 最小値（とても大きな数で初期化）
mn=10**10

for i in range(len(l)+1):
  S1=sum(l[:i])
  S2=sum(l[i:])

  mn=min(mn,abs(S1-S2))

# 出力
print(mn)

for 文の中で sum 関数を使用すると計算量がかなり大きくなってしまうのだが

今回のように制約が小さければ問題はない

提出結果はACでした

ABC128-B - Guidebook を解く

ABC128-B - Guidebook

N個のレストランについての情報が与えられる（市の名前、得点）

市の名前の辞書順に紹介が行われる

市の名前が同じ場合は、得点が大きい方が優先される

紹介される順に番号を出力する問題

まずは言われている通り、辞書順でソートする必要がある

しかし、名前が同じ場合は、得点が大きい方が優先される

ここで何も考えずソートしてしまうと

順番が「得点の昇順」になってしまう恐れがある

>>> print(l)
[['cd', 3], ['ab', 2], ['ab', 4]]
>>> 
>>> l.sort()
>>> 
>>> print(l)
[['ab', 2], ['ab', 4], ['cd', 3]]

「市の名前」と「得点」の2要素をもつリストをソートする場合

このようにまとめてソートしてしまうと両要素ともに昇順でソートされてしまう

（ "reverse=True" オプションを指定することで降順ソートは可能であるが

そうすると今度は両要素共に降順でソートされてしまう）

したがって、まずは「得点」の要素のみに注目して降順ソートを行い

次に「市の名前」の要素のみに注目して昇順ソートを行うことで

目的とするソートを実現させる

>>> print(l)
[['cd', 3], ['ab', 2], ['ab', 4]]
>>> 
>>> l=sorted(l,key=lambda x:x[1],reverse=True)
>>> l=sorted(l,key=lambda x:x[0])
>>> 
>>> print(l)
[['ab', 4], ['ab', 2], ['cd', 3]]

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())

# リスト
l=[]

for i in range(N):
  # 入力
  S,P=input().split()

  # リストに入れる（出力用の番号もついでに入れる）
  l.append([i+1,S,int(P)])

# 点数が高い順にソート
l=sorted(l,key=lambda x:x[2],reverse=True)

# 辞書順ソート
l=sorted(l,key=lambda x:x[1])

# 番号を出力
for x in l:
  print(x[0])

提出結果はACでした

ABC127-B - Algae を解く

ABC127-B - Algae

漸化式 xi+1 = rxi - D が存在する

r, D, x2000 が与えられるので x2001 ... x2010 を計算し、出力する問題

漸化式と聞くと身構える人もいるかもしれないが

前の計算結果を次の計算結果で使用するというだけの話だ

与えられた式に適切に数値を当てはめて計算し、結果を出力すれば良い

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
r,D,x=map(int,input().split())

for i in range(10):
  # 計算
  y=r*x-D

  # 出力
  print(y)

  # 次の計算の準備
  x=y

提出結果はACでした