Codeforces Beta Round #77 (Div.2 Only)

Virtual Participationでは2問, そのあと全部解き直しました.

Cの問題文意味不明すぎて, DかEかを選ぶときにEを選んだのが失敗でした. (Dの方が簡単だったので...)

DとEはとっても面白かったです. ちゃんと問題を取捨選択して取り組めるようにする力付けていきたいです.

A. Football

問題概要 : {0, 1}からなる文字列Sが渡される.7連続で0か1が立っている箇所があればYESを, なければNOを出力せよ.

解法 : やるだけ. 累積和を持てばO(N), 愚直探索でもO(N)で定数倍の7がつく. (N ≦ 100なのでどちらでも良い)

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long lint;

int main()
{
	char s[128];
	int len;
	
	scanf("%s", s);
	
	len = strlen(s);
	
	for (int i = 0; i <= len - 7; i++){
		bool ng = true;
		for (int j = 1; j < 7; j++){
			if (s[i] != s[i + j]) ng = false;
		}
		if (ng){
			printf("YES\n");
			return (0);
		}
	}
	
	printf("NO\n");
	
	return (0);
}

B. Lucky Numbers(easy)

問題概要 : "すごくラッキーな数"を, 4と7からだけ構成され, かつそれらが登場する桁の数が等しい数のことと定義する.
このとき, 入力された数より大きい"すごくラッキーな数"を答えよ.

解法 : Nが奇数桁のときは, 44..477..7が答えになる.
また, 偶数桁の時は, next_permutationでシミュレーションなどで探索すれば, すぐに答えが求まる. (上の桁から貪欲的に決めていっても良い.)
計算量は O(NC[N/2])くらいとなる.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long lint;

lint make(vector<lint> a)
{
	lint ret = 0;
	
	for (int i = 0; i < a.size(); i++) ret = ret * 10 + a[i];
	
	return (ret);
}

int main()
{
	char s[128];
	lint diff;
	int len;
	vector<lint> l;
	
	scanf("%s", s);
	len = (strlen(s) + 1) / 2;
	
	for (int i = 0; i < len; i++){
		l.push_back(4);
	}
	for (int i = 0; i < len; i++){
		l.push_back(7);
	}
	
	diff = atoll(s);
	
	do {
		lint check = make(l);
		if (check >= diff){
			printf("%lld\n", check);
			return (0);
		}
	} while (next_permutation(l.begin(), l.end()));
	
	for (int i = 0; i <= len; i++){
		printf("4");
	}
	for (int i = 0; i <= len; i++){
		printf("7");
	}
	printf("\n");
	
	return (0);
}

C. Hockey

問題概要 : 文字列wと, 禁止文字列siが与えられる. w上で禁止文字列が表される位置を, その文字以外のなにかに置き換えたい(この際に, 大文字/小文字の状態は保っておく). このとき, できるだけ文字letterが登場するようにしたい. また, そのような文字列が複数ある場合は, 辞書順最小の物が求めたい.
このとき, 置換後の文字列w'を出力せよ.
(今まで見てきた問題文の中で最も意味不明でした.)

解法 : 概要で説明されている処理を実際に行い, wi != letterのときはwiをletterで置き換え, wi == letterのときは, letterがaかどうかを注意して置き換える.

計算量は O(N)となる.

コード:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

typedef long long lint;

bool compare(char *s, char *t, int len)
{
	for (int i = 0; i < len; i++){
		if (tolower(s[i]) != tolower(t[i])) return (false);
	}
	return (true);
}

int main()
{
	int n;
	char str[128][128];
	char w[128];
	char fav[4];
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) scanf("%s", str[i]);
	scanf("%s", w);
	scanf("%s", fav);
	
	int lw = strlen(w);
	bool pos[128];
	
	memset(pos, false, sizeof(pos));
	
	for (int i = 0; i < n; i++){
		int li = strlen(str[i]);
		for (int j = 0; j <= lw - li; j++){
			if (compare(str[i], &w[j], li) == true){
				for (int k = j; k < j + li; k++){
					pos[k] = true;
				}
			}
		}
	}
	
	for (int i = 0; i < lw; i++){
		if (pos[i] && tolower(w[i]) != tolower(fav[0])){
			if (isupper(w[i])) w[i] = toupper(fav[0]);
			else w[i] = tolower(fav[0]);
		}
		else if (pos[i]){
			if (tolower(fav[0]) != 'a'){
				if (isupper(w[i])) w[i] = 'A';
				else w[i] = 'a';
			}
			else {
				if (isupper(w[i])) w[i] = 'B';
				else w[i] = 'b';
			}
		}
	}
	
	printf("%s\n", w);
	
	return (0);
}

D. VolleyBall

問題概要 : グラフが与えられる. このとき, 頂点iからは距離viだけ進むことができ, コストciがかかる. 辺の途中で止まることは許されない.
このとき, sからtまで行くのにかかる最小のコストを求めよ.

解法 : 全点対の最小コストを求めて, 最小コストを辺としダイクストラを行う.
全点対最小距離をO(N^3)で求めると, N ≦ 1000なのでTLEするので, こちらにもダイクストラを用いることで, O(N^2logN)でこの問題を解くことが出来る.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long lint;

