ABC185 参戦記録 p.33
itsukiです。
AtCoder Beginner Contest 185 に参戦した様子です。解説記事ではありません。
結果は A, B, C の 3完でした。
回答時間合計：70分25秒
パフォーマンス：536
考察の流れ
A - ABC Preparation
A1, A2, A3, A4 の最小値！
#include <stdio.h>
#define MIN(x,y) ((x)<(y)?(x):(y))
int main(){
int a1,a2,a3,a4,ans;
scanf("%d%d%d%d",&a1,&a2,&a3,&a4);
ans = MIN(a1,a2);
ans = MIN(ans,a3);
ans = MIN(ans,a4);
printf("%d\n",ans);
return 0;
}ここまで：1分46秒
B - Smartphone Addiction
問題文を理解するまでに時間がかかる
（当初の方針）
「カフェに寄らない場合（N - T）」に
「カフェに寄った時間（B_i - A_i）の 2倍」の和を足していけばいい？
-> フル充電になった場合や、途中で 0になった場合が抜けていてダメ！
問題文の流れをそのまま愚直に書く
#include <stdio.h>
#define Yes() printf("Yes\n")
#define No() printf("No\n")
typedef long long ll;
int main(){
ll n,m,t,a[1005]={0},b[1005]={0},tmp,now=0;
scanf("%lld%lld%lld",&n,&m,&t);
tmp=n;
for(int i=0; i<m; i++){
scanf("%lld%lld",&a[i],&b[i]);
// 消費
tmp -= (a[i]-now);
if( tmp <= 0 ){ No(); return 0; }
now = a[i];
// 充電
tmp += (b[i]-now);
if( tmp > n ){ tmp = n; } // フル充電
now = b[i];
}
// 最後のカフェ～帰宅
tmp -= (t-now);
if( tmp <= 0 ){ No(); }
else { Yes(); }
return 0;
}ここまで：31分16秒
・最初の方針がダメだったときに、立て直すまでに時間をかけすぎ
・サンプルが親切だったから助かったようなもの…
C - Duodecim Ferra
組み合わせか？と思いつつ ggって迷走し、「全射の個数」「スターリング数」にまで漂流
順列／組み合わせを履修した時に「仕切りを入れる場所の選び方」を考えたのを思い出す
「仕切りをいれることが出来る場所の数」を n 、「仕切りの数」を r とする nCr を考えると
n = L-1
r = 12-1
という組み合わせの問題になる
#include <stdio.h>
typedef long long ll;
ll _nCr(ll n, ll r){ if( n<r || n<0 || r<0 ){ return 0; } ll ans=1; if(r>(n-r)){ r=n-r; } for(ll i=1;i<=r;i++){ ans*=(n+1-i); ans/=i; } return ans; }
int main(){
ll i,n,k=12,ans=0;
scanf("%lld",&n);
printf("%lld\n",_nCr(n-1,k-1));
return 0;
}ここまで：70分25秒
・迷走した時間がもったいなかった
・解説を見たところ、オーバーフローの危険があったらしい…自作の nCr 関数は大丈夫だったぽいが、全く考えていなかったのでもしこれでオーバーフローだったらアウトだった
D - Stamp
入力例 4 より、M==0 の場合は ハンコの大きさ (k) ＝ 全マス (N) になるため、答えは 0
一番幅の狭いところが k になる（ここでコンテスト終了）
コンテスト後：
先頭マスが青色（A_1==1）だったり、末尾マスが青色（A_M==N）だったりした場合に 場合分けが面倒なので、N個のマスの両端に青色マスを置く
下図は入力例 1 の脳内イメージ
あとはひたすら 連続する白色マスの数を、ハンコの大きさ k で割って小数点以下を切り上げたものを加算していく
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MIN(x,y) ((x)<(y)?(x):(y))
int compare_int(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
int main(){
int i,n,m,a[200005]={0},k=999999999,tmp,ans=0;
scanf("%d%d",&n,&m); n++;
// 全部白
if(m==0){ printf("1\n"); return 0; }
a[0]=0; a[m+1]=n+1;
for(i=0; i<m; i++){ scanf("%d",&a[i+1]); }
qsort( a, m+1, sizeof(int), compare_int );
for(i=0; i<=m; i++){
tmp = MIN(k, a[i+1]-a[i]);
if( tmp!=1 ){ k=tmp; }
}
// 全部青
if( k==1 ){ printf("0\n"); return 0; }
k--;
for(i=0; i<=m; i++){
ans += (int)ceil((double)(a[i+1]-a[i]-1) / (double)k);
}
printf("%d\n",ans);
return 0;
}まとめ
・「問題文通り書く」があまりにも苦手
・順列／組み合わせの履修結果を発揮できたのは嬉しい
・発想は良くても、早解きできないと（コンテストでは）意味がない
・このまま 1色上のパフォーマンスを安定して積み上げていきたい
引き続き、のんびり精進します。