ABC178の感想

先ほどABC178を解いたので、その感想を書きます。

A問題は0と1を反転させるだけなので、非常に簡単でした。boolで取得して反転させたものを出力して終わりです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
int main()
{
 bool x;
 cin >> x;
 
 cout << !x << endl;
 return 0;
}

B問題は掛け算の最大値を求める問題。

-10^9<=a<=b<=10^9
-10^9<=c<=d<=10^9
a<=x<=b
c<=y<=d

のときに、x*yの最大値を求める問題。どんな感じで場合分けをしようかなと考えていましたが、結局のところ答えになり得る候補としては、各閉区間の端点の組み合わせの4種類しか存在しません。そのため、4つ全部計算してその最大値を取りました。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;

int main()
{
 vector<ll> a(4);
 rep(i,4) cin >> a[i];
 
 vector<ll> pro;
 rep(i,2)rep(j,2) pro.emplace_back(a[i]*a[j+2]);
 
 ll ans = LLONG_MIN;
 rep(i,4) ans = max(ans, pro[i]);
 cout << ans << endl;
}

ただし、1回目はLLONG_MINのところを0にしてたので、ペナルティをもらいました。小さいところに注意したいです。

C問題は0と9を含む順列の個数を求める問題。この問題は結局解けませんでした。高校生の数Bを思い出して、一般項を求めてからプログラムに起こすという方針で行こうとしました。

0~9で構成されるN項の重複順列のうち、0と9を両方含むものの数を求めればよいので、

全パターン 　－　条件を満たさないもの

として、条件を満たさないものは

0も9も含まない・・・１
0は含むが9は含まない・・・２
9は含むが0は含まない・・・３

の3パターン存在します。これを一般化すると、

10^N - (8^N + 2 * Σ N_C_i * 8^(N-i) )　　　　（iは1からNまで)

となります。N=2と3で検算したので大丈夫だと思いますが、間違っていたらすみません。

その後、これをプログラムに起こすことができませんでした。組み合わせのCの計算量が重いので、Cを含む条件２、３に関する漸化式として、条件2および3のi番目の項 をCi+1とすると

Ci+1 = Ci * (N-i) / (2 * 8) 

ってできそうだなーと考えましたが、答えが合いませんでした。

後は、Eの問題設定が非常に簡単だったので、通ればいいなーという気持ちで実装したらTLEでした。当然ですね。

他の人の解答状況を見るにいつもよりは難しかったと思いますが、悔しい結果でした。