typedef pair<lint, int> P;

struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
	Edge(){}
};

vector<Edge> G[1024];
vector<Edge> S[1024];

int main()
{
	int n, m;
	int s, t;
	
	scanf("%d %d", &n, &m);
	scanf("%d %d", &s, &t);
	
	for (int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		G[a].push_back(Edge(b, c));
		G[b].push_back(Edge(a, c));
	}
	
	for (int i = 1; i <= n; i++){
		int lim, cst;
		scanf("%d %d", &lim, &cst);
		
		priority_queue<P, vector<P>, greater<P> > pq;
		bool done[1024];
		memset(done, 0, sizeof(done));
		
		for (pq.push(P(0, i)); !pq.empty(); pq.pop()){
			P now = pq.top();
			
			if (done[now.second]) continue;
			done[now.second] = true;
			if (i != now.second) S[i].push_back(Edge(now.second, cst));
			
			int idx = now.second;
			for (int j = 0; j < G[idx].size(); j++){
				if (now.first + G[idx][j].cost <= lim) pq.push(P(now.first + G[idx][j].cost, G[idx][j].to));
			}
		}
	}
	
	priority_queue<P, vector<P>, greater<P> > pq;
	bool done[1024];
	memset(done, 0, sizeof(done));
	
	for (pq.push(P(0, s)); !pq.empty(); pq.pop()){
		P now = pq.top();
		
		if (now.second == t){
			printf("%lld\n", now.first);
			return (0);
		}
		
		if (done[now.second]) continue;
		done[now.second] = true;
		
		int idx = now.second;
		for (int i = 0; i < S[idx].size(); i++){
			if (!done[S[idx][i].to]) pq.push(P(now.first + S[idx][i].cost, S[idx][i].to));
		}
	}
	
	printf("-1\n");
	
	return (0);
}

E. Horse Races

問題概要 : "ラッキーっぽい数"とは, 数Aのi番目の桁をai, S = {4, 7}としたときに, j - i ≦ k かつai, aj ∈ S (i < j)を満たす数Aのことである.
このとき, 区間[l, r]にある"ラッキーっぽい数"の数を求めよ.

解法 : l, r ≦ 10^1000なので、全探索することは不可能である.

そこで, f(i, j, k, l) := 今i桁目を見ていて, 最後に4か7が出た位置がjで, すでにj - i ≦ kとなるようなi, jの組みがあり, 自由に探索ができるか(l : true or false) という状態を持つdpをすると, O(N^2)でdpが出来る.

しかし, テストケース数が最大で1000個あるため, 各テストケースでdp配列を使いまわすことで, O(TN)でこの問題を解くことが出来る.

使いまわす際に, "数の上限"が邪魔になるので, l = 0のところだけを記録するように工夫する.
上限となるところの探索は, O(N)で前計算しておけば良い.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long lint;

#define MOD (1000000007)

int t, k;
lint memo[1024][1024][2];
pair<int, int> check[1024];
int len;
char s[1024];

lint countNum(int pos, int last, bool done, bool free)
{
	if (free && memo[pos][last][done] >= 0) return (memo[pos][last][done]);
	
	if (pos == 0){
		return (done);
	}

	
	lint ret = 0;
	for (int i = 0; i < (free ? 10 : s[len - pos] - '0'); i++){
		if (i == 4 || i == 7){
			ret = (ret + countNum(pos - 1, pos, done | (last != 1002 && (last - pos <= k)), 1));
		}
		else {
			ret = (ret + countNum(pos - 1, last, done, 1)) % MOD;
		}
	}
	return (free ? (memo[pos][last][done] = ret) : (ret));
}

void lucky(char *s)
{
	int now = 1002, prev = 1002;
	
	for (int i = 0; i <= 1000; i++){
		check[i].first = 1002;
		check[i].second = 0;
	}
	
	for (int i = 0; s[i]; i++){
		if (s[i] == '4' || s[i] == '7'){
			prev = now;
			now = i;
		}
		check[i].first = i != now ? now : prev;
		check[i].second = (i ? check[i - 1].second : 0) | (prev != 1002 && now - prev <= k);
	}
}

int main()
{
	scanf("%d %d", &t, &k);
	
	memset(memo, -1, sizeof(memo));
	while (t--){
		scanf("%s", s);
		len = strlen(s);
		lucky(s);
		
		lint st = 0;
		for (int i = 0; s[i]; i++){
			st = (st + countNum(len - i, check[i].first != 1002 ? len - check[i].first : 1002, i ? check[i - 1].second : 0, 0)) % MOD;
		}
		scanf("%s", s);
		len = strlen(s);
		lucky(s);
		
		lint en = 0;
		for (int i = 0; s[i]; i++){
			en = (en + countNum(len - i, check[i].first != 1002 ? len - check[i].first : 1002, i ? check[i - 1].second : 0, 0)) % MOD;
		}
		en = (en + check[len - 1].second) % MOD;
		
		printf("%lld\n", (en - st + MOD) % MOD);
	}
	
	return (0);
}

感想 :
やっぱり全完するとうれしいし, 1回位本番で全完したいですネ.