[ABC407] ABC 407(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
- 切り捨て
ceilと切り上げfloorを求める。 -
realと差分が近い方を答えとする。
A.py
"""
<方針>
- 切り捨て `ceil` と切り上げ `floor` を求める。
- `real` と差分が近い方を答えとする。
"""
# 入力
A, B = map(int, input().split())
# A/Bを計算
real = A/B
# 切り上げを計算
ceil = (A+B-1)//B
# 切り捨てを計算
floor = A//B
# 切り上げのほうが差分が小さいとき、
if((ceil - real) < (real - floor)):
print(ceil)
# 切り捨てのほうが差分が小さいとき、
else:
print(floor)
B問題
- 余事象を考える。
-
6x6の全部の出目を考えて、notXかつnotYとなる回数を数える。 -
36からそれらを引けば良い。
-
- あとは
36で割れば良い。
B.py
"""
<方針>
- 余事象を考える。
- `6x6` の全部の出目を考えて、`notX` かつ `notY` となる回数を数える。
- `36` からそれらを引けば良い。
- あとは `36` で割れば良い。
"""
# 入力
X, Y = map(int, input().split())
# 余事象の数
notXY = 0
# 6x6パターンを考える。
for i in range(1, 7):
for j in range(1, 7):
# not X かつ not Y
if(
not (X <=i+j) and
not (Y <= abs(i-j))
):
notXY += 1
# 求めたい方に変える。
XY = 36-notXY
# 確率を求める。
ans = XY/36
# 出力
print(ans)
C問題
方針
- 文字列を後ろから見ていき、
0になるまで、Aボタンを押し、0になったらBボタンを押して、次の文字をみれば良いと思う。 - だけど、
N = len(S)とし、Bボタンの操作（毎回全ての文字列tを書き換える）をすると、O(N^2)みたいになっちゃう。 - そこで、どれだけ今まで
Aボタンを押したかを記録しておけば、毎回前方の文字を操作しなくてもいいよね。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 文字列を後ろから見ていき、`0` になるまで、`A` ボタンを押し、`0` になったら `B` ボタンを押して、次の文字をみれば良いと思う。
- だけど、`N = len(S)` とし、`B` ボタンの操作（毎回全ての文字列 `t` を書き換える）をすると、`O(N^2)` みたいになっちゃう。
- そこで、どれだけ今まで `A` ボタンを押したかを記録しておけば、毎回前方の文字を操作しなくてもいいよね。
"""
# [s_1, s_2, ..., s_N] を数字として受け取る
S = list(map(int, list(input())))
cntA = 0
cntB = 0
# 後ろから見ていく。
for s in reversed(S):
# 今まで押したボタンBの回数を反映させた上で、必要か回数を登録する。
cntB += (s - cntB)%10
# `0` になったので、ボタンAを押す。
cntA += 1
# 出力
print(cntA+cntB)
D問題
- ドミノで隠せる全パターンを考えて最適解を出力すれば良さそう。
-
Pythonなので、非再帰DFSで実装しよう。-
qに、それぞれのマスにドミノを縦に置く-1と横に置く+1と置かない0を格納して考える。
-
-
bit演算は^=で簡単に求まるよ。
D.py
"""
<方針>
- ドミノで隠せる全パターンを考えて最適解を出力すれば良さそう。
- `Python` なので、非再帰 `DFS` で実装しよう。
- `q` に、それぞれのマスにドミノを縦に置く `-1` と横に置く `+1` と置かない `0` を格納して考える。
- `bit` 演算は `^=` で簡単に求まるよ。
"""
# 入力
H, W = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(H)]
# 最大値
ans = 0
# 非再帰キュー
q = []
# 初期値を登録
q.append([0])
if(H > 1):
q.append([-1])
if(W > 1):
q.append([+1])
# 非再帰
while q:
B = q.pop() # DFS
# それぞれのマスが隠されていると `1` が格納される。
table = [[0]*W for _ in range(H)]
# ドミノで盤面を隠す
for i, b in enumerate(B):
if(b != 0):
h, w = divmod(i, W)
table[h][w] += 1
if(b == -1):
table[h+1][w] += 1
if(b == +1):
table[h][w+1] += 1
# まだ、全ての位置にドミノを置くかどうか決まってない時、
if(i < H*W):
# 次のマスでドミノを置かない
q.append(B+[0])
h, w = divmod(i+1, W)
if(w+0 < W and h+1 < H and table[h][w] == table[h+1][w] == 0):
# 次のマスでドミノを縦に置く
q.append(B+[-1])
if(w+1 < W and h+0 < H and table[h][w] == table[h][w+1] == 0):
# 次のマスでドミノを横に置く
q.append(B+[+1])
# 全てのマスにドミノを置くかどうか決まった時、
else:
tmp = 0 # 解
for h in range(H):
for w in range(W):
# ドミノで隠れてない時、
if(table[h][w] == 0):
# 排他的論理和
tmp ^= AA[h][w]
# 更新
ans = max(ans, tmp)
# 出力
print(ans)
E問題
- 貪欲に行こう。
- 右から
parenthesesをペアで追加して、その際、左にある任意の)の中で最大値と取り換えればいけそう。 - 最大値の保持には
heapqを使えば、logNなので、多分O(NlogN)でいけそう。
E.py
"""
<方針>
- 貪欲に行こう。
- 右から `parentheses` をペアで追加して、その際、左にある任意の `)` の中で最大値と取り換えればいけそう。
- 最大値の保持には `heapq` を使えば、`logN` なので、多分 `O(NlogN)` でいけそう。
"""
import heapq
T = int(input())
for _ in range(T):
q = []
N = int(input())
ans = 0 # 解
for i in range(N):
a1 = int(input())
a2 = int(input())
# 新入りのカッコの左について検討する。
# キューがある時は、
if(q):
# 最大値を取得する。
x = -heapq.heappop(q)
# 新入りの方が値が大きい時、
if(x < a1):
# キューを戻す。
heapq.heappush(q, -x)
# 新入りを答えに記入する。
ans += a1
# キューの方が大きい値が格納されている時、
else:
# 新入りをキューに入れる。
heapq.heappush(q, -a1)
# キューの最大値を答えに記入する。
ans += x
# まだキューが空の時は、
else:
# 新入りを答えに記入する。
ans += a1
# 新入りのカッコの右については必ずキューに格納する。
heapq.heappush(q, -a2)
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- My Thoughts When Solving the Problem C
- いいや!「限界」だッ!押すねッ! 『今だッ』!