Atcoder Beginner Contest 076 参加した。

abc076.contest.atcoder.jp


114514年振りに投下しておく、Cで詰まってD問題考えてるうちに終わった。



A問

かけてひくだけ

#include <cstdio>
 
int r, g;
 
int main(){
    scanf("%d %d", &r, &g);
 
    printf("%d\n", g * 2 - r);
 
    return 0;
}

B問

2倍した場合とK足した場合で増分の小さい方を選んでN回足す

#include <cstdio>
#include <cmath>
 
int n, k;
 
int main(){
    scanf("%d %d", &n, &k);
 
    int ans = 1;
    for(int i = 0; i < n; i++){
        if(ans * 2 < ans + k){
            ans *= 2;
        }else{
            ans += k;
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}


C問

辞書順を考慮してSの後ろからTと一致する部分を探索する、
(?部分はaで埋めるのでa以外の文字が含まれるかもしれないTはS'の後ろにあった方が都合がいい)

SとTが最大の長さでも調べるのは50×50回なので全部調べても問題なし。

#include <iostream>
#include <string>
 
std::string str, t;
 
int main(){
    std::cin >> str >> t;
 
    int k = -1;
    for(int i = str.size() - 1; i >= t.size() - 1; i--){
        bool flag = true;
        for(int j = t.size() - 1; j >= 0; j--){
            if((str[i + j - t.size() + 1] != t[j]) &&
                str[i + j - t.size() + 1] != '?'){
 
                flag = false;
                break;
            }
        }
 
        if(flag){
            k = i - t.size() + 1;
            break;
        }
    }
 
    if(k == -1){
        std::cout << "UNRESTORABLE\n";
    }else{
        int c = 0;
        for(int i = 0; i < str.size(); i++){
            if(k <= i && i < k + t.size()){
                str[i] = t[c++];
            }else if(str[i] == '?'){
                str[i] = 'a';
            }
        }
 
        std::cout << str << std::endl;
    }
 
    return 0;
}


うんこードを書いた日だった、寝る。

AOJ 0072 Carden Lantern

灯篭 | Aizu Online Judge


最小全域木問題、114514810は何の関係もない

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

int ma[100][100];

int main() {
	int n, m, a, b, d;
	char t;
	while (cin >> n) {
		if (n == 0) break;
		cin >> m;

		fill(ma[0], ma[100], 114514810);
		for (int i = 0; i < m; i++) {
			cin >> a >> t >> b >> t >> d;
			ma[a][b] = ma[b][a] = (d - 100) / 100;
		}

		bool v[100] = {false};
		v[0] = true;
		d = 0;
		for (int i = 0; i < n - 1; i++) {
			m = 114514810;
			for (int j = 0; j < n; j++) {
				if (ma[0][j] < m && !v[j]) {
					m = ma[0][j];
					b = j;
				}
			}
			v[b] = true;
			d += ma[0][b];
			for (int j = 0; j < n; j++) {
				ma[0][j] = min(ma[0][j], ma[b][j]);
			}
		}
		cout << d << endl;
	}
	return 0;
}

AOJ 0071 Bombs Chain

爆弾の連鎖 | Aizu Online Judge


(´・ω・`)

#include <iostream>
#include <string>
using namespace std;

bool map[8][8] = { 0 };
int siz[3] = { 1,2,3 }, dir[2][4] = { {1,0, -1,0},{0,1,0,-1} };
void bomb(int x, int y) {
	if (x < 0 || y < 0 || x >= 8 || y >= 8 || !map[y][x]) return;

	map[y][x] = false;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 3; j++) {
			bomb(x + dir[0][i] * siz[j], y + dir[1][i] * siz[j]);
		}
	}
}

int main() {
	int n, x, y;
	string str;
	cin >> n;
	for (int l = 1; l <= n; l++) {
		for (int i = 0; i < 8; i++) {
			cin >> str;

			for (int j = 0; j < 8; j++) {
				if (str[j] == '1') map[i][j] = true;
				else map[i][j] = false;
			}
		}
		cin >> x >> y;
		bomb(x - 1, y - 1);

		cout << "Data " << l << ":" << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				cout << map[i][j];
			}
			cout << endl;
		}
	}

	return 0;
}

AOJ 0070 Combination of Number Sequences

組み合わせの個数 | Aizu Online Judge


先に計算をしておく、s > 330 の場合はないので0個にしてしまう
(最大の数1*0+2*1+3*2+4*3+5*4+6*5+7*6+8*7+9*8*10*9=330であるため)

#include <iostream>
using namespace std;

int n, s, res[10][330] = { 0 };
bool num[10] = { 0 };
void combinations(int c, int sum) {
	if (c == 11) return ;
	for (int i = 0; i < 10; i++) {
		if (num[i]) continue;
		num[i] = 1;
		++res[c + 1][sum + i * (c + 1)];
		combinations(c + 1, sum + i * (c + 1));
		num[i] = 0;
	}
}

int main() {
	combinations(0, 0);
	while (cin >> n) {
		cin >> s;
		if (s > 330) {
			n = 0;
			s = 0;
		}
		cout << res[n][s] << endl;
	}
	return 0;
}

AOJ 0069 Drawing Lots II

あみだくじ | Aizu Online Judge


各階層の両側に線がない('1000'の3つ目4つ目みたいな)とこに線があった場合のあみだくじを一番上の一番左から順に解いていった

#include <iostream>
#include <string>
#include <numeric>
#include <vector>
using namespace std;

#define PAIR pair<int, int>

int lot[30][10];
int n, m, a, d;
int solve(int n) {
	for (int i = 0; i < d; i++) {
		if (lot[i][n] == -1) continue;
		n = lot[i][n];
	}
	return n;
}

int main() {
	string s;
	while (cin >> n) {
		if (n == 0) break;
		cin >> m >> a >> d;

		vector<PAIR> v[30];
		for (int i = 0; i < 30; i++) {
			fill(lot[i], lot[i] + 10, -1);
		}

		for (int i = 0; i < d; i++) {
			cin >> s;
			for (int j = 0; j < n - 1; j++) {
				if (s[j] == '1') {
					lot[i][j] = j + 1;
					lot[i][j + 1] = j;
				}

				if (s[j] == '1') continue;

				if ((j - 1 < 0 || s[j - 1] == '0') && (j + 1 >= n - 1 || s[j + 1] == '0'))
					v[i].push_back(make_pair(j, j + 1));
			}
		}

		m--; a--;
		if (solve(m) == a) {
			cout << 0 << endl;
			continue;
		}

		bool judge = false;
		for (int i = 0; i < d; i++) {
			if (v[i].empty()) continue;
			for (int j = 0; j < v[i].size(); j++) {
				lot[i][v[i][j].first] = v[i][j].second;
				lot[i][v[i][j].second] = v[i][j].first;

				if (solve(m) == a) {
					cout << i + 1 << " " << v[i][j].second << endl;
					judge = true;
					break;
				}

				lot[i][v[i][j].first] = -1;
				lot[i][v[i][j].second] = -1;
			}
			if (judge) break;
		} 
	
		if (!judge) cout << 1 << endl;
	}
	return 0;
}

AOJ 0065 Trading

取引 | Aizu Online Judge


無駄に長いと思う

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int a, b;
void split(string s) {
	int tmp = 0, n = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != ',') {
			tmp *= 10;
			tmp += s[i] - '0';
		} else {
			a = tmp;
			tmp = 0;
		}
		b = tmp;
	}
}

bool find(vector<int> v, int n) {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == n) return true;
	}
	return false;
}

int main() {
	string s;
	map<int, int> m1;
	map<int, int> m2;
	vector<int> v;
	while (getline(cin, s)) {
		if (s.size() == 0) break;
		split(s);
		m1[a]++;

		if (find(v, a)) continue;
		v.push_back(a);
	}

	while (getline(cin, s)) {
		split(s);
		m2[a]++;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		if (m2[v[i]] == 0) continue;
		cout << v[i] << " " << m1[v[i]] + m2[v[i]] << endl;
	}
	return 0;
}

AOJ 0064 Secret Number

暗証番号 | Aizu Online Judge

#include <iostream>
#include <string>
using namespace std;

int findNumber(string s) {
	int tmp = 0, res = 0;
	for (int i = 0; i < s.size(); i++) {
		if (0 <= s[i] - '0' && s[i] - '0' < 10) {
			tmp *= 10;
			tmp += s[i] - '0';
		} else {
			res += tmp;
			tmp = 0;
		}
	}
	return res + tmp;
}

int main() {
	string s;
	int sum = 0;
	while (cin >> s) {
		sum += findNumber(s);
	}
	cout << sum << endl;
	return 0;
}