2022-09-16 ABC129 の A, B, C, D を解いた
ABC129 : AtCoder Beginner Contest 129 の A, B, C, D を解いた。
- A - Airplane
https://atcoder.jp/contests/abc129/tasks/abc129_a
- 提出: https://atcoder.jp/contests/abc129/submissions/34888953
(p + q).min(p + r).min(q + r)
- B - Balance
https://atcoder.jp/contests/abc129/tasks/abc129_b
- 提出: https://atcoder.jp/contests/abc129/submissions/34888998
- すべての区切りを試せば良い
- あらかじめ総和 S を求めておいて S_1 を決めて S_2 = S - S_1 として求めると良い
- C - Typical Stairs
https://atcoder.jp/contests/abc129/tasks/abc129_c
- 提出: https://atcoder.jp/contests/abc129/submissions/34889129
- 典型的な DP 問題であるカエルの問題に踏んではいけない場所が増えたもの
- 踏んではいけない場所を毎回先頭から探すと間に合わない
- HashSet などに入れるか、昇順になっていて一度出てくれば以降は出てこないことから添字をループの外側で管理してインクリメントすると良い
- D - Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d
- 提出: https://atcoder.jp/contests/abc129/submissions/34889252
- マスごとに毎回数えると到底間に合わない
- あらかじめ上下左右の各方向について
#に当たるまでの.の数を数えておくと良い - そうすれば各マスでは事前に求めた各方向の和 + 1 で求められるので
O(1)で求められるので間に合う
- E - Sum Equals Xor
https://atcoder.jp/contests/abc129/tasks/abc129_e
- パッと見で桁 DP で A XOR B によって遷移が決まるもので解けそうだけど時間がないのでパス
- F - Takahashi's Basics in Education and Learning
https://atcoder.jp/contests/abc129/tasks/abc129_f
- 着手せず
今日のコミット。