🛷

AtCoder Beginner Contest 272 メモ(A-D)

2022/10/16に公開

AtCoder

tech

今回の結果

4AC
パフォーマンス更新。
C問題が易しかったからDまで解けてよかった。

A - Integer Sum

Difficulty: 8

参加中に考えたこと

要素を順番に足していくだけ。
非常にやさしい。

B - Everyone is Friends

Difficulty: 139

参加中に考えたこと

$N \times N$ のチェック用の二次元配列を持って、各舞踏会ごとにペアになったかのフラグを立てる。
最終的にチェック用の二次元配列を調べて、対角線以外のところでチェックがついていないところがなければ Yes を、チェックがついていないところがあれば No を出力すればよい。

C - Max Even

Difficulty: 167

参加中に考えたこと

2要素の和における偶奇のパターンとしては以下の３つである。

偶数＋偶数＝偶数
奇数＋奇数＝偶数
偶数＋奇数＝奇数

求めたいのは偶数なので、Aの入力を偶数と奇数の２つの配列に分けていれて、それぞれをソートすれば配列の後ろから2つが最大値を求める際に使う要要素になる。
あとは、配列の要素が2つに満たない場合の考慮を入れてあげる。これでAC。

考察・感想

C問題にしてはかなり易しい部類の問題。

D - Root M Leaper

Difficulty: 804

参加中に考えたこと

方針を立てるのに少し悩んだ。
$(i,j)$ から $(k,l)$ に移動できるということは、 $\sqrt{M}$ を斜辺、 $|i-k|$ , $|j-l|$ を残りの2辺とするとする直角三角形ができるはず。
式を変形して、 $M = (i-k)^2+(j-l)^2$ を満たす $(k,l)$ を探す必要がある。
この縦と横の移動距離がいくつになるかを先に求めてしまおうと考えた。
$N \le 400$ より、 $400 \times 400$ の二重ループで距離が $M$ になるパターンを探す。

縦と横の移動距離が求まれば、最終的に求めたいのは $(1,1)$ から何回操作を行えば移動できるかの回数なので、ここはBFSで行う。
移動距離が決まっても上下左右の4方向に移動できる可能性があるので、各方向について移動可能かを調べていく。

これでうまくいくかなと思ったらいくつかのケースでWAに。
何かしら考慮が漏れているところを探していると、1回の移動距離のパターンを1つ見つけたら終了させていたが2つ以上あることに気付く。
例えば、 $M=5$ の場合は、 $(3,4),(0,5)$ の2通りあるので、最初の縦横の移動距離を調べるところを全て調べるようにすることでACできた。

考察・感想

公式解説や多くの提出では前処理を使う解き方が多かったけど、中には前処理なしでBFSの中で移動できる範囲を探しているやり方で解いてる人もいますね。

今回の結果

A - Integer Sum

参加中に考えたこと

B - Everyone is Friends

参加中に考えたこと

C - Max Even

参加中に考えたこと

考察・感想

D - Root M Leaper

参加中に考えたこと

考察・感想

Discussion