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

(o_o)

ブログ。

AtCoder #007 のtesterやってました

テスターやってました。この時間帯はバイトだから参加できないのよね。
Dのテストケースをつくるときのわくわく感がやばかった。実際のテストケースファイルを作ったのはほとんどちょくだいさんだったけど。


A
前から順にやるだけ。resを用意せず順次出力していって最後に改行してもいい。

#include <iostream>
#include <string>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define sz          size()

using namespace std;

int main(void)
{
    string s, str, res;
    cin >> s >> str;
    REP (i, str.sz) if (str[i] != s[0]) res += str[i];
    cout << res << endl;
    return 0;
}


B
同じCDが二度以上使われたり二連続で使われたりするケースがあることに注意。

#include <iostream>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;

int a[128];

int main(void)
{
    int n, m;
    cin >> n >> m;
    REP (i, 128) a[i] = i;
    REP (i, m){
    	int in, num;
    	cin >> in;
    	REP (j, n + 1) if (a[j] == in) num = j;
    	swap (a[0], a[num]);
    }
    FOR (i, 1, n + 1) cout << a[i] << endl;
    return 0;
}


C
全探索。ビットを使うとよい。greedyだと落ちる。
割と実装めんどいかなと思ってたけどそうでもなかった。

#include <iostream>
#include <string>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define sz          size()

using namespace std;

int main(void)
{
    string str;
    int a = 0, res = 99999;
    cin >> str;
    REP (i, str.sz) a = a * 2 + (str[i] == 'o');
    a *= (1 << str.sz) + 1;
    REP (i, 1 << str.sz) {
    	int num = 0, cnt = 0;
    	REP (j, str.sz){
    		if ((i & (1 << j)) == 0) continue;
    		num |= (a >> j);
    		cnt++;
    	}
    	if ((num + 1) % (1 << str.sz) == 0) res = min (res, cnt);
    }
    cout << res << endl;
    return 0;
}


D
初項はたいてい1桁になる。
例えば
3234363840
のケースは初項は32ではない。3である。2項目は234363840。
あとは2項目をどこまで取るかで場合分けしてそれぞれが数列になりうるかどうかを判定する。数列になるもののうち2項目の値が最小となる場合を出力。
"00000"や"0001"や"0002"などのケースに注意。それぞれの出力結果は、"100000 1","1000 1","1000 1000"である。
死者数多数 http://arc007.contest.atcoder.jp/submissions/all?task_screen_name=arc007_4&language_screen_name=&status=

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define sz          size()
#define mp          make_pair

using namespace std;

typedef pair<string,string> P;

// return true iff a>b
bool compare (string &a,string &b){
    if(a.sz != b.sz) return a.sz > b.sz;
    REP(i,a.sz) if(a[i] != b[i])return a[i] > b[i];
    return false;
}

// increase or decrease in digit
string clean (string a){
    a = "0" + a;
    for (int i = a.sz-1 ; i >= 0; i--){
        if (a[i] > '9') { a[i] -= 10; a[i-1]++; }
        else if (a[i] < '0') { a[i] += 10; a[i-1] -= 1; }
    }
    REP(i,a.sz) if(a[i] > '0') return a.substr(i);
    return "0";
}

// culcurate a + b
string aplusb (string a, string b){
    if (compare(a,b)) swap(a,b);
    b = "0" + b;
    REP(i,a.sz) b[b.sz-1-i] += a[a.sz-1-i] - '0';
    return clean(b);
}

// culcurate a - b
string aminusb (string a, string b){
    if (compare(a,b)) swap(a,b);
    REP(i,a.sz) b[b.sz-1-i] -= a[a.sz-1-i] - '0';
    return clean(b);
}

// return true iff it can be a part of a series
bool isSeries(string term, string dif, string &series){
    string str;
    int cnt = 0;
    while (str.sz < series.sz) {
        term = aplusb(term, dif);
        str += term;
        while (cnt < series.sz && cnt < str.sz) {
            if (series[cnt] != str[cnt]) return false;
            cnt++;
        }
    }
    return true;
}

P solve (string str)
{    
    // culcurate first term
    int num = 1;
    FOR(i,1,str.sz){
        if (str[i] != '0') break;
        num = i + 1;
    }
    string firstTerm = str[0]=='0' ? "1" : "";
    firstTerm += str.substr(0, num);
    str = str.substr(num);
    // cout << firstTerm << " " << str << endl;
    
    // culcurate common difference
    string s;
    
    if(isSeries(firstTerm,"1",str)) return mp(firstTerm, "1");
    
    REP(i,10000000){
        if(i < str.sz) s += str[i]; else s += "0";
        if(compare(s,firstTerm)){
            string dif = aminusb(s,firstTerm);
            if(isSeries(firstTerm, dif, str)) return mp(firstTerm, dif);            
        }
    }
    return mp(firstTerm,str);
}

int main(void)
{
    string str;
    cin >> str;
    P ans = solve(str);
    cout << ans.first << " " << ans.second << endl;
    return 0;
}