🔤
ABC390の振り返り(Python)
ABC390の振り返り(Python)
ABC390に参加した結果の振り返りと学んだこと、今後の課題の備忘録
使用言語はPythonです
載せているコードは
- 提出したコードを多少いじったもの
- 回答などを見て書き直したりコメントだけしたりしたもの
のいずれかで、最適解とかではないです
提出結果
課題の多い回ですね...
Dは悪あがきで何回か愚直なコードを提出してます笑
A
"隣り合う"二つの項を一回だけ入れ替えて、昇順にできるかどうかを判定する問題です
問題文をよく読みましょう()
a = list(map(int, input().split()))
ans = 0
diff = []
for i in range(5):
if a[i] != i + 1:
ans += 1
diff.append(i)
if ans == 2 and (diff[1] - diff[0] == 1):
print('Yes')
else:
print('No')
B
- 比を整数のみだと勘違いして、
/
ではなく//
を使ってWA -
/
に書き換えたが、浮動小数点数の問題でどこかでWA(これですね) - Fractionというクラスを使って無理やりAC
from fractions import Fraction
n = int(input())
a = list(input().split())
b = Fraction(a[1]) / Fraction(a[0])
ans = 'Yes'
for i in range(1, n - 1):
if Fraction(a[i + 1]) / Fraction(a[i]) == Fraction(b):
continue
else:
ans = 'No'
break
print(ans)
解説のように整数で扱う方法をまず考えるのが良きですね
C
1 <= H,W <= 1000なので、全探索してa, b, c, dを見つけ、その範囲内に白がないことを確認すれば間に合います
h, w = map(int, input().split())
field = []
for i in range(h):
field.append(list(input()))
a = h
b = -1
c = w
d = -1
for i in range(h):
for j in range(w):
if field[i][j] == '#':
a = min(a, i)# 一番上に出てくる黒いマスの座標を更新していく
b = max(b, i)# 一番下 〃
c = min(c, j)# 一番左 〃
d = max(d, j)# 一番右 〃
ans = 'Yes'
for i in range(a, b + 1):
for j in range(c, d + 1):
if field[i][j] == '.':
ans = 'No'
break
print(ans)
D
緑になったばかりのやつに青diffは無理!
という言い訳は置いておいて...
- 元の袋を使って移し替えたりするのではなく、新しくグループを作っていくという考え方
- N個のものをグループに分ける方法
- ベル数による見積もり
以上のように勉強になる点が多い問題でした。また、実行時間制限が3秒であることから、ほかの問題より余裕がありそうということが読み取れるのかもしれないです。
- 袋を順番に見て行って、既存のグループに所属させるか新しくグループを作ってそこに所属させるかいていく(今回は最終的にグループ内の和を取るので、listを作るのではなく足し合わせていく)
- 最後の袋を見た後、xorを計算する
という流れを再帰で実装したのが以下になります
n = int(input())
a = list(map(int, input().split()))
ans = {}
def xor(ary):
global ans
n = 0
for i in ary:
n ^=i
ans[n] = 1
def recur(index , ary):
global a, n
if index == n:
xor(ary)
return
for i in range(len(ary)):
next_ary = ary[:]
next_ary[i] += a[index]
recur(index + 1, next_ary)
next_ary = ary[:]
next_ary.append(a[index])
recur(index + 1, next_ary)
recur(0, [])
print(len(ans))
ベル数についてはこちらが参考になりそうでした。
これらの枠組み(定義?)をもとに問題を見るだけでも考えが整理されたりすると思うので、頭に入れておきたいです。必要に駆られたらちゃんと計算を追っていこうと思います()
E
todo: dpできるようにする
反省点
課題は多いですが反省点は
- 問題文をよく読む
- 今やっている問題が解けなさそうであれば、E問題くらいまでは解けそうかどうか見てみる
くらいですね
感想
まだ知識も慣れも足りないなぁという感じです
焦らず楽しんでやっていこうと思います
入水まであと370!
Discussion