ABC178 参戦記録 p.6

itsukiです。
AtCoder Beginner Contest 178 に参戦した様子です。解説記事ではありません。

AtCoder Beginner Contest 178 - AtCoder

結果は A, B の 2完でした。

考察の流れ

A. Not

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

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

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