ABC173に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
結果
- コンテスト結果
- パフォーマンス、レーティング変動
反省点

解いた/挑んだ問題

A問題

問題の概要

N円の商品を買うとき、必要最小限の1000円札のみで支払う場合のおつりはいくらになりますか？

制約

$1 \leq N \leq 10000$
Nは整数

どのように考えたか

Nを1000で割ったあまりを求め、あまりがある場合1000から、Nを1000で割ったあまりを引いて出力
余りがないなら0を出力

結果

二回目でAC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int n;
    cin >> n;
    if (n % 1000) {
        cout << 1000 - (n % 1000) << endl;
    }
    else cout << 0 << endl;
}

焦ってしまい一回目でACすることができなかった

ACまでの時間

ACしたのはコンテスト開始から3分後です。

f:id:iiiimmmmo:20200705235046p:plain — ABC173_A

B問題

問題の概要

コンテストに参加してN回のジャッジ結果が"AC","WA","TLE","RE"のいずれかであった
各結果がそれぞれ何回ずつであったかを
[結果] × 回数　で一行ずつ出力せよ

制約

$1 \leq N \leq 10^5$
$S_iは$ "AC","WA","TLE","RE"のいずれか

どのように考えたか

for文の中でmapに結果をいれて、"AC","WA","TLE","RE"のキーで出現回数を出力

結果

一発AC
提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int n;
    string a;
    map<string, int>mp;
    cin >> n;
    rep(i, n) {
        cin >> a;
        mp[a]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
}

mapに入れてしまえば簡単だった

ACまでの時間

ACしたのはコンテスト開始から6分後です。

f:id:iiiimmmmo:20200705235235p:plain — ABC173_B

C問題

問題の概要

H行W列からなる白と黒で塗られているマス目が与えられる
そのうち、好きな行と好きな列を選んで赤く塗りつぶす
塗りつぶした後、残っている黒のマスがKと等しくなるような行列の選び方は何通りあるか

制約

$1 \leq H,W \leq 6$
$1 \leq K \leq HW$
$C_{i,j}$ は'.'または'#'

どのように考えたか

二重bit全探索をして、残った黒のマスがKと等しいかをカウントしていく

結果

一発AC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int h, w,key,black=0,cnt=0,tmp=0;
    string s;
    vector<string>grid;
    cin >> h >> w >> key;
    vector<int>bh(w, 0);
    vector<int>bw(h, 0);
    vector<int>hmemo,wmemo;
    vector<vector<int>>diffh(w,vector<int>(h,0));
    rep(i, h) {
        cin >> s;
        grid.push_back(s);
        for (auto c : s) {
            if (c == '#')black++;
            if (c == '#')bw[i]++;
        }
    }
    rep(i, w) {
        rep(j, h) {
            if (grid[j][i] == '#') {
                bh[i]++;
                diffh[i][j]++;
            }

        }
    }


    for (int i = 0; i < (1 << w); i++) {
        for (int k = 0; k < (1 << h); k++) {
            tmp = black;
            hmemo.clear();
            wmemo.clear();
            rep(j, w) {
                if (i & (1 << j)) {
                    tmp -= bh[j];
                    hmemo.push_back(j);
                }
            }
            rep(l, h) {
                if (k & (1 << l)) {
                    tmp -= bw[l];
                    wmemo.push_back(l);
                }
            }
            for (auto s : hmemo) {
                for (auto g : wmemo)tmp += diffh[s][g];
            }
            if (tmp == key)cnt++;
        }
    }
    cout << cnt << endl;
}