🩹

AtCoder Beginner Contest 269 メモ(A-D)

2022/09/23に公開

今回の結果

2AC

今解いている問題で詰まった時に、そのまま頑張るか飛ばして次の問題に行くかは悩んでしまう。
今回は飛ばすのが正解だった。。

A - Anyway Takahashi

https://atcoder.jp/contests/abc269/tasks/abc269_a

Difficulty: 8

参加中に考えたこと

すごく簡単な問題。
入力を受け取って数式に沿って計算した結果を1行目に出力し、2行目は決まった文字を出力すればよいだけ。

B - Rectangle Detection

https://atcoder.jp/contests/abc269/tasks/abc269_b

Difficulty: 68

参加中に考えたこと

10x10の正方形の中に、1つの長方形ができるのでその4つの頂点の座標を求めたい。
どうするのが一番簡単なのか、実装の仕方に悩みが生じた。

スマートな方法がすぐに思いつかず、結局は左上の座標を取って、そこから右と下に # が連続している範囲を探して右上、左下の座標を取り、その2つから右下の座標を取るような方法でループで書いた。
10行目、10列目の時の考慮として、最初にb,dに10をセットして、ループの中で . が出たら . の1つ手前の値をセットするようにした。

考察・感想

4つの頂点を求める方向性はよかったけど、解説の解法2にある、 # の位置についての max(i), min(i), max(j), min(j) の4つを取るのがシンプルにやる方法だった。

C - Submask

https://atcoder.jp/contests/abc269/tasks/abc269_c

Difficulty: 384

参加中に考えたこと

問題文が言っていることを理解するのに時間がかかった。
bitsetとDFSでできるかなと思ってコードを書いて提出したがWA。
ここで詰まってしまってACさせることができなかった。

考察・感想

1のビットが立っている桁についてbit全探索で順番に出力していくだけでよかったのか。
(DFSで解いてる回答もあった。)
その方針でコードを書いて提出するがいくつかのテストでWAになる。

WAになるテストケースを探す。
試しに 576460752303423488 ( = 2^{59}+1) で正しい値が返ってくるかを試すと以下のような結果が得られた。

1
576460752303423488
576460752303423488

ここから情報落ちが起きていることが分かったので原因を探って修正する。
pow関数にlong longのキャストをつける必要があった。
以前にもpowではまったことがあったのでpowは自前で用意しておくほうがいいかも。

D - Do use hexagon grid

https://atcoder.jp/contests/abc269/tasks/abc269_d

Difficulty: 612

考察・感想

コンテスト中には時間が足りずに解けなかったので後日解いてみた。
この問題は解説を見ずにACできた。

2次元ではなく6角形のグリッドを扱う問題については「初中級者が解くべき過去問精選 100 問」の問題で1回解いたことがある。

JOI 2012 予選 5 - イルミネーション
https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e

問題文にマスの隣接する関係は書かれているので、隣接しているかの判定にはそれに沿って以下のような定数を用意した。

const int dx[] = {-1, -1, 0, 0, 1, 1};
const int dy[] = {-1, 0, -1, 1, 0, 1};

X_i, Y_i の範囲はせいぜい 4 \times 10^6 なので各マスについで順に調べていく方法でも制限時間内に処理が完了する。
隣接してる範囲を探すのにはキューをつかったBFSで行う。
よって方針として、探索済かどうかの情報を持つ二次元配列をもう1つ持った上で、BFSを行った回数=求めたい答えとなる。

この問題でもう1つ考える必要がある点として、X_i, Y_i の範囲にマイナスもあるので、探索済かの二次元配列を-1000から始めることができない。
なのでこの配列については0から始まるように、実際の座標の値から+1000したものとして扱うことでこれを解消した。

これでAC。
後で解説を確認したが、解き方としては想定解法と同じだった。

Discussion