JOI惨敗日誌2
こんにちはつよっしーというものです。約1年ぶりにJOIの記事を書きます。結果は無惨に予選落ちでした。
誤読はするし、緊張で頭は回らず散々でしたね。まぁ、感想はのちほど書きます。
1問目・・・はい
2問目・・・誤読
3問目・・・はい
4問目・・・bitDPと終ってから分かった
5問目・・・座標でDPみたいなことするらしい（？？？）
6問目・・・拡張ダイクストラ
1～3はあれでしたが、4～6の中で一番解けそうな6が解けずに終わって予選落ちしたのが悲しい（2を誤読して4ケース落としてたのでどっちにしろ予選落ち）
6問目は答えの配列を1次元にしてたのでバグってた（悲しい）。一応予選終わった後に解いた6のコードをあげます。
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
static const int dx[] = {0,0,1,-1};
static const int dy[] = {1,-1,0,0};
typedef pair< int,int > PII;
typedef pair< int,pair<int,int> > PPII;
typedef pair< int,pair<int,pair<int, int> > > PPPII;
struct edge{
int to,cost;
edge(){}
edge(int p1,int p2){
to=p1;
cost=p2;
}
};
vector<edge> G[10005];
int dist[10005][205][5];
int A[20005];
int N,M,X;
void dijkstra(int s){
priority_queue<PPPII,vector<PPPII>,greater<PPPII> > que;
for(int i=0;i<10005;++i)for(int j=0;j<=200;++j)for(int k=0;k<3;++k)dist[i][j][k]=INF;
dist[s][0][A[s]]=0;
que.push(PPPII(0,PPII(s,PII(0,A[s]))));
while(!que.empty()){
PPPII p = que.top();
que.pop();
int v=p.second.first;
int time=p.second.second.first;
int hot=p.second.second.second;
if(dist[v][time][hot]<p.first)continue;
for(int i=0;i<G[v].size();i++){
edge e = G[v][i];
int ntime,nhot;
if(A[e.to]==0){
if(hot==2){
if(time+e.cost<X)continue;
else {
ntime=0;
nhot=A[e.to];
if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
}
}
}
if(hot==0){
ntime=0;
nhot=A[e.to];
if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
}
}
}
else if(A[e.to]==2){
if(hot==0){
if(time+e.cost<X)continue;
else {
ntime=0;
nhot=A[e.to];
if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
}
}
}
if(hot==2){
ntime=0;
nhot=A[e.to];
if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
}
}
}
else if(A[e.to]==1){
ntime=time+e.cost;
nhot=hot;
if(ntime>=X)ntime=200;
if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
}
}
}
}
}
signed main(){
cin>>N>>M>>X;
for(int i=0;i<N;++i)cin>>A[i];
for(int i=0;i<M;++i){
int a,b,c;
cin>>a>>b>>c;
a--;
b--;
G[a].PB(edge(b,c));
G[b].PB(edge(a,c));
}
dijkstra(0);
int ans=INF;
for(int i=0;i<=200;++i){
for(int j=0;j<3;++j){
ans=min(ans,dist[N-1][i][j]);
}
}
cout<<ans<<endl;
return 0;
}JOIの感想なんですが実力を十分に発揮できず悔しさが残りました。自分が本番に弱いのとコンテスト慣れしてなかったのが原因ですね。
これからについてなんですが競プロはJOIだけではないのでPCKやICPCに向けてこれまで以上に精進したいと思います。
あと、Imagine Capについてなんですが特に書くことが思いつかなかったので予選が終わったころにでも書きたいと思います。
お通夜みたいな記事になってしまいましたがJOIは@kuro_koji_と@_izrytと@gedorinkuの三人が僕の無念を晴らしてIOI代表になってくれるので応援しています。
次回は@Fukusan64です。
Reindeer with no sense of direction （方向音痴のトナカイ）
JOI難易度8の問題ですね。
Reindeer with no sense of direction | Aizu Online Judge
まあ、1<=N,M<=100なので全探索できそうってなったので全探索をした。
当然めちゃくちゃ遅い。
そこで空き地は移動するのに意味がないので家から家（教会）に飛ぶように変えることで遷移が結構減った。
これで一応、JOI予選だったらそこそこ待てば答えがでる。
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
typedef pair<int,int> pii;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int N,M;
int feld[11][11];
int cnt;
pii last;
int ans;
void dfs(int x,int y,int sum){
for(int i=0;i<4;++i){
int nx=x;
int ny=y;
while(1){
nx+=dx[i];
ny+=dy[i];
if(nx<0||nx>=N||ny<0||ny>=M)break;
if(feld[ny][nx]==-1)break;
if(feld[ny][nx]==1){
feld[ny][nx]=-1;
dfs(nx,ny,sum+1);
feld[ny][nx]=1;
}
else if(feld[ny][nx]==2){
if(sum==cnt){
ans++;
return ;
}
}
}
}
return ;
}
signed main(){
while(1){
cin>>N>>M;
if(N==0&&M==0)break;
memset(feld,-1,sizeof(feld));
for(int i=0;i<M;++i){
for(int j=0;j<N;++j){
cin>>feld[i][j];
if(feld[i][j]==2){
last.FI=i;
last.SE=j;
}
else if(feld[i][j]==1)cnt++;
}
}
dfs(last.SE,last.FI,0);
cout<<ans<<endl;
ans=0;
cnt=0;
}
}しかしAOJではTLEなのでダメ。
もう少し考えると、すでに配り終わった状態からプレゼントを回収するというのを思いつく。
プレゼントを回収していないところは上空を飛ぶことができず、降り立ってプレゼントを回収し教会へ戻るというふうにすることで遷移の数が減り計算量もいい感じになった。
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
typedef pair<int,int> pii;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int N,M;
int feld[11][11];
int cnt;
pii last;
int ans;
void dfs(int x,int y,int sum){
for(int i=0;i<4;++i){
int nx=x;
int ny=y;
while(1){
nx+=dx[i];
ny+=dy[i];
if(nx<0||nx>=N||ny<0||ny>=M)break;
if(feld[ny][nx]==1){
feld[ny][nx]=-1;
dfs(nx,ny,sum+1);
feld[ny][nx]=1;
break;
}
else if(feld[ny][nx]==2){
if(sum==cnt){
ans++;
return ;
}
}
}
}
return ;
}
signed main(){
while(1){
cin>>N>>M;
if(N==0&&M==0)break;
memset(feld,-1,sizeof(feld));
for(int i=0;i<M;++i){
for(int j=0;j<N;++j){
cin>>feld[i][j];
if(feld[i][j]==2){
last.FI=i;
last.SE=j;
}
else if(feld[i][j]==1)cnt++;
}
}
dfs(last.SE,last.FI,0);
cout<<ans<<endl;
ans=0;
cnt=0;
}
}はい(AC)
かなり時間をかけたのでもっと精進が必要ですね。
Dividing Snacks (お菓子の分割)
JOI非公式難易度表7の問題。結構、険しかった。
問題は読んで、どうぞ。
Dividing Snacks | Aizu Online Judge
DPであろうとは思ったけど、どんなふうにするか検討がつかない。
でもしばらく考えるとN個の長さ1mmのお菓子をAとBの二つのグループに分けていくと考えればよさそうということに気づく。
dp[N][Aに選んだ数][AかBか]でいけそう。
しかし制約が2<=N<=10000であるためMLE（険しい）
またしばらく考えてdp[i+1][...][...]がdp[i][...][...]によって決まるためdp配列を使いまわせることに気づく(勝った)
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define FI first
#define SE second
using namespace std;
typedef pair<int,int> pii;
static const int inf = 1ll<<60;
static const int MAX_N = 10000;
int N;
int a[MAX_N+5];
int dp[2][MAX_N/2+5][2];
signed main(){
cin>>N;
for(int i=1;i<N;++i)cin>>a[i];
for(int i=0;i<2;++i)for(int j=0;j<N/2;++j)for(int k=0;k<2;++k)dp[i][j][k]=inf;
dp[0][0][0]=0;
for(int i=0;i<N;++i){
for(int j=0;j<N/2;++j){
dp[(i+1)%2][j+1][0]=min(dp[i%2][j][0],dp[i%2][j][1]+a[i+1]);
dp[(i+1)%2][j][1]=min(dp[i%2][j][0]+a[i+1],dp[i%2][j][1]);
}
for(int j=0;j<N/2;++j)dp[i%2][j][0]=dp[i%2][j][1]=inf;
}
cout<<min(dp[N%2][N/2][0],dp[N%2][N/2][0])<<endl;
}
ABC041 徒競走
結構まえに解いた問題が好きだったので書く。
1～Nまでの番号のついたウサギが徒競走し、x番目がy番目より早く着くという情報がM個与えられる。
その情報にあうような着順が何通りあるか求める問題。
制約をみると1<=N<=16であったのですぐにbitDPを思いついた。
しかし僕はDPができないのでメモ化再帰をする。（弱い）
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define FI first
#define SE second
using namespace std;
typedef pair<int,int> PII;
static const int inf = 1ll<<60;
static const int MAX_N = 16;
static const int MBIT = 1<<17;
int N;
int M;
int all;
int mem[MBIT];
vector<int> V[MAX_N+1];
int cal(int bit){
int res=0;
if(mem[bit]!=-1)return mem[bit];
if(bit==0)return 1;
for(int i=1;i<=N;++i){
bool is=false;
int b=1<<i;
for(int j=0;j<V[i].size();++j){
int k=1<<V[i][j];
if(!(k&bit)){
is=true;
break;
}
}
if(is)continue;
if(bit&b){
res+=cal(bit-b);
}
}
return mem[bit]=res;
}
signed main(){
memset(mem,-1,sizeof(mem));
cin>>N>>M;
for(int i=1;i<=N;++i)all+=pow(2,i);
for(int i=0;i<M;++i){
int x,y;
cin>>x>>y;
V[x].PB(y);
}
int ans=0;
ans=cal(all);
cout<<ans<<endl;
}
JOI惨敗日誌
こんにちは。つよっしーというものです。JOI予選落ちの烙印をつけられるであろう人間です。まだ結果は出ていませんが4問目のソースコードを提出できてないと思います。（まぁ、ケース１しか通ってないので最高320点です。）悲しいですね。
1問目・・・やるだけ
2問目・・・やるだけ
3問目・・・戦犯。誤読しました。実際はやるだけっだったはず。
4問目・・・悲しい。考察する時間がなくO(n*t)しか書けなかった。
5問目・・・幅っぽいと思って少し考えて4問目に帰る。ここで4問目のソースコードを提出していないのに気付いて急いでアップロードを押したらコンテスト終了の画面に飛ばされる。悲しい(悲しい(悲しい))。某プロによるとやるだけらしい()。
6問目・・・悲しい。
JOIはDPがでると聞いていたけどグラフの問題がでて悲しみが単調増加しています。(6問目はDPっぽい？）この悲しみを晴らすためにデレステに5K課金しましたが悲しみが増えました。
いよいよ明日は結果発表ですがプロたちからのハラスメントによって結果をみる気力がないです。予選を通過したであろう人々は本選に向けて精進してください。最後に僕に人権をください。(終わります)
