AtCoder Beginner Contest 045

[TakefumiYamamura]

http://abc045.contest.atcoder.jp/

[TakefumiYamamura]

C - たくさんの数式 / Many Formulas

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

配点 : 300 点

問題文

1 以上 9 以下の数字のみからなる文字列 S が与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。

ありうる全ての数式の値を計算し、その合計を出力してください。

制約

1≤|S|≤10 S に含まれる文字は全て 1 〜 9 の数字

#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long 

using namespace std;

int main(){
    string s;
    cin >> s;
    ll sum = 0;
    for (int i = 0; i < 1 << (s.length() - 1); ++i)
    {
        string tmp;
        for (int j = 0; j < s.length(); ++j)
        {
            tmp.push_back(s[j]);
            if(i >> j & 1){
                tmp.push_back('+');
            }
        }
        // cout << tmp << endl;
        int tmp_count = 0;
        for (int j = tmp.length()-1; j >= 0 ; --j)
        {
            if(tmp[j] != '+'){
                sum += ((ll)(tmp[j] - '0') * pow(10, tmp_count));
                // cout << ((int)(tmp[j] - '0') * pow(10, tmp_count)) << endl;
                tmp_count++;
            }else{
                tmp_count = 0;
            }
        }
    }
    cout << sum << endl;
}

[TakefumiYamamura]

D - すぬけ君の塗り絵 / Snuke's Coloring

時間制限 : 3sec / メモリ制限 : 256MB

配点 : 400 点

問題文

縦 H 行、横 W 列のマス目からなる盤があります。最初、どのマス目も白く塗られています。

すぬけ君が、このうち N マスを黒く塗りつぶしました。i 回目 ( 1≤i≤N ) に塗りつぶしたのは、 上から ai 行目で左から bi 列目のマスでした。

すぬけ君がマス目を塗りつぶした後の盤の状態について、以下のものの個数を計算してください。

各整数 j ( 0≤j≤9 ) について、盤の中に完全に含まれるすべての 3 行 3 列の連続するマス目のうち、黒いマスがちょうど j 個あるもの。

制約

3≤H≤109 3≤W≤109 0≤N≤min(105,H×W) 1≤ai≤H (1≤i≤N) 1≤bi≤W (1≤i≤N) (ai,bi)≠(aj,bj) (i≠j)

note

H*Wの配列を作ると間に合わないが９マス範囲内に点をふくむ正方形はたかだか9Nしかないので、 そこから攻めていく感じ

#include <iostream>
#include <map>
#include <set>
#define ll long long

using namespace std;

ll H, W, N;

int main(){
    cin >> H >> W >> N;
    int a, b;
    map<pair<int, int>, int> mp;

    for (int i = 0; i < N; ++i)
    {
        pair<int, int> p;
        cin >> a >> b;
        mp[pair<int, int>(a-1, b-1) ]++;
        mp[pair<int, int>(a-1, b) ]++;
        mp[pair<int, int>(a, b-1) ]++;
        mp[pair<int, int>(a, b) ]++;
        mp[pair<int, int>(a+1, b+1) ]++;
        mp[pair<int, int>(a+1, b) ]++;
        mp[pair<int, int>(a, b+1) ]++;
        mp[pair<int, int>(a+1, b-1) ]++;
        mp[pair<int, int>(a-1, b+1) ]++;
    }
    ll ans[10] = {0};
    ll size = 0;
    for (auto itr = mp.begin(); itr != mp.end(); ++itr)
    {
        if(itr->first.first > 1 && itr->first.second > 1 && itr->first.first < H && itr->first.second < W ){
            ans[itr->second]++;
            size++;
        }
    }
    ans[0] = (W - 2) * (H - 2) - size;

    for (int i = 0; i < 10; ++i)
    {
         cout << ans[i] << endl;
    }

}