【AtCorderメモ】AtCoder Beginner Contest 253
現在の目標は、茶色なのでABCの問題A~Dを安定的に解けること。
AtCoder Beginner Contest 253の問題A~Dの内容整理。
成績
感想
- 問題Cに時間をかけてしまい、3問(問題A,~,C)しか解けなかった。
- せめて、問題Dは解けたらな…
コンテスト成績証
| 項目 | 結果 |
|---|---|
| 順位 | 4748th / 8944 |
| パフォーマンス | 485 |
| レーティング | 476 → 477 (+1) |
提出結果
| 問題 | 結果 | 得点 | 作業時間 |
|---|---|---|---|
| A | AC | 100 | 8:36 |
| B | AC | 200 | 17:18 |
| C | AC←RE | 300(1) | 66:34 |
| 合計 | 600(1) |
A. Median?
Point
- solution 1 :
(a>=b)and(b>=c)or(c>=b)and(b>=a)かどうか？ - solution 2 :
(a,b,c)をソートして,bが真ん中かどうか？ - solution 2 は、他の人の回答見て知った。上手い！！！
ソースコード
solution 1（クリックすると展開）
a,b,c = map(int, input().split()) flag = (a>=b and b>=c) or (c>=b and b>=a) ans = 'Yes' if flag else 'No' print(ans)
solution 2（クリックすると展開）
abc_list = list(map(int, input().split())) b = abc_list[1] abc_list.sort() flag = abc_list[1] == b ans = 'Yes' if flag else 'No' print(ans)
B. Distance Between Tokens
Point
- マス目上の
oを2つ探し、マンハッタン距離を計算 - マス目上の探索は、素直に二重ループするべきだった…涙
ソースコード
solution（クリックすると展開）
h,w = map(int, input().split()) t_point = [] for i in range(h): s_i = list(input()) for j in range(w): if s_i[j] == 'o': t_point.append([i,j]) ans = abs(t_point[0][0]-t_point[1][0])+ abs(t_point[0][1]-t_point[1][1]) print(ans)
C. Max - Min Query
Point
- いつも悩まされるクエリと
multiset - とりあえず、
dictを使ったスタックで解いた。 - ただ、1から書き始めると時間が掛かるので、チートシートのようなものを作成した方が良さそう。
- 公式の解説を見ると、
Pythonでも①平方分割②heapq③Binary Indexed Treeなどの方法があるらしい。 一度整理したい。
ソースコード
solution（クリックすると展開）
class Stack(): def __init__(self): self.dict = {} self.max_value = -1 self.min_value = 10000000000 #クラス変数を初期化 def initialization(self): self.dict = {} self.max_value = -1 self.min_value = 10000000000 #クラス変数の最大値・最小値をxに設定 def set_max_min(self,x): self.min_value = x if self.min_value > x else self.min_value self.max_value = x if self.max_value < x else self.max_value #クラス変数の最大値・最小値がxの場合、再設定 def del_max_min(self,x): if self.min_value == x: self.min_value = min(self.dict.keys()) if self.max_value == x: self.max_value = max(self.dict.keys()) #クラス変数の辞書にxを追加 def append(self,x): #クラス変数の辞書は、空かどうか if len(self.dict)>0: #クラス変数の辞書にxが含まれているかどうか if x in self.dict.keys(): self.dict[x] = self.dict[x]+1 else: self.dict[x] = 1 self.set_max_min(x) else: self.dict[x] = 1 self.set_max_min(x) #クラス変数の辞書からxを削除・減らす def pop(self,x,c): #クラス変数の辞書は、空かどうか if len(self.dict)>0: #クラス変数の辞書にxが含まれているかどうか if x in self.dict.keys(): del_num = min(c,self.dict[x]) self.dict[x] = self.dict[x] - del_num #クラス変数の辞書のxが無くなったかどうか if self.dict[x] == 0: self.dict.pop(x) if len(self.dict)>0: self.del_max_min(x) else: self.initialization() if __name__ == "__main__": stack = Stack() q = int(input()) for _ in range(q): q_i = list(map(int, input().split())) if q_i[0]==1: x = q_i[1] stack.append(x) if q_i[0]==2: x = q_i[1] c = q_i[2] stack.pop(x,c) if q_i[0]==3: print(stack.max_value - stack.min_value)
参考
- Python | 辞書の長さ(要素数)を取得する
- Pythonで辞書の要素を削除するclear, pop, popitem, del | note.nkmk.me
- Pythonで辞書の値の最大値・最小値とそのキーを取得 | note.nkmk.me
D. FizzBuzz Sum Hard
Point
- 以下のように包除原理で整理できる(数式っぽく書く方法が分からんかった…涙)
(1,...,nのうち、Aの倍数でもBの倍数でもないものの総数)= (1,...,nの総数) - (1,...,nのうち, Aの倍数 or Bの倍数の総数)= (1,...,nの総数)- (1,...,nのうち, Aの倍数の総数)- (1,...,nのうち, Bの倍数の総数)+ (1,...,nのうち, AとBの最小公倍数の倍数の総数)
- 最小公倍数を直接計算できる
lcmが使えないらしい //（整数除算）を意識しないと、値がずれるので注意
ソースコード
solution（クリックすると展開）
import math n,a,b = map(int, input().split()) c = a * b // math.gcd(a, b) ans = (1+n)*n//2 ans -= (n//a)*(a+(n//a)*a)//2 ans -= (n//b)*(b+(n//b)*b)//2 ans += (n//c)*(c+(n//c)*c)//2 print(ans)
