Atcoder Beginner Contest 141を振り返る
ABC141で4完したので備忘録として復習＆軽い解説を書いてみた。不備や誤りなどありましたらコメント欄などで指摘頂ければ幸いでございます。
A-Weather Prediction
簡単なif-else文を3回書けばいいだけ。凝った書き方をしたい人はmodとか使えばいいそう。
# include <string>
# include <iostream>
using namespace std;
int main(void) {
string s; cin >> s; // 入力
if (s == "Sunny") { // 晴れなら次の日は曇り
cout << "Cloudy" << endl;
}
else if (s == "Cloudy") // 雲りなら次の日は雨
{
cout << "Rainy" << endl;
}
else if (s == "Rainy") { // 雨なら次の日は晴れに戻る
cout << "Sunny" << endl;
}
return 0;
}
B-Tap Dance
入力はL, R, U, Dのいずれかしかとらない。U, Dは奇数、偶数ステップで共通。ということは偶数ステップの時にLを踏むと「踏みにくい」、もしくは奇数ステップの時にRを踏むと「踏みにくい」となるので、踏みにくいステップを踏んだ瞬間にfalseとなるフラグを管理すればよいだろう。実装は以下の通り。
# include <string>
# include <iostream>
using namespace std;
int main(void) {
string s; cin >> s; // 入力
bool flag = true; // 「踏みやすい」かどうか判定するフラグ,
// 文字列sの要素数だけループ回す(10文字だと10回回る)
// 踏みにくいステップ(文字列)を受け取った場合、即座にフラグがfalseになる
for (int i = 0; i < s.size(); i++) {
if (i % 2 == 0) { // 偶数ステップ(i=0,2,4,6...)
if (s[i] == 'L') {
flag = false; // 踏みにくい！
break;
}
}
else { // 奇数ステップ(i=1,3,5,7...)
if (s[i] == 'R') {
flag = false; // 踏みにくい！
break;
}
}
}
// 踏みやすい(flag == true)なら"Yes"、そうでなければ"No"
cout << (flag ? "Yes" : "No") << endl;
return 0;
}
C-Attack Survival
C問題レベルになると途端に制約条件がきつくなるみたいなのでよく確認しておかないといけない。筆者も二重ループ回して制約時間超過してからウンウン考えたので、手を動かす前に頭を使いましょう(自戒)
誤：
１．全員に初期ポイントK付与する
２．正答した人以外から－１ポイントしていく
３．TLE
正：
Q回正解が出た中で、Q回とも全て正解できなかった場合、元々与えられたKポイントからQ×(-1)ポイント引かれることになる。つまりK-Qを参加者全員で共通のスタートラインとして、そこから正解した人だけに問題数だけ+1ポイント与えてやり、最終得点が0点より高くなった回答者だけ生き残る(=脱落しない)という判定にしてやれば良い。実装は以下の通り。
# include <vector>
# include <iostream>
using namespace std;
int main(void) {
// n: 参加者の人数, k: 最初に全員に付与された得点, q: 正解が出た回数
long long n, k, q; cin >> n >> k >> q;
// X: 全参加者の得点配列, A: 出題順に正解した人を並べた配列
vector<int> X(n), A(q);
// 1-オリジンから0-オリジンに変換
// (配列では1番目の人は0インデックスに格納される為)
for (int i = 0; i < q; i++) {
cin >> A[i]; // 入力
A[i]--; // 0-オリジンに変換
X[A[i]]++; // 正解者に+1ポイント付与する
}
// 初期ポイントK-Qから正解して得たポイントX[i]を足して
// 0点以下であれば脱落("No")
for (int i = 0; i < n; i++) {
if (k - q + X[i] > 0) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}
D-Powerful Discount Tickets
全商品の価格中の最も高価な商品に対して毎回割引券(÷2なのでつまり半額クーポン券)を使用していけば最小でいくら払えばいいか導き出せる。しかし半額クーポンを使うごとに最大価格が入れ替わる為、クーポン券を使うごとに最大価格を探索し直さなければならない。もちろん毎回ソートしていては間に合わないので、最大ヒープ木というデータ構造を使用する。最大ヒープ木では木の根が常に最大値を保有するように工夫されており、最大値を取り出すと、その次に最大値となる値を木の根に移動させて根が常に最大値をキープする仕組みになっている。今回の問題ではこれが役に立ちそうだ。C++ではSTLコンテナであるpriority_queue(#include <queue>が必要)で最大ヒープ木を実装出来る。0から最大ヒープを作るのは骨が折れるのでこれを利用してみる。
例）
10円、16円、28円の商品があり、割引券が2枚あった場合...
まず最大値の28円に対して半額クーポンを適用して28 ÷ 2 = 14円にする。
最大値が16円の商品になったので、これにクーポンを適用すると16 ÷ 2 = 8円になる。
割引券をすべて使いきったので金額を合計すると
10 + 8 + 14 = 32円が最小で支払う価格になる。これを最大ヒープ木を利用して実装してみよう。
# include <vector>
# include <algorithm>
# include <iostream>
# include <queue>
using namespace std;
// 入力aを受け取って2で割る(小数点以下切り捨て)だけの関数
template<class T> inline void coupon(T & a) {
a /= 2;
}
int main(void) {
int n, m; cin >> n >> m; // n: 商品個数, m: 割引券枚数
long long a; // 商品の価格
priority_queue<long long> que; // 最大ヒープ木(常に木の根が最大値になる)
// 商品価格を順にヒープ木にプッシュしていく
// プッシュする毎に木が変形し、根には常に最大価格がキープされるようになっている
for (int i = 0; i < n; i++) {
scanf("%lld", &a);
que.push(a);
}
int root; // 最大ヒープ木の根を格納
// 割引券の枚数分だけ最大価格を割り引きしていく
for (int i = 0; i < m; i++) {
root = que.top(); // ヒープ木の根を取得(この時点では根の値はまだ保有されている)
coupon(root); // 割引券適用(単純に2で割ってるだけ)
que.pop(); // 根をポップする(木の根から最大値を取り出して無くした)
que.push(root); // 割り引いた価格を再びヒープ木に格納する(最大値が根にあるように木が変形される)
}
// ヒープ木に格納されている全商品の価格を合計する
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += que.top();
que.pop();
}
cout << sum << endl;
}
E-Who Says a Pun?
現在誠意執筆中
F-Xor Sum 3
現在誠意執筆中
間違いや不備、質問などありましたらコメント欄などから知らせて頂ければ幸いです。