zukaAPG4bを終えたので次はABSです。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回はABC085C - Otoshidamaです。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
int N = 0;
int Y = 0;
int a, b, c = 0;
// 2重for文を抜け出すためのフラグ
bool flag = false;
cin >> N >> Y;
int remain = 0;
rep(i, N+1){
rep(j, N+1-i){
remain = Y - 10000*i - 5000*j;
if (remain/1000==N-i-j){
flag = true;
a = i;
b = j;
c = N-i-j;
break;
}
if (flag == true) break;
}
}
if (flag==true) cout << a << " " << b << " " << c << endl;
else cout << -1 << " " << -1 << " " << -1 << endl;
}ポイント
今回おさえるべき内容
計算量を削減するための工夫をしてみる
ついにC問題です。愚直に3重for文を回そうとすると，Nが最大2000であるために2000^3が10^8よりも大きくなってしまうために無理そうです。そこで，3重forではなく，10000円札と5000円札の枚数の2重for文にして，1000円札は合計枚数であるNから計算することで計算量を抑える作戦にしてみました。2重for文を抜け出すためには，flagを用意しておく必要があります。
コメント