AtCoder Regular Contest 006 D 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Regular Contest 006 D
結局、他の人の提出コードを参考にしてAC。
今日の問題はアルファベット探し！太古のARCのD問題！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 23, 2019
現行システムだと500点問題くらい？競プロ慣れしてない人でもチャレンジできる難問！
水色の人でもけっこう苦戦するんじゃないかなあ。#chokudai今日の一問 https://t.co/47xE9HJYHp
D - アルファベット探し
与えられた図の中から A、B、C の図形がそれぞれ何個あるか数える問題。
解いた方針
各図形のマスを数える
30分くらい考えていたら、 各図形を形作っている黒マスの数がそれぞれ異なっていることに気づいた。
- Aは12マス
- Bは16マス
- Cは11マス
さらに、 図形を整数倍してもそれぞれのマスの数は判別できそうだった。
- 図形を2倍にすると、マスの数は2*2=4倍
- 図形を3倍にすると、マスの数は3*3=9倍
- 図形を4倍にすると、マスの数は4*4=16倍
- ......
各図形を整数倍したときのマスの数
| 倍 | Aのマス数 | Bのマス数 | Cのマス数 |
|---|---|---|---|
| 1 | 12 | 16 | 11 |
| 2 | 12x2x2=48 | 16x2x2=64 | 11x2x2=44 |
| 3 | 12x3x3=108 | 16x3x3=144 | 11x3x3=99 |
| 4 | 12x4x4=192 | 16x4x4=256 | 11x4x4=176 |
| ... | ... | ... | ... |
つまり黒マスの数をカウントすれば、 その図形が A なのか、B なのか、C なのかが判別できる。
一つの図形のマスだけを数える方法
まず、黒マスを一つ見つける。
見つけた黒マスの周り8マスの見て、 また黒マスがあればそちらに移動する。
この処理を再帰的に行う。
こんな感じで黒マスを5つカウントできた（カウントの順番は実装方法によるため、図の通りになるかは分からない）。
コード
数えるところまでは実装できたけど、 図形の判別方法でおかしくなってしまった。
WAの原因が分からなかったので、 同じころに提出してACしていたta7uwさんのコードを参考にしたらACした（ありがたい）。
ta7uwさんの提出コード：
自分が提出したコード：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<string> field(10010);
int ans[3] = {0};
int cnt = 0;
void painting(int i, int j)
{
for(int x: dx) {
for(int y: dy) {
if(field[i+x][j+y] == 'o') {
cnt++;
field[i+x][j+y] = '.';
painting(i+x, j+y);
}
}
}
return;
}
int check(int a)
{
for(int i = 2; i*i <= a; i++) {
while(a % (i*i) == 0) a /= (i*i);
}
return a;
}
int main()
{
int H, W; cin >> H >> W;
for(int i = 0; i < H; i++) {
cin >> field[i];
}
for(int i = 1; i < H-1; i++) {
for(int j = 1; j < W-1; j++) {
if(field[i][j] == 'o') {
cnt = 0;
painting(i, j);
int a = check(cnt);
if(a == 3) ans[0]++;
else if(a == 1) ans[1]++;
else if(a == 11) ans[2]++;
}
}
}
cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
return 0;
}
おわりに
ふつうに難しかった。
