最近知った言葉

　知らなかったなあ～。となった言葉をただひたすら書いていく備忘録みたいなもん。競プロには全く関係なかったりあったりする。

・陥穽(かんせい)・・・落とし穴。例：落とし穴が完成した

・黄昏泣き(コリック)・・・赤ちゃんが決まって夕方あたりに泣く。原因不明(原因はおなかにガスが溜まって不快感を覚えるのも一因)。
　　最初はパワーワードの方載せようかと思ったけど、割と一般的な言葉っぽいのでやめた。

yukicoder contest 176

　久々に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;
}

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

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

AtCoder Regular Contest 076

　みなさんこんにちは。放送大学の文系講義が面白くて自分の大学の講義をさぼり中な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文というのがあるので、そっちを使ってもいいでしょう。

　ではでは。

AtCoder Regular Contest 075 C - Bugged

　AtCoderのC埋め3問目。ABC063 / ARC075 のC問題「Bugged」(蠅ではない)。
　N個の自然数s[i]がもらえるので、それを全部足したやつが答えなんですが、ここでBugが起きます。なんと答えが10の倍数だと0扱いされてしまうのです。なので、答えが10の倍数にならないためにはどのs[i]を「答えに足さない」かということを考えましょう。

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

int main(void){
    int N, ans = 0;
    cin >> N;
    int s[N];
    for(int i=0; i<N; i++){
        cin >> s[i];
        ans += s[i];
    }

    if(ans%10==0){
        sort(s, s+N);
        for(int i=0; i<N; i++){
            if(s[i]%10){
                ans -= s[i];
                break;
            }
        }
    }

    if(ans%10==0) ans = 0;

    cout << ans << endl;

    return 0;
}

　とりあえずansに全部足して、それが10の倍数だと、s[i]が10の倍数かどうかを小さいやつから順にみていって、10の倍数でなければ、そいつをansから引いてあげればOK。と思ったんですが、sの全部が10の倍数のときはどうやっても0なので、その場合をしっかり考えて、if(ans%10==0) ans = 0; の一文を付け加えてあげるとACです。(こういう問題を一発で通せるようにならなければ・・・)

　という問題でした。ちゃお～。

　と思ったけど、sort(s, s+N); が初出でした。これはalgorithmライブラリをincludeしてあげてから使います。sortはvoid(値を返さない)型の関数で、sort(ポインタA, ポインタB) とやると、ポインタAからポインタBが(確保されていれば)入っている数値の小さい順に並べかえられます(ポインタよくわかんない人は「ポインタ　配列」とかでググってください)。
　そんぐらいの関数は自分で書けよと思ったでしょ。いやまあそうなんだけどね。実はソートには色々あって、それぞれ計算量が違うので、常に適切なソートを書くのは大変なのよ。その点、計算量が多くともO(NlogN) (Nは要素数)に最適化されるsort関数は便利なのね。もっと便利に使えるんだけど、それはまたの機会に。

　今度こそちゃお～。

AtCoder Regular Contest 078 C - Splitting Pile

　AtCoderのC埋め2つ目。
　ARC078 / ABC067 のC問題「Splitting Pile」です。a[1]からa[N]までの数字が書かれた山札(pile)を上側の数の合計と下側の数の合計の差がなるべく小さくなるようにして2つに分割(split)します。この差の絶対値を出力すればよいです。

#include <iostream>

typedef long long ll;

using namespace std;

int main(){
    int N;  cin >> N;
    int a[N+1];
    ll sum = 0LL;
    for(int i=1; i<=N; i++){
        cin >> a[i];
        sum += a[i];
    }

    ll sunuke = 0LL;  /* 0LLは「long long型の0」という意味。LLでlong long型にキャスト */
    ll araiguma;
    ll ans = (ll) 2e10;
    for(int i=1; i<N; i++){
        sunuke += a[i];
        araiguma = sum - sunuke;
        ans = min(ans, abs(araiguma - sunuke));
    }

    cout << ans << endl;

    return 0;
}

　とりあえずa[1]からa[N]までの合計をsumにとります。そんで、a[i]をi=(1→N-1)で動かして、上側の合計(sunuke=Σ(k=1→i))と下側の合計(araiguma=sum-sunuke)との差がansより小さいかなあとゆーのをやればできます。

