Atcoder Regular Contest #011

せっかくGoogle Calendarに登録しておいたのに忘れてました．
今日90分で解いてみたら-oo-でした．私から見た難易度はA>B=Cでした．

A

あわあわ(解けない)
あわあわ(解けた)．A問題にしては難易度が高いなーと思った．

#include<iostream>

int n, m;

int recycle(int N, int unused){
	if(N < n){
		if(N + unused < n)return N;//もうできないよー
		return N + recycle((N+unused) / n * m, (N+unused) % n);//何とかしてつくるよー
	}
	
	return N + recycle(N / n * m, unused + N % n);
}

int main(){
	int N;
	std::cin >> n >> m >> N;
	std::cout << recycle(N, 0) << std::endl;
}

B

c++11の火力を使った．*1

#include<iostream>
#include<algorithm>
#include<cstdio>

std::string convert(std::string s){
	std::transform(s.begin(), s.end(), s.begin(), [](char c){
			return tolower(c);
		});
	std::string res = "";
	std::for_each(s.begin(), s.end(), [&res](char c){
			switch(c){
			case 'b':
			case 'c':
				res += "1";
				break;
			case 'd':
			case 'w':
				res += "2";
				break;
			case 't':
			case 'j':
				res += "3";
				break;
			case 'f':
			case 'q':
				res += "4";
				break;
			case 'l':
			case 'v':
				res += "5";
				break;
			case 's':
			case 'x':
				res += "6";
				break;
			case 'p':
			case 'm':
				res += "7";
				break;
			case 'h':
			case 'k':
				res += "8";
				break;
			case 'n':
			case 'g':
				res += "9";
				break;
			case 'z':
			case 'r':
				res += "0";
				break;
			}
		});
	return res;
}

int main(){
	int n;
	std::cin >> n;
	std::string s;
	
	for(int i=0, t=0;i<n;i++){
		std::cin >> s;
		if((s = convert(s)) != ""){
			if(t++)std::cout << " ";
			std::cout << s;
		}
	}
	std::cout << std::endl;
}

C

Dijkstra法と経路復元をするだけ．

#include<iostream>
#include<stack>

const int INF = 1 << 24;
int n, d[1002], used[1002], prev[1002], cost[1002][1002];


void dijkstra(int s){
	for(int i=0;i<1002;i++){
		d[i] = INF;
		used[i] = 0;
		prev[i] = -1;
	}

	d[s] = 0;

	while(true){
		int v = -1;
		for(int i=0;i<n;i++){
			if(!used[i] && (v == -1 || d[i] < d[v])){
					v = i;
			}
		}
		
		if(v == -1)break;

		used[v] = 1;

		for(int i=0;i<n;i++){
			if(d[v] + cost[v][i] < d[i]){
				d[i] = d[v] + cost[v][i];
				prev[i] = v;
			}
		}
	}
}

int main(){
	std::string words[1002];
	std::cin >> words[0] >> words[1];
	
	int res;

	std::cin >> n;
	n += 2;

	for(int i=2;i<n;i++){
		std::cin >> words[i];
	}

	int word_length = words[0].size();

	for(int i=0;i<1002;i++){
		for(int j=0;j<1002;j++){
			cost[i][j] = INF;
		}
	}

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(i == j)continue;
			int diff = 0;
			for(int k=0;k<word_length;k++){
				if(words[i][k] != words[j][k]){
					diff++;
				}
			}
			if(diff == 1){
				cost[i][j] = 1;
				cost[j][i] = 1;
			}
		}
	}

	if(words[0] == words[1])std::cout << "0\n" << words[0] << "\n" << words[1] << "\n";
	else{
		dijkstra(0);
		
		if(d[1] == INF)std::cout << "-1" << std::endl;
		else{
			int v = 1;
			std::stack<std::string> s;
			while(v != -1){
				s.push(words[v]);
				v = prev[v];
			}

			std::cout << d[1] - 1 << std::endl;
			while(!s.empty()){
				std::cout << s.top() << std::endl;
				s.pop();
			}
		}
	}
}

*1:なお，最大火力の1%以下だった模様