ABC-063 C Bugged を解いてみた

今日もC問題を解いてみました。

区間内の最大値を組合せ計算の最大値を出力せよと言うもの

では問題を見ていきましょう 以下問題

Bugged

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

あなたはコンピュータで試験を受けています。試験は N 問の問題からなり、i 問目の問題の配点は si です。それぞれの問題に対するあなたの解答は「正解」または「不正解」のいずれかとして判定され、正解した問題の配点の合計があなたの成績となります。あなたが解答を終えると、解答がその場で採点されて成績が表示される…はずでした。

ところが、試験システムに欠陥があり、成績が 10 の倍数の場合は、画面上で成績が 0と表示されてしまいます。それ以外の場合は、画面に正しい成績が表示されます。この状況で、成績として画面に表示されうる最大の値はいくつでしょうか？

自分の考えたこと

愚直に計算して最大値をだすとそれぞれの問題の成績から正解した問題と不正解の問題の点数のシミュレーションを行い、最大値を算出すると言う方法がありますが、計算のオーダは2の累乗になってしまいN=100で計算をしても2100なので現実的でない。。

そこで、計算オーダを抑えるために考えた結果、最初に全て正解した際の計算を行いそこから10の倍数にならない成績の最小の点数を引けば最大値が求められます。

プログラムのフロー

  • 入力を受け取りながら、最大値の計算を行う
  • 成績に一つずつアクセスする
    • もし最大値が10の倍数ならばループを抜ける
    • 成績の配列に 最大値 - 成績 の値を格納する
  • 最大値が 10の倍数の場合
    • 最大値を0とする
    • 最大値 - 成績 に 1つずつアクセスする
      • 最大値よりも最大値 - 成績 が大きい かつ 最大値 - 成績 が10の倍数でない場合 に 最大値 - 成績 で最大値を更新する
  • 最大値が10の倍数の場合 最大値を0とする
  • 最大値を出力する

とまあこんな感じに考えました。終わって考えてみると、10の倍数のあとreturn 0;しておけばそのあとの分岐いらないはずだったんですが。。まあAC取れたのでよしとしましょう.

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(void){
    int N,max;
    cin >> N;
    vector<int> score(N);
    max = 0;
    for(int i = 0;i < N;i++){
        cin >> score[i];
        max += score[i];
    }
    for(int i = 0;i < N;i++){
        if(max % 10 != 0)
            break;
        score[i] = max - score[i];
    }

    if(max % 10 == 0){
        max = 0;
        for (int i = 0;i < N;i++){
            max = score[i] > max && score[i] % 10 != 0 ? score[i] : max;
        }
    }
    max = max % 10 == 0 ? 0 : max;
    cout << max << endl;
}

これでACとりました。