0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

ABC305

今週は参加できましたので、書いていきます。
ABC305( https://atcoder.jp/contests/abc305 )

A

余りで場合分けした。一度5で割ることで端数の処理を行ったが、もっとうまいやり方がある気がする。。。

N = int(input())
if N % 5 >= 3:
  print((N//5+1) * 5 )
else:
  print(N//5 * 5)

B

文字を入れた配列l_sと文字間の距離を入れた配列lを作り、文字ごとにl_sのindexを取ってその値をlに利用した。
例えば、AとBの間であればl_sのindexを取ることで0と1の値を得る。その値を用いて、l[1:2]のようにスライスを使って計算に用いる部分配列を求め、その配列にsum()関数を用いることで求めた。
問題上、文字が昇順で与えられるとは限らないため、その部分の条件文を加えた。

p,q = map(str, input().split())
l = [3,1,4,1,5,9]
l_s = ["A","B","C","D","E","F","G"]
a = l_s.index(p)
b = l_s.index(q)
if a > b:
  box = a
  a = b
  b = box
print(sum(l[a:b]))

C

各行ごとの#の数をカウントし、それを配列cとして格納する。クッキーを食べている行は#が一つ少ないため、配列cの最大値から1ひいたもののindexを調べることで食べた行までわかる。その後、食べた行と食べてない行で#が一致しない部分を調べることで座標を求めた。
「周囲に2個以上#がある.の座標」というのも考えたがTLEを警戒して上記手法をとった。が、今回は行けたらしい。

H, W = map(int, input().split())
M = [input() for _ in range(H)]
l = []	#列ごとのクッキーの数
 
for i in range(H):
  l.append(M[i].count("#"))
 
x = l.index(max(l)-1)	#食べた列
x_ = l.index(max(l))	#食べてない列
 
#食べた行の判別
for j in range(W):
  if M[x][j] != M[x_][j]:
    y = j
    break
 
#回答
print(x+1,y+1)

D

TLEとなり時間内の回答ができなかった。条件をみて工夫がいることが分かったが、全く思いつかずに愚直にやることしかできなかった。
計測の終了時間までの睡眠時間の総和から、開始時間までの睡眠時間の総和を引くことで求められる。起床や就寝時点までの睡眠時間の総和は簡単に求められるため、配列として確保しておく。計測時間は就寝や起床のタイミングで行われない場合があるため、どのタイミングで起きたかを二分探索で求め、各タイミングでの処理を行う。ここはおそらく条件文でもいいし、解説のように睡眠時間の配列を利用し条件なしでも計算のみでも対応できる。
多分重要なのは二分探索の部分で、計算の部分は書く時間帯ごとの睡眠時間とかを使ってもいける気がする。。。

from bisect import bisect_left
 
def Calsleep(T,A,x):
  t = bisect_left(A,x)
  if t == 0:
    return 0
  else:
    return T[t-1] + (T[t] - T[t-1])//(A[t]-A[t-1]) * (x - A[t-1])
 
N = int(input())
A = list(map(int, input().split()))
T = [0]
 
for i in range(N):
  if i % 2 == 0:
    T.append(T[i])
  else:
    T.append(T[i] + A[i+1] - A[i])
 
Q = int(input())
 
for i in range(Q):
  s,e = map(int, input().split())
  print(Calsleep(T,A,e) - Calsleep(T,A,s))

反省・感想

二分探索には今まで何度か問題として触れてきているが、使う場面を見抜くことがまだまだできていないと感じるコンテストでした。使うアルゴリズムの取捨選択の判断を今後はっきりとさせていきたいと思います。あと、自分で作る二分探索よりライブラリ使った方がバチバチに早いこともわかりました。はい。
どんどんレート下がってやる気も下がりそうですが、ちまちま取り組んでいきたいと思います。

745 → 728

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?