yukicoder contest 176 - u_sho競プロぶろぐ

　久々にyukicoderに参加したよ。yukicoderの前に晩ごはん食べに中華料理屋さんのとこ行ったよ。食べ終わって帰ってきたらポケットの中にスマホがなかったよ。中華屋さんに置き忘れたと思ったよ。取りに戻ったよ。なかったよ。道を探したよ。なかったよ。暗いから夜が明けてから探すことにしたよ。yukicoderがはじまってから20分が経っていたよ。

A問題 No.586 ダブルブッキング

　Yukiホテルの予約システムがぶっ壊れてて、同じ部屋に何組も予約が入ってしまったから、Yukiホテルが2組目以降のお客さんに別のホテルの新しい部屋を用意してあげることに・・・　Yukiホテルの宿泊料がP1、振替先のホテルの宿泊料がP2のとき、Yukiホテルは全部でいくらの損失？　ってな問題。

#include <iostream>
#include <set>
using namespace std;
int main(void){
    int P1, P2, N, R;
    set<int> reserves;
    cin >> P1 >> P2 >> N;
    int oneLoss = P1 + P2;
    int ans = 0;
    for(int i=0; i<N; i++){
        cin >> R;
        auto c = reserves.insert(R);
        if(!c.second) ans+=oneLoss;
    }
    cout << ans << endl;
    return 0;
}

　今回のコードでは、setですね。リスト(配列)の一種ですたぶん。setヘッダをincludeしてあげて、set<型名> 変数名; って感じで宣言します。要素を二分木(バイナリツリー)で持ってるので、要素の探索がO(log2_n)で速いです。
　今回は、このsetの特徴である「同じ要素を持たない」ってことを使いました。変数名.insert(値)で値を挿入できるんですが、このときに返り値として、pair 型を返します。pairは、値を2つ持った構造体みたいなもんです。んで、setにその値がまだ入っていなければ、その値をinsert(挿入)して、pair<その値のiterator(ポインタみたいなもん), true(成功)> を返します。setにもう値が入っているときは、pair<その値のiterator, false(失敗)> を返します。
　では、なぜ pair c = reserves.insert(R); とせずに auto c = reserve.insert(R); としているかというと、単順にpairは書くのがめんどくさかったからです。auto型はC++の強いやつで、コンパイラが具体的な型名を勝手に推論してコンパイルしてくれます。動的な型ではないので注意が必要(auto i=0 はint型なので1e18とかはオーバーフロー / auto i=0LL とすると大丈夫)ですが、結構どんな型でも推論してくれます。えらい。
　pair型は変数名.first で1個目(左側)の値を、変数名.second で2個目(右側)の値を取得できます。これでコードの説明は終わりですね。あ、!c.second は c.second の否定です。

B問題 No.587 七対子

　なんか説明疲れた。(だいたいスマホのせい←)

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    char S[14];
    for(int i=0; i<13; i++) cin >> S[i];
    S[13]='\n';
    sort(S, S+13);
    bool odd=0;
    char ans='\n';
    for(int i=0; i<13; i++){
        if(!odd){
            if(S[i]==S[i+1] && S[i]!=S[i+2]){
                i++;
            }else if(S[i]==S[i+1]){
                ans = 'I';
                break;
            }else{
                ans = S[i];
                odd = 1;
            }
        }else{
            if(S[i]==S[i+1] && S[i]!=S[i+2]){
                i++;
            }else{
                ans = 'I';
                break;
            }
        }
    }

    if(ans=='I' || ans=='\0' || ans=='\n')cout<<"Impossible\n";
    else cout<<ans<<endl;

    return 0;
}

　もっといい書き方があるとは思います。かなり冗長なコード。苦悩のあとが見て取れる。とりあえずソートして2個(S[even],S[odd])ずつ見ていって3個のやつ出てきたらbreakして "Impossible\n" を出力。1個のやつ出てきたらansにもって、また2個(S[odd], S[even])ずつ見ていって1個か3個のやつが出てきたらbreakして "Impossible\n" 出力。ansになんかの値が入ってるとansを出力。そんなかんじ。

C問題 No.588 空白と回文

　この問題のポイントは実際に空白に置き換えなくてもいいってことと、与えられる文字列には空白が含まれないってこと。全部の部分文字列について、真ん中から対称に比較してって同じか違うかだけ見ればいいじゃん。

#include <iostream>
#include <string>
using namespace std;
int main(){
    string S;
    getline(cin, S);
    int ans=0, cnt;
    if(S.length()==1){
        ans=1;
    }else{
        for(int i=1; i<S.length(); i++){
            cnt=0;
            for(int j=0; i+j<S.length() && i-j-1>=0; j++){
                if(S[i-j-1]==S[i+j]){
                    cnt+=2;
                }
            }
            ans = max(ans, cnt);

            cnt=1;
            for(int j=1; i+j<S.length() && i-j>=0; j++){
                if(S[i-j]==S[i+j]){
                    cnt+=2;
                }
            }
            ans = max(ans, cnt);
        }
    }
    cout<<ans<<endl;
    return 0;
}

　文字列の最初っから見ていって、どこを中心にしたら一番長くなるかな～って全部試してます。いじょう。

　スマホみつかるといいなあ。