chigichan24に人権はあるだろうか,いやない

競技プログラミングやってます。

JOI 本選 2014 オンラインに参加してみた

みなさん。こんばんは。chigichanです。

今日はJOI本選の日でした。自分は予選落ちだったので、オープンコンテストに参加してみることにしました。


どうやら、10:30からやっていたみたいなのに、11:00頃に思い出して、問題を解き始めました。

includeとかはこんな感じ

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<numeric>
#define INF 1e+8
#define EPS 1e-8
#define PB push_back
#define fi first
#define se second
#define rep(i,j) for(int  i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;


11:00
 1問目 JOI 紋章(JOI Emblem)を読む。
 やばそう。JOI旗ってめっちゃ過去問でも見たなぁ(小並感)
 とりあえず、頭悪そうなこーど書いてみよう


11:30
 あ、なんかサンプル通ったし提出。 -> WA
 ですよねーーー。


11:45
 いやー、flag[i+1][j]とかそこらへんの+1 -1するあたりがかなり間違ってたので修正して
 提出 -> WA
 やばいなぁ。これ、どはまりする奴やーーーー。
 あ、文字を置き換えた処理の後、元の文字に戻してない。訂正する。
 提出 -> WA


12:00
 んんんんん?????
 あああああああああ
 いろいろとまずいことしてることに気づく。修正
 
 提出 -> AC
 
 あれれれ????めっちゃ愚直に書いたのに実行時間 0.98[s] でぎりぎり通ってる。
 うけぽよーーーー
 とりあえず100点
 

 こーど

 const int dx[]={0,1,0,1},dy[] = {0,0,1,1};
char flag[1024][1024];
bool made[1024][1024];
int check(string str,int y,int x){
    rep(i,4){
        if(flag[y+dy[i]][x+dx[i]] != str[i])return 0;
    }
    rep(i,4){
        made[y+dy[i]][x+dx[i]] = 1;
    }
    return 1;
}
int solve(int i,int j,string x,int m,int n){
    int res=0;
    if(i == 0 && j == 0){res+=check(x,i,j);}
    else if(i == 0 && j == m-1){res+=check(x,i,j-1);}
    else if(i == n-1 && j == 0){res+=check(x,i-1,j);}
    else if(i == n-1 && j == m-1){res+=check(x,i-1,j-1);}
    else if(i == 0){res+=check(x,i,j);res+=check(x,i,j-1);}
    else if(i == n-1){res+=check(x,i-1,j-1);res+=check(x,i-1,j);}
    else if(j == 0){res+=check(x,i-1,j);res+=check(x,i,j);}
    else if(j == m-1){res+=check(x,i-1,j-1);res+=check(x,i,j-1);}
    else{res+=check(x,i-1,j-1);res+=check(x,i-1,j);res+=check(x,i,j-1);res+=check(x,i,j);}
    return res;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,n){
        scanf("%s",flag[i]);
    }

    string x;
    string y;
    cin >> x;
    cin >> y;
    x += y;
    int ans = 0;
    rep(i,n){
        rep(j,m){
            if(x[0] == flag[i][j]){
                ans += check(x,i,j);
            }
        }
    }
    int ma = 0;
    rep(i,n){
        rep(j,m){
            if(!made[i][j]){
                char sub = flag[i][j];
                int res = 0;
                if(sub == 'J'){
                    int hoge1=0;
                    int hoge2=0;
                    flag[i][j] = 'O';
                    hoge1 = solve(i,j,x,m,n);
                    flag[i][j] = 'I';
                    hoge2 = solve(i,j,x,m,n);
                    flag[i][j] = 'J';
                    res += max(hoge1,hoge2);
                }
                if(sub == 'O'){
                    int hoge1=0;
                    int hoge2=0;
                    flag[i][j] = 'J';
                    hoge1 = solve(i,j,x,m,n);
                    flag[i][j] = 'I';
                    hoge2 = solve(i,j,x,m,n);
                    flag[i][j] = 'O';
                    res += max(hoge1,hoge2);
                }
                if(sub == 'I'){
                    int hoge1=0;
                    int hoge2=0;
                    flag[i][j] = 'J';
                    hoge1 = solve(i,j,x,m,n);
                    flag[i][j] = 'O';
                    hoge2 = solve(i,j,x,m,n);
                    flag[i][j] = 'I';
                    res += max(hoge1,hoge2);
                }
                ma = max(res,ma);
            }
        }
    }
    printf("%d\n",ans+ma);
    return 0;
}

 いやー。いろいろとひどいですなー。

12:10
 ご飯を食べる(*'▽')

13:00
 2問目 IOI 饅頭(IOI Manju) を読む。
 ナップサックっぽい。


13:20
 漸化式が立たない、のでやばい。頭悪い。


13:30
 3問目 バームクーヘン(Baumkuchen) を読む。
 訳が、分からない。尺取り法とか、2分探索とか使いそうだなぁ。とか思ったけど、うまく
 まとまらない。


13:40
 4問目 フクロモモンガ(Sugar Glider) を読む。
 dijkstraっぽい。あきらめて、2問目を解こうと決心する。



14:00
 わからん。わからん。わからん体操を始める。


14:10
 なんか閃いて、コードに興したら、サンプル一致。
 提出
 提出
 提出


14:20
 サーバからの返答がないので、BANされたとしか考えられなくなる。


14:30
 結局、judgeされないまま、終了。


いったい何だったのだろうか????


結果
 1(2)完 100(200)

うん。ザコい。

本選の人権ラインは3完?くらいだったらしいので、残念ですね。
あと、1問目の想定解が気になりますね。
あした、本選erに聞いてみますかな

それでは。