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に聞いてみますかな
それでは。
