Atcoder Beginner Contest 103に参加したー
こんにちは、kisseです。
昨日のAtcoder Beginner Contest 103に参加したので、参加記録を書きました。
使用言語はC++14です。
A Task Scheduling Problem
実装方針
サンプルみる限り、3つの数字を昇順に並べた上で、1個目と2個目の差と2個目と3個目の差を足し合わせれば良さそうだったので、そのように実装しました。
他の人のブログ見て気づいたんですが、3つの数字の最小値と最大値の差が答えでしたね。笑
ちょうどpriority_queueを知ったので使いたくて使ってみました。
提出コード
#include <iostream>
#include <queue>
using namespace std;
int main(void) {
int ans = 0;
int tmp;
priority_queue<int, vector<int>, greater<int>> que;
for (int i = 0; i < 3; i++) {
cin >> tmp;
que.push(tmp);
}
int first = que.top();
que.pop();
int second = que.top();
que.pop();
ans += second - first;
int third = que.top();
ans += third - second;
cout << ans << endl;
}
B String Rotation
実装方針
貪欲法で実装しました。
計算量がO(n^3)なので巨大な入力が来ると無理ですがAtcoderのB問題なら多分大丈夫、っていう実装です。
比較開始地点をずらしながら、1周回す間全て文字が一致したら”Yes”を出力します。
提出コード
#include <iostream>
#include <string>
using namespace std;
void solve() {
// 貪欲法
string s, t;
cin >> s;
cin >> t;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < t.size(); j++) {
for (int k = 0; k < s.size(); k++) {
if (s[(i + k) % s.size()] == t[(j + k) % s.size()]) {
if (k == s.size() - 1) {
cout << "Yes" << endl;
return;
}
} else {
break;
}
}
}
}
cout << "No" << endl;
}
int main(void) {
solve();
}
C Modulo Summation
実装方針
与えられた数の最小公倍数-1が関数fの最大値をとる点になります。
ここで、最大公倍数を求める必要は無く、すべての数から-1した数を足し合わせればACです。
提出コード
#include <iostream>
using namespace std;
const int MAX_N = 3000;
void solve() {
int N;
int a[MAX_N];
int ans = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
ans += a[i] - 1;
}
cout << ans << endl;
}
int main(void) {
solve();
}
D Islands War
今回AC出来なかった問題です。
他の方の提出やブログを見て理解しました。
方針
要望の範囲の終端の数字が小さいものから順に並び変えをします。
要望を1個ずつ見ながら、最後に落とした橋が要望の範囲の外側である場合その要望の終端の橋を落とす、といった処理を繰り返すことで全ての要望を達成することができます。
実装
#include <iostream>
using namespace std;
const int MAX_N = 100000;
void solve() {
int N, M;
int a[MAX_N], b[MAX_N];
pair<int, int> orders[MAX_N];
bool cut[MAX_N];
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
cin >> a[i];
cin >> b[i];
orders[i].first = b[i];
orders[i].second = a[i];
}
sort(orders, orders + M);
int ans = 0, d = 0;
for (int i = 0; i < M; i++) {
if (d <= orders[i].second) {
d = orders[i].first;
ans++;
}
}
cout << ans << endl;
}
int main(void) {
solve();
}
おわり
ちゃんとAtcoder参加記録を書いたのは初めてですね。
ちゃんと問題解けるようになるように、練習を続けて行こうかなと思ってます。
最後まで読んでいただきありがとうございます!
