読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 191/192/193

yukicoder

yukicoder open 2015 small前半
一応この3問はできました。
ICPCを意識してマクロ縛りをしています。

- 191 供託金

  • 問題概要

得票数が全票数のうち1/10に満たない候補者数*30を出力せよという問題です。
ざっくりです。

  • 解説

for文で計算するだけなのですが全票数を10で割ってしまうと整数的な意味で怖いので得票数のほうを10倍して計算した方がいいかもです。

#include<iostream>
using namespace std;

int data[100] = { 0 };
int zenbu = 0;
int res = 0;
int main(void){
    int N;
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> data[i];
        zenbu += data[i];
    }
    for (int i = 0; i < N; i++){
        if (data[i] * 10 <= zenbu)
            res++;
    }
    cout << res * 30 << endl;
    return(0);
}

- 192 合成数

  • 問題概要

Nが与えられ,[N-100,N+100]の範囲内の合成数を一つ出力する問題です。

  • 解説

Nが101以上なのでN,N+1のどちらかが必ず偶数になり2を約数にもつ合成数です。
これだけです。

ソースコードの短さも狙いにいきました。
なぜか+3になってます。

#include<iostream>
using namespace std;
int main(void){
    int N;cin >> N;
    cout << N + 3 + ((N + 3) & 1);
    return(0);
}

- 193 筒の数式

  • 問題概要

問題文をざっくりと解釈すると,文字列Sを与えられたとき、
[i,|S|]の部分文字列と[0,i-1]の部分文字列を連結した文字列が数式になったときの解をTとする。
iが0のときはSと同じです。
考え得るTの最大値を求めよ。って感じです。
演算子二項演算子+-だけで単項演算子+-は数式として認められません。
リーディングゼロがあることにも注意。

  • 解説
S <=10なので全てのiについて求めても間に合いそうです。

まずは分割、連結してできた文字列が数式かどうか判断します。
最初と最後に演算子がきてはいけないのでそこだけ判断すれば多分大丈夫です。
次は数式の計算です。
数式が ABC-D+EF という形を考えます。
(ABC) (-D) (+EF)という形に分解できると思います。
最初の(ABC)を(+ABC)に変換してあとは各部分文字列をstollで64bit整数に変換して合計すれば数式の答えが現れます。
ちなみにコーナーケースとして,
0-9 (解が負の数なので暫定最大値の初期値に注意が必要)
9999999999 (32bit整数に入りきらない)
があるので注意しましょう。


ソースコード

#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long Int;
#define num(x) ('0'<=x&&x<='9')
int main(void){
    string S;
    cin >> S;
    int n = S.size();
    Int res = -9999999999;
    
    for (int i = 0; i < n; i++){
        if (!num(S[i]))continue;
        if (!num(S[(i+n-1)%n]))continue;

        Int sum = 0;
        string now="";
        for (int j = n-1; j >= 0; j--){
            switch (S[(i + j) % n]){
            case '+':sum += stoll(now); now = ""; break;
            case '-':sum -= stoll(now); now = ""; break;
            default:now = S[(i + j) % n] + now; break;
            }
            
        }
        sum += stoll(now);
        res = max(res, sum);
        
    }
    cout << res << endl;
    return(0);
}