AtCoder ABC377 振り返り
AtCoder Beginner Contest 377 の振り返りです。
AtCoder Beginner Contest 377（Promotion of AtCoder Career Design DAY）
配点がいつもの100-200-300-400になっていたので、いつものペースで取り組めました。
BC問題がチェスを題材にしたものだったけれど、何でだったんだろうか？（377に関係するのかな？）
A: Solved
与えられた文字列が,"ABC"を入れ替えた文字列かどうかを判定する問題。 文字列をソートして、ABCと比較してYes or Noを出力してAC。
100点問題らしい問題でした。
2分以下でACできたのがちょっとうれしい。
B: Solved
チェスの盤面にルークが複数配置されており、そのときいずれのルークの移動範囲に被らないマスはいくつあるのかを数え上げる問題。
ルークの動きは単純に上下に動くだけなので、同一の列または行にルークが存在するかどうかを判定しすればよい。 行と列の二つの配列を定義して、各行と列のルークの個数を代入しておき、各マスにおいて同一行と同一列のルークの個数が0であるようなマスを全探索した。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<string> s(8);
vector<int> x(8,0),y(8,0);
int c = 0;
for(int i=0; i<8; i++){
cin >> s[i];
}
for(int i=0; i<8; i++){
rep(int j=0; j<8; j++){
if(s[i][j] == '#'){
x[i]++;
y[j]++;
}
}
}
for(int i=0; i<8; i++){
rep(int j=0; j<8; j++){
if(x[i] == 0 && y[j] == 0){
c++;
}
}
}
cout << c << endl;
}C: Solved
B問題のチェス盤のサイズを拡張して、ルークをナイトに置き換えた問題。
最初、愚直にナイトが移動できる箇所を二重配列上でマークしていこうと考えたけれど、明らかに計算量がオーバーするため断念。
どうにかしてナイトの移動先を重複なく管理できるかを考えたところで、Setを使うことを思いつく。
盤面のマスをpairで表現して、移動移動可能なマスをSetにInsertしていった。
盤面の外に出てしまうケースについては一旦盤全体を縦横に+1することで配列の外を参照しないようにして、最後に盤面外かどうかを判定するようにしたところ無事にACできた。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,m,c=0;
cin >> n >> m;
set<pair<int,int>> s;
for(int i=0; i<m; i++){
ll a,b;
cin >> a >> b;
s.insert(make_pair(a,b));
s.insert(make_pair(a+2,b+1));
s.insert(make_pair(a+1,b+2));
s.insert(make_pair(a-1,b+2));
s.insert(make_pair(a-2,b+1));
s.insert(make_pair(a-2,b-1));
s.insert(make_pair(a-1,b-2));
s.insert(make_pair(a+1,b-2));
s.insert(make_pair(a+2,b-1));
}
for (auto const &p: s) {
if(p.first < n+1 && p.first > 0 && p.second < n+1 && p.second > 0){
c++;
}
}
cout << (n*n) - c << endl;
}D: Unsolved
検討がつかずに早々に諦めてしまった。
答えを見たけれど、いまいちピンと来ていないので要復習。
E: Unsolved
D問題を諦めて、問題を見てみたところDPを使ったダブリングの問題かと思い挑戦してみる。結果、解けず。
所感
Highestの479になりRatingを更新したので、ひとまずは嬉しい。しかし、いつも通りC問題止まりでD問題には手もつけられなかった。
このままだと入緑までにまだまだ時間がかかりそうなので、もう少しD問題にも手をつけられるようになりたい。
ちゃんと勉強しよう。励もう。