2020/11/23 7:18 D問題を解説ACしました。
2020/11/23 9:02 E問題を解説AC(暫定)しました。
はじめに
A,Bの2完で3626位でした＼(^o^)／
C問題でのWAが取れず、D問題はDPっぽいことは分かったのですが遷移が書けず…。
E問題に取り組んだのですがTLEが取れず終わりました。
コンテスト後にF問題を見たらあっさり解けるという、C,D,E解けないのにFが解けるコンテストがあるのか…。
CをACまで持って行ったので参加記を書きます。
A – Determinant
問題文に計算式が書いてあるので、その通り実装するだけです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<a*d-c*b<<endl;
}
B – Quizzes
クイズに正解すると 1 点増え、不正解だと 1 点減ります。
とのことなので、Xを初期値とし”o”なら+1、”x”なら-1していきましょう。ただし、0点の時に”x”だった場合、それ以上点は下がらないので、少し分岐が必要です。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,X;
cin>>N>>X;
string S;
cin>>S;
for(int i=0;i<S.size();i++){
if(S[i]=='o') X++;
else if(X!=0) X--;
}
cout<<X<<endl;
}
C – Super Ryuma
問題児！！！！！！
斜めを2回使えば市松模様に飛んでいけるので、3回以内に目的地に行けそうです。
0回、1回の条件は簡単で
(r1,c1)と(r2,c2)が同じ → 0回(最初から同じ) (r1,c1)と(r2,c2)との差が3以内 → 1回(3マス以内に移動できる) r1とr2の差と、r2とc2の差が同じ → 1回(斜めはどこまでも移動できる)
問題は2回で行けるかどうかです。
まず、1回で3マスは好きな場所に移動できるので
(r1,c1)と(r2,c2)との差が6以内
は2回で行けそうです。また、冒頭で言った通り市松模様に移動できる=差が偶数であるマスに移動できるため
r1とr2の差と、r2とc2の差の和が2で割り切れる
も2回で行けそうです。
ここまではコンテスト中に思いついて実装できたのですが、斜め移動して3マス移動するパターンをコードに落とし込めませんでした。
後々考えれば簡単な話で、”r1とr2の差と、r2とc2の差が同じ”なら斜め移動できるので、
"r1とr2の差と、r2とc2の差が3つ違い
なら、斜め移動した後に3マス移動で行けることになります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
long long r1,c1,r2,c2;
cin>>r1>>c1>>r2>>c2;
if(r1==r2&&c1==c2) cout<<"0"<<endl;
else if(abs(r1-r2)==abs(c1-c2)) cout<<"1"<<endl;
else if(abs(r1-r2)+abs(c1-c2)<=3) cout<<"1"<<endl;
else {
if(abs(abs(r1-r2)-abs(c1-c2))<=3) cout<<"2"<<endl;
else{
if(abs(r1-r2)+abs(c1-c2)<=6) cout<<"2"<<endl;
else if((abs(r1-r2)+abs(c1-c2))%2==0) cout<<"2"<<endl;
else cout<<"3"<<endl;
}
}
}
苦手な問題でした。
こういったややこしい条件分岐を漏らさず列挙し、コードに落とし込むのが苦手です。(職業プログラマーとしてどうなんだ？という話ですが)
D – increment of coins
コンテスト中にDPということは分かったのですが、遷移が分からず解けませんでした。
解説を見ました。
A,B,Cの時の操作回数の期待値をf(A,B,C)とした場合 (f(A+1,B,C)+1)*A/(A+B+C) ... Aを1枚増やすケース (f(A,B+1,C)+1)*B/(A+B+C) ... Bを1枚増やすケース (f(A,B,C+1)+1)*C/(A+B+C) ... Cを1枚増やすケース これらを足し合わせたものになる。
f(A,B,C)の初期値として、A,B,Cのどれかが100の場合は0になります。
上記をコードに落としていきます。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
double dp[101][101][101];
double dfs(int a,int b,int c){
if(dp[a][b][c]!=-1) return dp[a][b][c];
double sum=a+b+c;
dp[a][b][c]=(dfs(a+1,b,c)+1)*a+(dfs(a,b+1,c)+1)*b+(dfs(a,b,c+1)+1)*c;
dp[a][b][c]/=sum;
return dp[a][b][c];
}
int main(){
int A,B,C;
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
for(int k=0;k<100;k++){
dp[i][j][k]=-1;
}
}
}
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
dp[100][i][j]=0;
dp[i][100][j]=0;
dp[i][j][100]=0;
}
}
cin>>A>>B>>C;
printf("%.12f",dfs(A,B,C));
}
こういうDPを確率DPなんて呼びます。私はかなり苦手です。
E – Third Avenue
単純なBFSだとTLEするため、工夫が必要です。
ボトルネックはワープの処理でしょうか。aがスタートとゴール以外の2000*2000-2マスにある場合、ワープで枝分かれした先で更にワープでの更新確認をしようとすると計算量が膨れます。
一度ワープすれば、そのワープゾーンは使わない(BFSなので、始めに訪れた行き方が最短なはず)ので、制御する必要があります。
暫定解法
テストケースに助けられた感があるので、暫定で嘘っぽい解法を乗せておきます。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int H,W;
cin>>H>>W;
string a[H];
for(int i=0;i<H;i++){
cin>>a[i];
}
vector<pair<int,int>> v[30];
int sy,sx,gy,gx;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(a[i][j]=='G'){
gx=j,gy=i;
}
else if(a[i][j]=='S'){
sx=j,sy=i;
}
else if(a[i][j]>='a'&&a[i][j]<='z'){
v[a[i][j]-'a'].push_back(make_pair(i,j));
}
}
}
int dp[H][W];
int nxx[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
dp[i][j]=-1;
nxx[i][j]=0;
}
}
dp[sy][sx]=0;
queue<pair<int,pair<int,int>>> qu;
qu.push(make_pair(0,make_pair(sy,sx)));
while(!qu.empty()){
if(dp[gy][gx]!=-1) break;
int ny=qu.front().second.first;
int nx=qu.front().second.second;
int nn=qu.front().first;
qu.pop();
//cout<<ny<<","<<nx<<endl;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
for(int i=0;i<4;i++){
int tx=nx+dx[i];
int ty=ny+dy[i];
if(tx>=0&&tx<W&&ty>=0&&ty<H&&
a[ty][tx]!='#'&&(dp[ty][tx]==-1||dp[ty][tx]>dp[ny][nx]+1)){
dp[ty][tx]=dp[ny][nx]+1;
qu.push(make_pair(0,make_pair(ty,tx)));
}
}
if(nn!=1&&nxx[ny][nx]==0&&a[ny][nx]>='a'&&a[ny][nx]<='z'){
nxx[ny][nx]=1;
for(int i=0;i<v[a[ny][nx]-'a'].size();i++){
int ty=v[a[ny][nx]-'a'][i].first;
int tx=v[a[ny][nx]-'a'][i].second;
//cout<<ty<<"="<<tx<<endl;
if(tx>=0&&tx<W&&ty>=0&&ty<H&&
a[ty][tx]!='#'&&(dp[ty][tx]==-1||dp[ty][tx]>dp[ny][nx]+1)){
dp[ty][tx]=dp[ny][nx]+1;
qu.push(make_pair(1,make_pair(ty,tx)));
}
}
}
}
cout<<dp[gy][gx]<<endl;
}
if(dp[gy][gx]!=-1) break;
で計算を打ち切っていますが、これが無ければTLE、これがあればACです。
ゴールに辿り着かないケースでは高速化されない処理のため、たまたまTLEになったテストケースがゴールできるものだったっぽいです。
後で解きなおします…。
F – Programming Contest
個人的にC,D,Eより簡単な問題です。知ってれば制約見ただけで解法がすぐに分かる素直な問題です。
単純にナップサックしようとすると、O(2^N)でTLEします。ただ、Nは最大40とそこまで大きくありません。
こんな時は半分全列挙法です。
入力例 1
5 17
2 3 5 7 11
の場合、
{2 3 5},{7 11} 入力を2つに分けてそれぞれのグループで全パターン列挙する
{0 2 3 5 7 8} , {0 7 11 18}
この時、両方のグループから1個ずつ取り出して足し合わせるを全てのパターンやると、元々の入力の足し合わせ全パターンが網羅できる。
このまま線形探索すると、計算量は変わらないが、片方のグループの探索を2部探索で探すことで計算量を抑えられる。
具体的には、左のグループから7(2+5)を選ぶ場合、右のグループからは10(17-7)に一番近い数字を2部探索で探す。ということを、左のグループ全てに行えばOKです。
こうすることで、列挙にO(2*2^(N/2))、探索に((N/2)*2^(N/2))となりN=40の場合でも何とか間に合うようになります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
vector<long long> ls,rs;
vector<long long> l,r;
void dfs(int pat,long long sum,int n){
if(pat==1&&l.size()==n) ls.push_back(sum);
else if(pat==2&&r.size()==n) rs.push_back(sum);
else{
if(pat==1){
dfs(pat,sum+l[n],n+1);
dfs(pat,sum,n+1);
}
else{
dfs(pat,sum+r[n],n+1);
dfs(pat,sum,n+1);
}
}
}
int main(){
int N;
long long T;
cin>>N>>T;
long long A[N];
for(int i=0;i<N;i++) cin>>A[i];
for(int i=0;i<N/2;i++) l.push_back(A[i]);
for(int i=N/2;i<N;i++) r.push_back(A[i]);
dfs(1,0,0);
dfs(2,0,0);
sort(ls.begin(),ls.end());
sort(rs.begin(),rs.end());
long long ans=0;
for(int i=0;i<ls.size();i++){
auto a=lower_bound(rs.begin(),rs.end(),T-ls[i]);
int ai=a-rs.begin();
//cout<<ls[i]<<","<<rs[ai]<<endl;
if(ai!=rs.size()&&ls[i]+rs[ai]<=T) ans=max(ans,ls[i]+rs[ai]);
if(ai!=0&&ls[i]+rs[ai-1]<=T) ans=max(ans,ls[i]+rs[ai-1]);
}
cout<<ans<<endl;
}
おわりに
ABCにしては中々難しかったです。
Beginner Contestって名前だけど、Beginner向けでは難易度ですよね…。
青になって早く引退したいのに、レートが落ちちゃいましたが気楽にやっていきます＞＜
コメント