本日2つ目のABCです。
A – Discount Fare
A - Discount Fare
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題文の通り、X(A駅からB駅)+Y(B駅からC駅)/2(特別券)をすればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int X,Y;
cin>>X>>Y;
cout<<X+Y/2<<endl;
}
B – Palace
B - Palace
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
これも問題文の通り、N個に対してT−x×0.006 を計算し、Aとの差が最も小さいものを出力すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
int T,A;
cin>>N>>T>>A;
double mxv=DBL_MAX;
int mx=-1;
for(int i=0;i<N;i++){
double H;
cin>>H;
double kion=T-H*0.006;
double sa=abs(A-kion);
if(sa<mxv){
mx=i;
mxv=sa;
}
}
cout<<mx+1<<endl;
}
C – ID
C - ID
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
発想自体は簡単で、PごとにYの昇順でまとめて、小さい順に番号を割り当てるだけです。
ただ実装がやや難しく、出力の形式も厄介です。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
map<int,int> m[N+1];
for(int i=0;i<M;i++){
int P,Y;
cin>>P>>Y;
m[P].emplace(Y,i);
}
string ans[M];
for(int i=1;i<=N;i++){
auto it=m[i].begin();
int c=1;
while(it!=m[i].end()){
string tmp="";
int n=c;
for(int j=0;j<6;j++){
tmp=(char)(n%10+'0')+tmp;
n/=10;
}
n=i;
for(int j=0;j<6;j++){
tmp=(char)(n%10+'0')+tmp;
n/=10;
}
ans[it->second]=tmp;
it++;
c++;
}
}
for(int i=0;i<M;i++){
cout<<ans[i]<<endl;
}
}
結構ゴリゴリ書いてしまいました。
私は、int型から0埋めのstring型を生成していますが、printfの書式設定で%06dをすれば一発みたいです。(他の提出を覗いてみました)
以下、書きなおしです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
int P[M],Y[M];
map<int,int> m[N+1];
for(int i=0;i<M;i++){
cin>>P[i]>>Y[i];
m[P[i]].emplace(Y[i],i);
}
int ans[M];
for(int i=1;i<=N;i++){
auto it=m[i].begin();
int c=1;
while(it!=m[i].end()){
ans[it->second]=c++;
it++;
}
}
for(int i=0;i<M;i++){
printf("%06d%06d\n",P[i],ans[i]);
}
}
かなりスッキリしたかと思います。
D – Number of Amidakuji
D - Number of Amidakuji
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
高さiの時にどの縦棒にいるかをdpで管理すれば解けそうです。ややこしさとして、横棒の引くパターンが少し面倒なことです。
入力例の絵にはありませんが、ある高さに2本横棒が引いてあるパターン(1と2,4と5みたいなの)もあるので、単純にはいかなさそうです。
今回、制約が弱いということもあり、bit全探索で「正しいあみだくじ」かは関係なく全パターンの横棒を列挙し、その中から「正しいあみだくじ」である横棒の引き方であるものに対し、dpの遷移をするようにしました。
#include<bits/stdc++.h>
using namespace std;
int main(){
int H,W,K;
long long mod=1000000007;
cin>>H>>W>>K;
long long dp[H+1][W+1];
for(int i=0;i<H+1;i++){
for(int j=0;j<W+1;j++){
dp[i][j]=0;
}
}
dp[0][1]=1;
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
for(int k=0;k<(1<<(W-1));k++){
bool f=false;
int n=k;
int mv=0;
bool t=false;
for(int l=0;l<W-1;l++){
if(n%2==1){
if(t) f=true;
else t=true;
int idx=W-l;
if(idx==j) mv=-1;
if(idx-1==j) mv=1;
}
else t=false;
n/=2;
}
if(f) continue;
dp[i][j]+=dp[i-1][j+mv];
dp[i][j]%=mod;
}
}
}
cout<<dp[H][K]<<endl;
}
“あみだくじ”と聞いて、縦に連結する問題かと思ったのですが違ってビックリしました。> <
コメント