🧵

AtCoder Beginner Contest 274 メモ(A-D)

2022/10/26に公開約1,100字

今回の結果

3AC

もう少し時間があればD問題に手が届いてた。
C問題とD問題の差が大きかったのでCまでだとRatingが下がるのが辛い。

A - Batting Average

https://atcoder.jp/contests/abc274/tasks/abc274_a

Difficulty: 23

参加中に考えたこと

小数第何位まで出力するかはprintf関数を使えば書式の設定ができたはず。
四捨五入か切り捨てかは分からなかったのでそこだけ確認して、問題なさそうだったのでprintf関数で一発。

B - Line Sensor

https://atcoder.jp/contests/abc274/tasks/abc274_b

Difficulty: 48

参加中に考えたこと

B問題なので全探索。 N の値も小さいので O(N^2) の計算量で解いても十分。
二次元配列に入れてもいいけど、文字なので文字列型の一次元配列に入れて列・行の二重ループで列ごとの # の数を数える。

考察・感想

列ごとに # の数を取りたいので答えとなる列の配列を用意して、入力を1文字ずつ読み込んで # があればその列の値をインクリメントするほうがシンプルな解き方ではあった。

C - Ameba

https://atcoder.jp/contests/abc274/tasks/abc274_c

Difficulty: 315

参加中に考えたこと

有向グラフと見立てて、入力を隣接行列に格納。
そこからキューを使ってBFSで順番に辿って行って深さを求めていく。

考察・感想

解説を見て呆然。。難しく考えすぎていた。
でも自分と同じくキューで解いた人もいるのでは?

D - Robot Arms 2

https://atcoder.jp/contests/abc274/tasks/abc274_d

Difficulty: 916

参加中に考えたこと

最初、この問題もキューを使って解けるかと考えた。
|x|,|y| \le 10^4 であればそこまで大きくないし、setを使って途中で座標が重複したものは1つとみなすようにすれば計算量は足りるだろう、と思ったがTLE。
DPで出来ないかと考えて、x,yの2軸でそれぞれのDPをしてやれば計算量は問題なさそう、というところに気付いたがコードを書く時間が残っておらずここまで。

考察・感想

コンテスト中に解き方に辿り着くことまでは出来たから、もう少し経験積めば緑Diffの問題が解けるようになれるかな。

Discussion

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