AtCoder Beginner Contest 269 メモ(A-D)
今回の結果
2AC
今解いている問題で詰まった時に、そのまま頑張るか飛ばして次の問題に行くかは悩んでしまう。
今回は飛ばすのが正解だった。。
A - Anyway Takahashi
Difficulty: 8
参加中に考えたこと
すごく簡単な問題。
入力を受け取って数式に沿って計算した結果を1行目に出力し、2行目は決まった文字を出力すればよいだけ。
B - Rectangle Detection
Difficulty: 68
参加中に考えたこと
10x10の正方形の中に、１つの長方形ができるのでその４つの頂点の座標を求めたい。
どうするのが一番簡単なのか、実装の仕方に悩みが生じた。
スマートな方法がすぐに思いつかず、結局は左上の座標を取って、そこから右と下に # が連続している範囲を探して右上、左下の座標を取り、その２つから右下の座標を取るような方法でループで書いた。
10行目、10列目の時の考慮として、最初にb,dに10をセットして、ループの中で . が出たら . の1つ手前の値をセットするようにした。
考察・感想
4つの頂点を求める方向性はよかったけど、解説の解法2にある、 # の位置についての
C - Submask
Difficulty: 384
参加中に考えたこと
問題文が言っていることを理解するのに時間がかかった。
bitsetとDFSでできるかなと思ってコードを書いて提出したがWA。
ここで詰まってしまってACさせることができなかった。
考察・感想
1のビットが立っている桁についてbit全探索で順番に出力していくだけでよかったのか。
（DFSで解いてる回答もあった。）
その方針でコードを書いて提出するがいくつかのテストでWAになる。
WAになるテストケースを探す。
試しに
1
576460752303423488
576460752303423488
ここから情報落ちが起きていることが分かったので原因を探って修正する。
pow関数にlong longのキャストをつける必要があった。
以前にもpowではまったことがあったのでpowは自前で用意しておくほうがいいかも。
D - Do use hexagon grid
Difficulty: 612
考察・感想
コンテスト中には時間が足りずに解けなかったので後日解いてみた。
この問題は解説を見ずにACできた。
2次元ではなく6角形のグリッドを扱う問題については「初中級者が解くべき過去問精選 100 問」の問題で1回解いたことがある。
JOI 2012 予選 5 - イルミネーション
問題文にマスの隣接する関係は書かれているので、隣接しているかの判定にはそれに沿って以下のような定数を用意した。
const int dx[] = {-1, -1, 0, 0, 1, 1};
const int dy[] = {-1, 0, -1, 1, 0, 1};
隣接してる範囲を探すのにはキューをつかったBFSで行う。
よって方針として、探索済かどうかの情報を持つ二次元配列をもう1つ持った上で、BFSを行った回数＝求めたい答えとなる。
この問題でもう1つ考える必要がある点として、
なのでこの配列については0から始まるように、実際の座標の値から+1000したものとして扱うことでこれを解消した。
これでAC。
後で解説を確認したが、解き方としては想定解法と同じだった。
Discussion