読者です 読者をやめる 読者になる 読者になる

年中春休み

年中春休みじゃないです。

競技プログラミング 7 (過去問ABC 040)

abc040.contest.atcoder.jp


更新するのは久しぶりになります(一応ちょこちょこ勉強していました)。


A問題
いつものごとくそのまま回答しました。

#include<iostream>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
 
int main() {
	int n, x;
	cin >> n >> x;
	cout << min(x-1, n - x) << endl;
	return 0;
}


B問題
for文の条件を一回間違えたせいで一度WAになってしまいましたが、これも至って普通に計算しました(=を付け忘れた)。

#include<iostream>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
 
int main() {
	int n;
	cin >> n;
	int ans = n;
	for (int h = 1; h*h <= n; h++) {
		int w = n / h, a = n%h;
		ans = min(ans, w - h + a);
	}
	cout << ans << endl;
	return 0;
}


C問題
プログラミングの問題を解く場合はグラフを書くと良いと聞いたのでグラフを書いてごちゃごちゃやっていたら動的計画法でやることがよさそう、となったのでそうしました。
ただ、解いているときはそれが動的計画法だという自覚はなかったんですが、こういうところどうなんでしょうね。解ければいいのかもしれないけど自分が何をやっているかわからずに解いているようじゃダメですね。

#include<iostream>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
 
int main() {
	int n;
	int a[100000],cost[100000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cost[0] = 0; cost[1] = abs(a[1] - a[0]);
	for (int i = 2; i < n; i++) {
		cost[i] = min((cost[i - 2] + abs(a[i] - a[i - 2])), (cost[i - 1] + abs(a[i] - a[i - 1])));
	}
	cout << cost[n-1] << endl;
	return 0;
}


D問題
部分点の方ならなんとかなるかな?と思ったんですがダメでした。
グラフの問題が凄い苦手なので対策しない限り一生できないと思います。
解説見たら満点解答はちょっと今の自分では書けないかな~…という感じ。


ということで今回も3完でした。そろそろD問題解けるようになりたい、ので大学図書館で蟻本を借りてきましたが、ちゃんと勉強できるんでしょうか…?