AtCoder Beginner Contest 270 メモ(A-D)
今回の結果
3AC
時間いっぱい使ってなんとかC問題まで解けた。
B問題も時間かかった。
A - 1-2-4 Test
Difficulty: 45
参加中に考えたこと
全てのパターンを探すと
1,2,4点という数字からビット演算が思いつくのでどのビットが立っているかを判定すれば短いコードで処理ができる。
考察・感想
A問題でビット演算を出してくるのはびっくりした。ビット演算に触れたことがない人にとっては大変だったかもしれない。
自分はビット演算は全く使わないので慣れてなくて提出したコードは冗長なものになってた。
どちらかが解けた問題＝ORで済む話だった。
B - Hammer
Difficulty: 106
参加中に考えたこと
数直線上での X,Y,Z の位置関係を分岐すればよさそうだが、テストが通らないケースがあってはまった。
正の数と負の数で分岐するのは面倒なので、X<0 ならX,Y,Zの全てに-1をかければこの分岐を考える必要はなくなり、答えも変わらない。
考察・感想
公式解説と同じ解き方だった。
数直線は苦手意識があるのか詰まってしまいがち。
C - Simple path
Difficulty: 625
参加中に考えたこと
DFSでやっても計算量は足りる。。よね。
経路を出力するのが面倒。DFSの過程で経路を保持しておく必要がある。
探索済かのフラグの配列と、経路の配列を持たせてDFSでコードを書いて提出するもTLEとMLEまで出てしまった。
原因を調べると、DFSの関数に配列を実体で渡してたからだった；
参照渡しにして無事AC。
考察・感想
経路を持つ配列をローカル変数にしたから失敗したけど、競プロにおいてはグローバル変数でやってる人の方が多いみたいだし、グローバル変数を使うことへの抵抗は捨ててしまうほうがいいのかな。
D - Stones
Difficulty: 1300
参加中に考えたこと
問題文を見てまず思ったのが、条件を満たす最大の
DPっぽいが漸化式が組み立てられなくて時間切れ。
考察・感想
解説を何度も読んでやっと理解できた。
コードはシンプルだけどどういうDPを作るかを考えられるかの問題だった。
Discussion