AtCoder Beginner Contest 199

昨日受けたので復習。

問題A, B

A - Square Inequality

B - Intersection

についてはすぐ実装が終わった。AOJのITP1をすべてこなしたおかげで力がついたかもしれない。せっかくなのでB問題に使ったmax_elementとmin_elementの使い方を復習しておく。

vector<int> x(100) = {/* hoge */};
cout << *max_element(x.begin(), x.end());  // 返り値がiteratorなので*を忘れずに！
cout << *min_element(x.begin(), x.end());  // 同様

問題C

C - IPFL

について。問題通り素直に実装したがTLE。入力関係の遅さを疑い，cinをscanfにするが，手間取った上にMLEまでつく。cinに戻す。例えばすべてのクエリがで，のとき，このようなコードだと間に合わないらしい:

case 2:
    string tmp1 = s.substr(0, n);
    string tmp2 = s.substr(n, n);
    s = tmp2 + tmp1;
    break;

substr関数がなのだそう。結局flagを作って(そのときはint型にしたが多分bool型にしておいたほうが良かったな…)T=2のときflagを反転させ，T=1のときにflagによって処理を変える方針がいいっぽい。最終的に提出したコード:

Submission #22026711 - AtCoder Beginner Contest 199（Sponsored by Panasonic）

最後に何を思ったかswapを使わないほうが早いのかな？とか考えてswapを使わなかったが，絶対使ったほうがいいに決まってる。

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;


int main() {
    string A = "cat";
    string B = "dog";
    clock_t start = clock();
    rep(i, 1000000) {
        swap(A, B);
    }
    clock_t end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    string tmp;
    start = clock();
    rep(i, 1000000) {
        tmp = A;
        A = B;
        B = tmp;
    }
    end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
}

結果:

1.013s //swap
1.432s //自作swap

今度からはSTLを疑わず使います…あと前半と後半の文字列を分割して保存しておくやり方は頭いいなあと思った。

問題D

D - RGB Coloring 2

わかんなかった。この問題青diffらしいので，別の基礎的な問題をやってからまたこっちに戻ってこようと思う。