🧪

AtCoder Beginner Contest 270 メモ(A-D)

2022/10/09に公開約1,200字

今回の結果

3AC

時間いっぱい使ってなんとかC問題まで解けた。
B問題も時間かかった。

A - 1-2-4 Test

https://atcoder.jp/contests/abc270/tasks/abc270_a

Difficulty: 45

参加中に考えたこと

全てのパターンを探すと (2^3)^2 通りあるからIF文だけで書くのはしんどい。
1,2,4点という数字からビット演算が思いつくのでどのビットが立っているかを判定すれば短いコードで処理ができる。

考察・感想

A問題でビット演算を出してくるのはびっくりした。ビット演算に触れたことがない人にとっては大変だったかもしれない。
自分はビット演算は全く使わないので慣れてなくて提出したコードは冗長なものになってた。
どちらかが解けた問題=ORで済む話だった。

B - Hammer

https://atcoder.jp/contests/abc270/tasks/abc270_b

Difficulty: 106

参加中に考えたこと

数直線上での X,Y,Z の位置関係を分岐すればよさそうだが、テストが通らないケースがあってはまった。
正の数と負の数で分岐するのは面倒なので、X<0 ならX,Y,Zの全てに-1をかければこの分岐を考える必要はなくなり、答えも変わらない。

考察・感想

公式解説と同じ解き方だった。
数直線は苦手意識があるのか詰まってしまいがち。

C - Simple path

https://atcoder.jp/contests/abc270/tasks/abc270_c

Difficulty: 625

参加中に考えたこと

DFSでやっても計算量は足りる。。よね。
経路を出力するのが面倒。DFSの過程で経路を保持しておく必要がある。
探索済かのフラグの配列と、経路の配列を持たせてDFSでコードを書いて提出するもTLEとMLEまで出てしまった。
原因を調べると、DFSの関数に配列を実体で渡してたからだった;
参照渡しにして無事AC。

考察・感想

経路を持つ配列をローカル変数にしたから失敗したけど、競プロにおいてはグローバル変数でやってる人の方が多いみたいだし、グローバル変数を使うことへの抵抗は捨ててしまうほうがいいのかな。

D - Stones

https://atcoder.jp/contests/abc270/tasks/abc270_d

Difficulty: 1300

参加中に考えたこと

問題文を見てまず思ったのが、条件を満たす最大の A_i を選び続けて勝てないケースがあるのか?ということ。
DPっぽいが漸化式が組み立てられなくて時間切れ。

考察・感想

解説を何度も読んでやっと理解できた。
コードはシンプルだけどどういうDPを作るかを考えられるかの問題だった。

Discussion

ログインするとコメントできます