AtCoder Beginner Contest 045 by C

AtCoder Beginner Contest 045　について
C言語での回答

atcoder.jp

できたもの
A

できなかったもの
B
C
D

問題A

#include <stdio.h>

int main(void){
    int a, b, h;
    int m2;

    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &h);

    m2 = (a+b)*h/2;

    printf("%d", m2);

    return 0;
}

方針

台形の面積を求める問題。
台形の公式は（上辺+下辺）×高さ÷2なのでそれを出力。

問題B

#include <stdio.h>

int main(void){
    char a[100], b[100], c[100], point;

    scanf("%s %s %s", a, b, c);

    point = a[0];
    int i = 0;
    int j = -1;
    int k = -1;

    while(1){
        if(point == 'a'){
            i++;
            if(a[i]=='\0'&&i>=0){
                printf("A\n");
                break;
            }
            point = a[i];
        }
        else if(point == 'b'){
            j++;
            if(b[j]=='\0'&&j>=0){
                printf("B\n");
                break;
            }
            point = b[j];
        }
        else{
            k++;
            if(c[k]=='\0'&&k>=0){
                printf("C\n");
                break;
            }
            point = c[k];
        }
    }

    return 0;
}

方針

それぞれの文字列を配列に入れ、ターンが来るごとに添え字を+１して中身を見て、次の人に飛んで……ということを繰り返します。終端文字\0に来たらその人が勝ち。

解けなかった原因

文字列を配列の添え字で見て行けばよいものを文字を消そうとしていたため。

問題C

#include <stdio.h>
#include <string.h>

int main(void){
    int i,j,n;
    char s[11];
    scanf("%s", s);
    n = strlen(s);

    long long ans = 0, sum = 0;
    //選んだ組み合わせと整数値と対応づけ
    for(i=0;i<(1<<(n-1));i++){
        for(j=0;j<n;j++){
            sum *= 10;
            sum += s[j] -'0';
            
            //bit全探索で整数値と対応付ける
           //1<<j：j桁のみを残して他の桁を0にする
            if(i & (1<<j)){
                ans += sum;
                sum = 0;
            }
        }
        ans += sum;
        sum = 0;
    }

    printf("%lld\n", ans);

    return 0;
}

方針

数字の間に+を入れる入れないの判断は2(n-1)、nが最大でも10なので全探索ができます。
ビット演算子を使用してフラグ管理をするようです。

以下を読めばビット全探索についてよく分かると思います
drken1215.hatenablog.com

要点を述べると、
・ビット全探索は、Ｎ個の中から選ぶ組み合わせ一つ一つと整数値を一対一で対応付けるもの
・選んだ桁を1としてフラグを立て、それを十進数に直すと整数値が得られる
というものです

sumとi、jとビットAND演算の結果
青字はjのループを抜けて加算されるもの、オレンジが途中で加算されるもの

変化を一つずつ追ったもの：クリックで展開

i=0
sum：1
000
001
000

sum：12
000
010
000

sum：125
000
100
000

i=1

sum：1
001
001
001

sum：2
001
010
000

sum：25
001
100
000

i=2
sum：1
010
001
000

sum：12
010
010
010

sum：5
010
100
000

i=3

sum：1
011
001
001

sum：2
011
010
010

sum：5
011
100
000

わかりやすく書くと

i=	0	1	2	3
j=0	1	1	1	1
1	12	2	12	2
2	125	25	5	5

4文字の場合に考えてみると、以下のようになり、フラグが立った箇所だけを抜き出せるため、全探索ができていることがわかります

i=	0	1	2	3	4	5	6	7
j=0	000	001	010	011	100	101	110	111
1		〇		〇		〇		〇
2			〇	〇			〇	〇
3					〇	〇	〇	〇

n≦20くらいでないと使えないところに注意。反対にその程度の範囲であればbit全探索を疑うとよさそう。

問題D

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

map<pair<int,int>, int> m;

int main() {
    int h, w, n;
    vector<ll> a(10);
	cin >> h >> w >> n;
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		for (int dx = 0; dx < 3; dx++){
			for (int dy = 0; dy < 3; dy++){
				if (x - dx >= 0 && y - dy >= 0 && x - dx < h - 2 && y - dy < w - 2){
					m[make_pair(x - dx, y - dy)]++;
                }
            }
        }
	}

  	//正方形の総数
	a[0] = ll(h - 2) * (w - 2);
	for (auto x : m) {
		a.at(0)--;
		a.at(x.second)++;
	}
	for (int i = 0; i < 10; ++i)
		cout << a[i] << endl;
}

方針

mapとかpairの概念がなくてC言語だと無理ゲーだったのでC＋＋でやりました許して。
数が非常に大きく、愚直にマスをぬり後から3×3の正方形でチェックしていくとまず間に合いません。
そのため塗ったマスがどの3×3の正方形に影響をあたえるかを調べます。これだと一つのマスあたり最大9個調べればいいです。
dxとdyを0~2に変化させて引くことで上と左にマスを3つほどずらして調べられます。
また正方形のマスがはみ出していてはダメなので、x-dxはh-2未満とy-dyはw-2未満を満たしている必要があります。

入力例1における一部のカウントの仕方を図示してみました。

pairで3×3正方形の左上の座標を、mapの第二要素でそのマス内の塗られた正方形の数をカウント。
最後に黒いマスを0~9個含む正方形の数を数えますが、まず全体に含まれる3×3の正方形の数はh-2×w-2。すべての正方形において塗られたマスが0個として初期化。
mapの第二要素がその座標を左上とする正方形内に含まれる黒いマスなのでそれぞれ数え、1個以上の正方形の場合はトータルの数から引いて行けば実際に塗られたマスが0個の正方形の数も求まります。