情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Beginner Contest 113

AtCoder Beginner Contest 113 (ABC113) の解説です。
AtCoder Beginner Contest 113 旧版
AtCoder Beginner Contest 113 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 113
rated 1200
11/4(日) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - Discount Fare

まず、A駅からB駅までの料金はX円です。
次に、B駅からC駅までの料金は半額なので\frac{Y}{2}円です。
よって、運賃の合計はX+\frac{Y}{2}円です。

#include<iostream>
using namespace std;
int main() {
	int X, Y;
	cin >> X >> Y;
	cout << X + (Y >> 1);
	return 0;
}

B - Palace

ちょっと問題を変形してみます。
まずは、温度を1000倍しても温度の差の絶対値の大小関係は保たれるので、登場する全ての温度を1000倍してみましょう。
これにより標高xmにおける平均気温は1000T-6x度となり、これが1000Aに最も近いものを選ぶ問題になります。
更に全ての温度を1000A度引いても温度の差の絶対値の大小関係は保たれるので、1000(T-A)-6xが最も0に近いものを選ぶ問題に変わりました。
後は各H_iに対し|1000(T-A)-6H_i|を求め、これが最小になるようなiを出力すれば良いことが分かります。
なお、このような操作を行う際は必ずオーバーフローしないか先に考えておきましょう。今回のケースでは大丈夫です。

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int N, T, A, H;
	cin >> N >> T >> A >> H;
	T = 1000 * (T - A); // Tを平行移動することで、計算を楽にする
	int diff = abs(T - 6 * H), ans = 1; // diffは平均気温との差、これが最も小さくなる地点を探すよ
	for (int i = 2;i <= N;++ i) {
		cin >> H;
		if (diff > abs(T - 6 * H)) {
			diff = abs(T - 6 * H);
			ans = i;
		}
	}
	cout << ans;
	return 0;
}

C - ID

まず、問題を整理すると各iについて同じ県の何番目に成立したか分かれば良いことが分かります。
まず、(P_i, Y_i, i)という3個のデータを持つ構造体を考えます。
このデータをPの小さい順にソートすると、同じ県は隣接した順に並ぶことが分かります。
更にPが同値の時はYの小さい順にソートすれば、同じ県の中で何番目かも即座に分かります。
実際にxを求める時は、自分より1個上のデータのPを見て同値ならば1個上のデータのxに1を足したものが、そうでないなら1がxに入ることが分かります。
後は0埋めをして出力を行うと良いです。
これは、フォーマット指定子が指定できる言語なら(例えばC++ならばprintf)、%06dとすれば0埋めした6桁の整数を出力できます。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX = 100000; // Nの最大値
int main() {
	int N, M, P, Y;
	scanf("%d%d", &N, &M);
	static pair<pair<int, int>, int> city[MAX]; // <<P, Y>, i>を記憶しているよ
	static pair<int, int> num[MAX]; // 求めた番号を記録するよ
	for (int i = 0;i < M;++ i) {
		scanf("%d%d", &P, &Y);
		city[i] = make_pair(make_pair(P, Y), i);
	}
	sort(city, city+M); // これでPの小さい順→同値ならYの小さい順にソートされるよ
	for (int i = 0, c = 1;i < M;++ i, c = i < M && city[i - 1].first.first == city[i].first.first ? c + 1 : 1) { // cは同じPにおける何番目かを表してるよ
		num[city[i].second] = make_pair(city[i].first.first, c);
	}
	for (int i = 0;i < M;++ i) printf("%06d%06d\n", num[i].first, num[i].second); // 0埋め
	return 0;
}

D - Number of Amidakuji

まず、あみだくじは上から考えていくことができます。
dp_{i, j}=高さiにおける左からj番目の縦棒に辿り着く組み合わせとします。
ここで、dp_{0, 1}=1, dp_{0, x}=0とします。
この時、あみだくじの性質よりdp_{i, j}はdp_{i-1, j-1}とdp_{i-1, j}とdp_{i-1, j+1}を何倍かしたものになることは自明です。
次に、具体的にどのような倍数が掛かるか考えてみましょう。
まずは、dp_{i, j}とdp_{i-1, j-1}、すなわちj-1番目からj番目に横棒を引いた時を考えます。
この時、あみだくじの制約よりj-2番目からj-1番目、およびj番目からj+1番目には横棒が引かれていません。
残りの横棒に関して考えましょう。
今、f(x)=長さxのあみだくじに引くことのできる横棒の組み合わせとします。f(0)=f(1)=1です。
ここでf(n)は、まずn-1番目からn番目に横棒を引くならn-2番目からn-1番目に横棒を引けないので組み合わせはf(n-2)となり、
n-1番目からn番目に横棒を引かないなら組み合わせはf(n-1)で表せるので、f(n)=f(n-1)+f(n-2)という漸化式が組めます。
この式を用いて、先ほどのDPは次のように定義することができます。
dp_{i, j}=dp_{i-1, j-1} \cdot f(j-2) \cdot f(W-j) + dp_{i-1, j} \cdot f(j-1) \cdot f(W-j) + dp_{i-1, j+1} \cdot f(j-1) \cdot f(W-j-1)
f(x)は{\rm O}(W)で求めることができ、それにより各i, jにおいてdp_{i, j}を{\rm O}(1)で求めることができるので、計算量は{\rm O}(WH)です。
なお、左右1マス分を参照するのでバグを防ぐためにiの範囲は0からHまで、jの範囲は0からW+1まで取り、予め0で埋めておくと良いです。
また、f(-1)=0とするとバグが無くなります。実装の際はfを1個平行移動すると負数が消えて楽だと思います。

#include<iostream>
using namespace std;

const int MAX = 10; // 横
const int MAX2 = 101; // 高さ
const int MOD = 1000000007; // 今回使う余り
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	long long int fib[MAX] = {}, dp[MAX2][MAX] = {}; // 番兵付きなので間違えないように！dp[i][j]は高さiにおける左からj番目に辿れる組み合わせ
	fib[1] = 1;
	for (int i = 2;i <= W + 1;++ i) fib[i] = fib[i - 1] + fib[i - 2]; // ここまででO(W)
	dp[0][1] = 1;
	for (int i = 1;i <= H;++ i) for (int j = 1;j <= W;++ j) dp[i][j] = (dp[i - 1][j - 1] * fib[j - 1] * fib[W - j + 1] + dp[i - 1][j] * fib[j] * fib[W - j + 1] + dp[i - 1][j + 1] * fib[j] * fib[W - j) % MOD;
	cout << dp[H][K];
	return 0;
}

結果

oooo 4完(1000点) 02:07-07:51-19:52-57:19 / 57:19
146位

感想

今回はABCOnlyだったこともあり、割と簡単な問題セットだったのではないでしょうか。
D問題に関しては、あみだくじの各地点に辿り着く組み合わせ数を求めようとすると自然とDPが作れると思うので、ちゃんと問題を読んで遷移が存在しないか考えるようにしましょう。
動的計画法は必ず分割統治法である、すなわち何らかの方法で問題が分割できます。
今回の場合は高さを分割すると、必ず1個上のあみだ部分の遷移から考えられるということが分かると思います。