JOI2012-2013本選参加記

プラクティスの日はそれなりに交流できて楽しかった。
結論から言うと2, 3がバグって1完しかできませんでした。去年と違ってそれなりに頑張っていたので無念な気持ちに..萎えてコード回収しなかったのでさっき書いたコードを貼っておきます。
合宿行ける人は頑張ってください!

1. 適当に交互列に切って連続した3つをやる

#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)

int n, ans = 1;
int il[100010];
int run[100010];

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%d", &il[i]);
    int crt = il[0], now = 0, ret = 1;
    for(int i = 1; i < n; ++i){
	if(il[i] != crt){
	    crt = il[i];
	    ret++;
	}else{
	    run[now++] = ret;
	    ret = 1;
	    crt = il[i];
	}
    }
    run[now++] = ret;
    rep(i, now) ans = max(ans, run[i] + run[i + 1] + run[i + 2]);
    printf("%d\n", ans);
    return 0;
}

2. よくあるDPなのはわかるがバグる。しかも途中で車庫に追いやれないのに気付くのにめちゃくちゃ時間がかかった...

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)

int m, n, ans;
string s, t;
char tr[] = "IO";
int dp[2010][2010][2];

int solve(int a, int b, int bit){
    if(dp[a][b][bit] >= 0) return dp[a][b][bit];
    if(a == m && b == n) return 0;
    int ret = 0;
    if(a < m && tr[bit] == s[a]) ret = max(ret, solve(a + 1, b, bit ^ 1) + 1);
    if(b < n && tr[bit] == t[b]) ret = max(ret, solve(a, b + 1, bit ^ 1) + 1); 
    return dp[a][b][bit] = ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n >> s >> t;
    memset(dp, -1, sizeof(dp));
    rep(i, m){
	rep(j, n){
	    int tmp = solve(i, j, 0);
	    ans = max(ans, tmp - (tmp % 2 == 0));
	}
    }
    cout << ans << endl;
    return 0;
}

3.適当にグラフを構築してDijkstra. まず無難に部分点を取りに行こうとするが、どうせ後でダイクストラするので書いておこうとして、priority_queueにgreater<>をつけるのを忘れて死亡。
そりゃTLEするわ.....

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, int> PT;
typedef pair<ll, int> PL;

struct edge{
    int to, cost;
    edge(int to, int cost) : to(to), cost(cost){}
};

int m, n, k;
PT ch[200010];
vector<edge> g[400020];
ll d[400020];

bool cmp(const PT a, const PT b){
    if(a.fi.se != b.fi.se) return a.fi.se < b.fi.se;
    else return a.fi.fi < b.fi.fi;
}

void dijk(){
    priority_queue<PL, vector<PL>, greater<PL> > que;
    fill(d, d + 400020, LLONG_MAX);
    d[0] = 0;
    que.push(PL(0, 0));
    while(!que.empty()){
	PL p = que.top(); que.pop();
	int v = p.se;
	if(p.fi > d[v]) continue;
	rep(i, g[v].size()){
	    edge e = g[v][i];
	    if(d[e.to] > d[v] + e.cost){
		d[e.to] = d[v] + e.cost;
		que.push(mp(d[e.to], e.to));
	    }
	}
    }
}

int main(){
    scanf("%d %d %d", &m, &n, &k);
    rep(i, k){
	ch[i].se = i + 1;
	scanf("%d %d", &ch[i].fi.fi, &ch[i].fi.se);
	g[i + 1].pb(edge(i + 200011, 1));
	g[i + 200011].pb(edge(i + 1, 1));
    }
    ch[k] = mp(mp(1, 1), 0); ch[k + 1] = mp(mp(m, n), k + 1);
    sort(ch, ch + k + 2);
    rep(i, k + 1){
	if(ch[i].fi.fi == ch[i + 1].fi.fi){
	    g[ch[i].se].pb(edge(ch[i + 1].se, ch[i + 1].fi.se - ch[i].fi.se));
	    g[ch[i + 1].se].pb(edge(ch[i].se, ch[i + 1].fi.se - ch[i].fi.se));
	}
    }
    sort(ch, ch + k + 2, cmp);
    rep(i, k + 1){
	if(ch[i].fi.se == ch[i + 1].fi.se){
	    g[ch[i].se + 200010].pb(edge(ch[i + 1].se + 200010, ch[i + 1].fi.fi - ch[i].fi.fi));
	    g[ch[i + 1].se + 200010].pb(edge(ch[i].se + 200010, ch[i + 1].fi.fi - ch[i].fi.fi));
	}
    }
    dijk();
    if(d[k + 1] == LLONG_MAX && d[k + 200011] == LLONG_MAX) printf("-1\n");
    else printf("%lld\n", min(d[k + 1], d[k + 200011]));
    return 0;
}

4. 時間中には精神的余裕が無くて読めなかった。imos先生ぱない><

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)

int n;
int apply_i[1000010], apply_o[1000010];
char s[1000010];
bool used[1000010];

bool C(int k){
    memset(used, false, sizeof(used));
    int now = 0;
    for(int i = n - 1; i >= 0; --i){
	if(now >= k) break;
	if(s[i] == 'I'){
	    apply_i[now++] = i;
	    used[i] = true;
	}
    }
    if(now < k) return false;
    now = 0;
    for(int i = n - 1; i >= 0; --i){
	if(now >= k) break;
	if(s[i] == 'O' && apply_i[now] >= i) apply_o[now++] = i;
    }
    if(now < k) return false;
    now = 0;
    for(int i = n - 1; i >= 0; --i){
	if(now >= k) break;
	if(i <= apply_o[now] && (s[i] == 'J' || (s[i] == 'I' && !used[i]))) now++;
    }
    if(now < k) return false;
    return true;
}

int main(){
    scanf("%d", &n);
    scanf("%s", s);
    int lb = 0, ub = 400000;
    while(ub - lb > 1){
	int mid = (ub + lb) / 2;
	if(C(mid)) lb = mid;
	else ub = mid;
    }
    printf("%d\n", lb);
    return 0;
}

5. 反転数の求め方は知っていたけれど....解説聞いてやばすぎると思った。そのうち実装します。


まとめ : bugparty(絶望) バグったら一旦捨てて他のやつ解きに行くとかやるべきだなあ...
部分点集める作業が全くできなかったので反省。問題文はちゃんと読みましょう。みんなやばいと思う。400点以上0人とか前代未聞完ある。後1回だけ出れるので頑張る。とはいってもしばらく立ち直れないかも....