AtCoder Regular Contest 076 - u_sho競プロぶろぐ

　みなさんこんにちは。放送大学の文系講義が面白くて自分の大学の講義をさぼり中なu_shoです。

　一昨日あったABC076のやつやるよ。u_shoはABしか解けなくてごみごみのごみだったよ(T^T)
　まずA問題だよ。問題名は「Rating Goal」、今のレートRとなりたいレートGがもらえるから、RをGにするために必要なパフォーマンスPを求めるよ。問題文から、
　(P＋R)/2 ＝ G
　∴　　　　　P ＝ 2G－R
だよ。方程式の解き方が分からない人はこのページ方程式の解き方等式の性質を見てね。
∴は「したがって」みたいな意味だよ。
んじゃコード↓

#include <iostream>
int main(){
    int r, g;
    std::cin >> r >> g;
    std::cout << 2*g-r << '\n';
    return 0;
}

　いままで using namespace std; で書いたことにしていた std:: を直に書いてます。std::endl を書くのがめんどくさいので、直に改行文字 \n を出力するようにしています。コーディングが速く終わりました。ついでに言っとくと、std::endl とするよりも実行時間が速いです。namespace（名前空間）については私がよくわかってないので、自分で調べてください←

　次はB問題、「Addition and Multiplication」。最初の数1に、2をかけたり(do multiplication)、Kをたしたり(add)して、N回の計算でなるべく小さな数にしようね！　って言ってます。2をかけても、Kをたしても、数は絶対に正です(∵Kは正の数(∵は∴の逆の意味。「なぜなら」とか))。なので、2をかけるときもKをたすときも、もとの数が小さい方が小さくなります。
　つまり、一回の計算ごとに、小さくなるほうを選んでいけばOKってことですね。はい。

#include <iostream>
using namespace std;
int main(void){
    int n, k;
    cin >> n >> k;
    int ans=1;
    for(int i=1; i<=n; i++){
        if(ans*2 < ans+k){
            ans *= 2;
        }else{
            ans += k;
        }
    }
    cout << ans << endl;
    return 0;
}

　では、u_shoがゴミになった~~元凶の~~C問題ですね。「Dubious Document 2」(意訳：うさんくさい文章その２)です。?t?o??? みたいな謎の文字列S'にcoderみたな普通の文字列Tが入るかなーってやって、S'を辞書順最小になるように(この場合atcoder)どうにかしてね。
　私奴の嘘解法(コンテスト時間外にAC)はこうですね。

#include <iostream>
#include <string>
using namespace std;
int main(){
    string S, T;
    cin >> S;
    cin >> T;
    bool check=false;
    int ct,cs;

    for(int j=S.length()-T.length(); j>=0; j--){
        for(int i=0; i<T.length(); i++){
            for(int k=0; k<T.length(); k++){
                if(S[j+k-i]!='?' && S[j+k-i]!=T[k]){
                    break;
                }else if(k==T.length()-1){
                    check=true;
                    cs=j;
                    ct=i;
                    goto LABEL;
                }
            }
        }
    }
    LABEL:

    string ans=S;
    if(check){
        for(int i=0; i<T.length(); i++){
            ans[cs+i-ct]=T[i];            //<-私はここで-ctを忘れてWAくらいまくりましたorz
        }
        for(int i=0; i<S.length(); i++){
            if(ans[i]=='?')ans[i]='a';
        }
        cout << ans <<endl;
    }else{
        cout << "UNRESTORABLE\n";
    }
    return 0;
}

　これACしちゃうんですけど(私はまずこれが通せなかったんですが)、S'が?b??で、Tがbaとかだと、ほんとはabaaって出力しなきゃいけないのに、このコードだとabbaって出力しちゃうんですよね。本番はこれに該当するテストケースがなくて大丈夫だった(通せた)みたいですが、、、
　このテストケースを通すには、全探索ですね。上のコードみたいに、入るかなーってやって、入ったやつを全部記憶して、それが辞書順で小さいかどうかを順に比較していけばいいんですよね。大変そうなのでやりません。
　えーっと、goto文っていうのはそこから、goto ?; の ?: って書いてあるところまで一気に処理をとばすヤバイ文ですね。?; を書くところを間違えては絶対にいけません。特にgoto文より上の行に書いてはいけませんし、ループの代わりに使うのもだめです。無限ループのもとです。注意して使いましょう。今回の場合だと、ラベル付きbreak文というのがあるので、そっちを使ってもいいでしょう。

　ではでは。