KUPC2016 A~D問題

kupc2016.contest.atcoder.jp

A問題

問題概要

A時間目からB時間めの始まる直前まで授業は中止される。
N個の履修中の授業のうちいくつの授業をうけることができるか。

解法

各授業の時間に対して  [A - B) の範囲内でないものをカウントしていけば良い。

#include <iostream>

int main() {
	int n, a, b;
 
	std::cin >> n >> a >> b;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int num;
		std::cin >> num;
		if (num < a || b <= num) ans++;
	}
 
	std::cout << ans << std::endl;
	return 0;
}

B問題

N個の問題があるので以下の条件を満たす用にKUPCを開催する。
 1回のKUPCではK問の問題を出題する。
 各問題が出題される回数はたかだか1回である。
 1回のKUPCに出題するK問の問題の頭文字をすべて異なるように出題する。
最大で何回KUPCを開催することができるか

解法

制約に  P_i \ne P_j とは限らないと書いてあるのでsetを使い問題の重複をなくす。
また、頭文字にしか興味が無いので頭文字の出現回数のみをカウントする。
カウント数を降順にソートし、上から順番にK個使用していく。
ただし、使っていくたびにソートを行う必要がある。
そうしないと頭文字の出現回数が
A=4, B=4, C=2 で、1回のKUPCの出題問数が2のとき
最初だけソートした場合だと(A,B),(A,B),(A,B),(A,B) となりKUPCの開催回数は4回となる。
しかし、毎回ソートを行うと(A,B), (A,B), (A,B), (C, A), (C, B) の5回となる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
 
int main() {
	int n, k;
 
	std::cin >> n >> k;
 
	std::vector<int> p(26);
	std::set<std::string> se;
        // 問題の重複をなくす
	for (int i = 0; i < n; i++) {
		std::string s;
		std::cin >> s;
		se.insert(s);
	}
        // 頭文字のみを取り出し、カウントする。
	for (auto i : se) {
		p[i[0] - 'A']++;
	}
 
	int ans = 0;
	while(true){
		int count = 0;
		std::sort(p.begin(), p.end());
		std::reverse(p.begin(), p.end());
		for (int j = 0; j < 26; j++) {
			if (p[j] > 0) {
				p[j]--;
				count++;
			}
			if (count == k) {
				ans++;
				break;
			}
		}
		if (count < k) break;
	}
 
	std::cout << ans << std::endl;
 
	return 0;
}

C問題

kupc2016.contest.atcoder.jp

解法

各クッキーに対して美味しさ(x xor y)が127となるようにする。
この時美味しさyのクッキーは次の操作のときに127となるようにしていくだけ。


f:id:Matchald:20161002190419p:plain


#include <iostream>
#include <vector>
#include <algorithm>
 
void solve() {
	int n, d;
 
	std::cin >> n >> d;
 
	long long ans = 0;
	for (int i = 0; i < n - 1; i++) {
		ans += 127;
		d = 127 - d;
	}
 
	std::cout << ans + d << std::endl;
}
 
int main() {
	int test_case;
 
	std::cin >> test_case;
 
	for (int i = 0; i < test_case; i++) {
		solve();
	}
 
	return 0;
}

D問題

kupc2016.contest.atcoder.jp

解法

全探索を行うだけ。
黒板の状態はたかだか4種類である。黒板の長さは最高でも100なので 検索回数の上限以下でおさまる。
しかし、右方向に合っているか確かめたあとに、左方向に対してもクエリを出す必要がある。

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    int n;
 
    std::cin >> n;
 
    std::string upper = "", lower = "";
 
    std::string uq = "..##", lq = ".#.#";
    bool back = false;
    while (true) {
	int before_length = upper.length();
	for (int i = 0; i < 4; i++) {
		std::string result;
 
		if (back) {
                        // ある点から左方向があっているか確かめる。
			std::cout << uq[i] << upper << std::endl;
			std::cout << lq[i] << lower << std::endl;
			std::cin >> result;
			if (result == "end") return 0;
			if (result == "T") {
				upper = uq[i] + upper;
				lower = lq[i] + lower;
				break;
			}
		} else {
                        // ある点から右側があっているか確かめる。
			std::cout << upper << uq[i] << std::endl;
			std::cout << lower << lq[i] << std::endl;
			std::cin >> result;

			if (result == "end") return 0;
			if (result == "T") {
				upper += uq[i];
				lower += lq[i];
				break;
			}
		}
	}
        // 右方向に確かめている間にすべてのパターンでミスした場合は
        // もう右方向に黒板はない。しかし、左方向にはあるかもしれないのでそちらを確かめる。
	if (before_length == upper.length()) {
		back = true;
	}
    }
 
	return 0;
}