ABC178 参戦記録 p.6
itsukiです。
AtCoder Beginner Contest 178 に参戦した様子です。解説記事ではありません。
結果は A, B の 2完でした。
考察の流れ
A. Not
深く考えずに if文
#include <stdio.h>
int main(){
int x;
scanf("%d",&x);
if( x==0 ){ printf("1\n"); }
else { printf("0\n"); }
return 0;
}コンテスト後：
こっちの方が格好良かったなぁと思った
#include <stdio.h>
int main(){
int x;
scanf("%d",&x);
printf("%d",!x);
return 0;
}B. Product Max
a, b, c, d が、全部 正だった場合と、全部 負だった場合と、…
もしかして場合分けせずに全部比較すればいいのでは？
#include <stdio.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
typedef long long ll;
int main(){
ll ans,a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
printf("%lld\n", (ll)MAX( (ll)MAX(a*c,a*d), (ll)MAX(b*c,b*d) ));
return 0;
}C. Ubiquity
さっぱりわからない
ひとまず N=3 を手計算しようとするも多くて諦める
余事象を思いついた！はずが、謎のベン図を生成する
|A∪B| = |A| + |B| - |A∩B| まで思いつくも、
コードに落とし込めない＆mod が分かってないまま時間切れ
#include <stdio.h>
#define MOD 1000000007 /* 10^9 + 7 */
typedef long long ll;
ll POW(ll a, ll n){ ll ans=1; while(n){if(n&1){ans=ans*a%MOD;} a=a*a%MOD; n>>=1; } return ans; }
int main(){
ll n,ans=0;
scanf("%lld",&n);
ans = (POW(10,n) - POW(9,n)) + (POW(10,n) - POW(9,n)) - POW(8,n);
printf("%lld\n",ans);
return 0;
}コンテスト後：
解説AC（正しい考え方は解説を参照してください）
#include <stdio.h>
#define MOD 1000000007 /* 10^9 + 7 */
typedef long long ll;
ll POW(ll a, ll n){ ll ans=1; while(n){if(n&1){ans=ans*a%MOD;} a=a*a%MOD; n>>=1; } return ans; }
int main(){
ll n,ans=0;
scanf("%lld",&n);
ans = POW(10,n) - POW(9,n) - POW(9,n) + POW(8,n);
ans%=MOD;
ans=(ans+MOD)%MOD;
printf("%lld\n",ans);
return 0;
}まとめ
・ちゃんとベン図を書きましょう
・包除原理、余事象、mod 、要再履修
・重複組み合わせを初めて知った
・悔しい！次は解く！
引き続き、のんびり精進します。
#note初心者 #備忘録 #参戦記録 #AtCoder #ABC #プログラミング #競プロ #C言語 #数学 #ベン図 #包除原理 #余事象 #重複組み合わせ #mod