【競プロ精進日記】ABS編＜９＞Beginaid

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

AtCoder Beginners Selection

AtCoder Beginners Selectionの問題を1から解いていくシリーズです。使用言語はc++とpythonです。今回はABC085C – Otoshidamaです。

c++

#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を用意しておく必要があります。

python

N, Y = map(int, input().split())
flag = False

for i in range(N+1):
  for j in range(N+1-i):
    remain = Y - 10000*i - 5000*j
    if remain/1000 == N-i-j:
      flag = True
      break
  if flag==True:
    break

if flag==True:
  print("{} {} {}".format(i, j, N-i-j))
else:
  print("{} {} {}".format(-1, -1, -1))

pythonも方針は同様です。