AtCoder Beginner Contest 129 A～DをPythonで解く
週末といえばABCですね
A、B、Cの3完でした
茶色になってからもレート上がったので一安心です
A - Airplane
3つの自然数のうち2つ選んだ時の和が最小となるのはどれか、という問題
この曲がめちゃくちゃ脳内再生されました
www.youtube.com
BTSのメンバーが出したソロ曲です
BTS、曲とダンス死ぬほどカッコいいのでチェックしてみてください
www.youtube.com
何を歌ってるのかは僕もまだ全然分かりません
3数から2数選んだ和は3通りありますが、3つ求めて最小取る実装をわざわざ書くのアレだなと思っていたら
3つの和から最大のヤツ引けばいい
と閃きました
めんどくさがることが良いプログラムを書くための足掛かりのひとつなのかもしれません、知らんけど
a, b, c = map(int, input().split()) print(a + b + c - max(a, b, c))
B - Balance
N個の自然数を前後2つに分けてそれぞれの総和を求めるとき、その差が最小となる切れ目はどこかという問題
Nがデカい時は違うやり方考えるんだろうなと思いながら愚直実装です
A、Bで「C問題以降でも計算量的にちゃんと大丈夫な解法」をスッと思いつく脳にしていきたいですね
制約が緩いことにかまけて愚直実装でササっと終えがちです、そんなに急いでやってるわけでもないのに...
n = int(input()) weights = list(map(int, input().split())) diff = sum(weights) for i in range(n): if abs(sum(weights[:i]) - sum(weights[i:])) < diff: diff = abs(sum(weights[:i]) - sum(weights[i:])) print(diff)
C - Typical Stairs
初見で「うわ今日のC問題動的計画法みたいな設定や...知らんけど...概要だけ知ってて実装したこと無い...」と狼狽えましたが
試しに紙に書いて考えてみたところ
- ある段にたどり着くには、一段下から来るのと二段下から来るのしか無い
- 三項間漸化式っぽいなー懐かしー
- 壊れた階段では「そこまで来る方法の総数がそのまま二段上にコピー(？)される」とみなす
- 「壊れた階段をスキップしたばかり」「そこから一段上った」「一段下と二段下の両方から来ることができる」の3状態しかない
などに気付いて実装してみました
もしかしてこれが動的計画法..？(知らんけど)
ムダが多い(inが冗長すぎ)と心配しながら提出したらTLEをくらったのがこちら
n, m = map(int, input().split()) broken = [int(input()) for _ in range(m)] ways = [0] * (n+1) ways[0] = 1 keep = 1 noway = False for i in range(1, n+1): if i in broken: if i-1 in broken: noway = True break ways[i] = ways[i-1] keep = 0 else: if keep == 2: ways[i] = ways[i-1] + ways[i-2] else: ways[i] = ways[i-1] keep += 1 print(ways[-1] % 1000000007 if not noway else 0)
- 3状態を遷移したい
- 全ての段でひとつ操作をして次へ、としたい
- 壊れている段は保持しておく
- 2段連続で壊れてたら0を表示するようにしとかないと
などの欲望を頭の中ごちゃごちゃのまま実装したら案の定TLEでした
inで調べる操作どう考えてもやりすぎてる
無事AC通ったのがこちら
n, m = map(int, input().split()) broken = [int(input()) for _ in range(m)] ways = [1] * (n+1) for i in broken: ways[i] = 0 keep = 1 for i in range(1, n+1): if ways[i]: if keep == 2: ways[i] = ways[i-1] + ways[i-2] elif keep == 1: ways[i] = ways[i-1] keep += 1 else: ways[i] = ways[i-2] keep += 1 else: keep = 0 print(ways[-1] % 1000000007)
シンプルになって動作時間も短いという素敵な結果です
プログラミングって世の中では数少ない「完全上位互換」が存在する世界ですよね
だいたいのものって何かしらのトレードオフ関係があるのでそこがプログラミング好きポイントのひとつです
D - Lamp
DSソフトのレイトン教授に似たような問題があったなぁと懐かしみながら22時過ぎから用事があったため見送りました
レイトン教授では全マスを照らすのに必要なランプの最小個数を求める問題でした
マジで良いゲームだったな...
解説を読んでAC通せたので掲載します
学びとして
- 「事前に計算しておくといいモノがある」というケースが存在する
- 2000×2000のマスはいくつ作ろうが計算量は
オーダーであり、作業が階層にならなければ大丈夫
がありました
計算量制約への苦手意識がまだ全然取れていないので、2つ目が自然な発想にまだ組み込まれていませんでした
本番でも解けなかったと思います
方針としては「そのマスから上下左右それぞれについてどれだけ照らせるかマップを作成する」のが肝ですね
h, w = map(int, input().split()) s = [input() for _ in range(h)] l = [[0] * w for _ in range(h)] r = [[0] * w for _ in range(h)] u = [[0] * w for _ in range(h)] d = [[0] * w for _ in range(h)] for i in range(h): for j in range(w): if s[i][j] == '.': l[i][j] = l[i][j-1] + 1 u[i][j] = u[i-1][j] + 1 if s[i][-j-1] == '.': r[i][-j-1] = r[i][-j] + 1 if s[-i-1][j] == '.': d[-i-1][j] = d[-i][j] + 1 torch = 0 for i in range(h): for j in range(w): torch = max(torch, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3) print(torch)
AtCoderを始めて考えをプログラムに起こす力が確実に上がりました
マジでやってよかったと既に思えるのではっぴーです
