ながめも

競技プログラミングについて

ABC096 C - Grid Repainting 2

AtCoder

ABC096 C - Grid Repainting 2

グリッド問題。
問題は以下。

atcoder.jp


〜考え方〜
全探索。
'#'の上下左右が全て'.'のところが一つでもあったら"No"。

rep1(i, N)（1から始まるloop）を定義してやるとやりやすいと思ったので、Snippetにも追加した。

コードは以下。
Submission #4230493 - AtCoder Beginner Contest 096

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()

int main() {
	int H,W;
	cin>>H>>W;
	vector<string> S(H);
	rep(i,H){
		cin>>S[i];
	}
	string ans = "Yes";
	rep1(i,H-1)rep1(j,W-1)
	if(S[i][j] == '#')
	if(S[i+1][j]!='#'&&S[i][j+1]!='#'&&S[i-1][j]!='#'&&S[i][j-1]!='#')
	ans = "No";

	cout<<ans<<endl;
}

ABC075 B-Minesweeper グリッド

AtCoder

ABC075 B-Minesweeper

C++のグリッド問題を初めて真面目にやりました。
問題は以下。

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文H×W のマス目が与えられます。 入力において、全てのマスは文字で表されており、.は空きマス、 # は爆弾マスに対応します。 マス目は H 個の文字列 S1,...,SH で表されます。 文字列 Si の j 文字目は、マス目の上から i 番目、左から j 番目のマスに対応します。(1≦i≦H,1≦j≦W)イルカは各空きマスの上下左右および斜めの 8 方向で隣接しているマスに爆弾マスが何個あるか気になっています。 そこで、各空きマスに対応する . を、その空きマスの周囲8方向に隣接するマスにおける爆弾マスの個数を表す数字で置き換えることにしました。

以上の規則で置き換えられた後のマス目を出力してください。

制約1≦H,W≦50
Si は # と . からなる長さ W の文字列


〜考え方〜
高々50^2なので全探索。
グリッドの問題では、vectorで行を受けて、列はそのstringの位置を指定する形でやる。（？）

周囲8方向はdxとdyをそれぞれ-1,0,1の二重ループをまわす。
dx = dy = 0のときは移動しないが、'.'の周りをみているので、それをカウントする心配はない。

コードは以下。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int main() {
	int H,W;
	cin>>H>>W;
	vector<string> S(H);
	rep(i,H)cin>>S[i];

	rep(i,H)rep(j,W){
		if(S[i][j] == '.'){
			S[i][j]='0';
			for (int dx = -1; dx <= 1; ++dx){
				for (int dy = -1; dy <= 1; ++dy){
					int nx = i+dx,ny = j+dy;
					if(0<=nx&&nx<H&&0<=ny&&ny<W){
						if(S[nx][ny]=='#')S[i][j]++;
					}
				}
			}
		}
	}
rep(i,H)cout<<S[i]<<endl;
}

AtCoder ABC114 C-755 深さ優先探索

AtCoder

ABC114 C-755

初めて深さ優先探索（Depth-First Search）を書いたのでブログに書きます。（なんとなく）
問題は以下。

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300点

問題文
整数 N が与えられます。1 以上 N 以下の整数のうち、七五三数 は何個あるでしょうか？

ここで、七五三数とは以下の条件を満たす正の整数です。

十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

制約
1≤N<10^9
Nは整数である。


〜考え方〜
9桁なので、それぞれの桁が3 or 5 or 7の場合を全て調べても3^9で済む。
全列挙は深さ優先探索を用いる（本番解いたときは直積とか使って無理矢理数えた）。
7,5,4がそれぞれ一回以上現れないといけないので、それをどう表現するかが少し悩みどころ。
a,b,cの初期値を0(false)にしておいて、
3が出たらaを1に変更、
5が出たらbを1に、
7が出たらcを1にという風にしたあと、
a&b&cを取るときれいに書けるっぽい。
単純に数えてもいいけど、無駄も多そう。
あとans++する前にx<=Nを考えておく。

変数の宣言をどこにするかがまだ悩むけど、たぶんdfsとmainで共通のやつはその外で定義して、
dfs内だけで使うやつは引数のところでいいのかな。たぶん。

コードは以下。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll N;
int ans = 0;
void dfs(ll x,int a,int b,int c){
	if(x>N) return;
	if(a&b&c)ans++;
	dfs(10*x+3,1,b,c);
	dfs(10*x+5,a,1,c);
	dfs(10*x+7,a,b,1);
}

int main() {
	cin>>N;
	dfs(0,0,0,0);
	cout<<ans<<endl;
}