　そんで、関数abs(x)は、xの絶対値を返す関数です。便利です。if文使って3行くらいで書けるので覚えなくてもいいです。
そんじゃばいばい。

ll abs(ll x){
  if(x<0) return -x;
  else return x;
}

AtCoder Regular Contest 080 C - 4-adjacent

　AtCoderのC問題を埋めようと思い立ったので、頑張る。

　今回は、ABC069、ARC080のC問題「4-adjacent」。adjacentはグーグル先生によると「隣接」という意味らしい。N個の整数a[i]がもらえるので、それを並べ替えて、「隣接」するすべてのaの積(任意のiについてa[i]*a[i+1])を「4」の倍数にできるか？　という問題。
　つまり、数列aを並べ替えて、奇数の隣に必ず4の倍数を持ってこれるかという問題。偶数の隣は、偶数であれば何でもよいからだ。つまり、見るべきはaの具体的な個々の数ではなく、aに含まれている4の倍数の数と奇数の個数である。ただし、奇数、4の倍数、奇数のように、両端が奇数のパターンもある(偶数が0個の場合のみ)ので、注意しようね、って感じ。

#include <iostream>
using namespace std;

int N, a;
int odd=0, even=0, multiple4=0;

int main(void){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> a;
        if(a%2) odd++;
        else if(a%4) even++;
        else multiple4++;
    }

    bool ans = true;

    if(!even){
        if(odd > multiple4+1) ans = false;
    }else{
        if(odd > multiple4) ans = false;
    }

    if(ans) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

　なにかコードについて言うとしたら、if(!even) のところかな。前にも書いたけど、C++やCでは、false値として0が設定されているので(0以外はtrue)、even の否定 !even とは、even==0 と同値です。even==0 のとき、even は偽(false)なので、!even は真(true)になります。even!=0 のときは、even は真(true)なので、!even は偽(false)になります。

　ではでは。

AtCoder Beginer Contest 070 C - Multiple Clocks

　みなさん、おはこんばんにちは。またしても #いいねされた数だけAtCoderでAC タグのための問題です。

　ABC070のC問題「Multiple Clocks(意訳：時計がいっぱい)」です。N個の自然数T[i] (1<=i<=N) がもらえるので、T[1]からT[N]までの最小公倍数を教えてあげる問題です。

#include <iostream>
typedef long long ll;
using namespace std;
 
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
 
ll lcm(ll a, ll b){
    ll g = gcd(a, b);
    return (a / g) * b;
}
 
int main(void){
    int N;  cin >> N;
    ll T, ans = 1LL;
    for(int i=0; i<N; i++){
        cin >> T;
        ans = lcm(ans, T);
    }
 
    cout << ans << endl;
 
    return 0;
}

　関数gcdは最大公約数(GCD:greatest common divisor)を返し、関数lcmは最小公倍数(LCM:least common multiple)を返します。gcdでやってるのは、ユークリッドの互除法で、lcmでは、2つの自然数a,bについて、LCM = (a*b)/GCD が成り立つことを使って、オーバーフローしないように計算しています。この中で、gcdを呼び出しています。
　あと、私みたいに次のようにlcmを求めてしまうと、 (a, b)=(1,1e18) とかのとき(2e9=2*10^9)、O(1e18)になってしまって、余裕でTLEになってしまいます。気を付けましょう。

#include <iostream>
typedef long long ll;
using namespace std;

ll a, b;
ll lcm(x, y){
  if(x==y) return x;
  else if(x<y) x += a;
  else if(y<x) y += b;
  return lcm(x,y);
}
//

　なので、ユークリッドの互除法を使います。ユークリッドの互除法なら、O( log(1e18) ) だそうです。つまり、全体でO(Nlog(1e18) < 1e6)なので、余裕です。
　ちなみに、O(1e9) 程度が競プロにおける標準的な(2秒)計算量の制限になります。

　あ、あと、typedef はだいたいdefineみたいな感じだけど、既にある型(int, bool, long long 等)に新しい名前(integer, boolen, ll 等)を与えたいときに使います。

　じゃ、ちゃお。