パナソニックプログラミングコンテスト2020

AtCoder 競プロ

最近まとめてなかったのですが，昨日は酷すぎたので，まとめておきます． パナソニックプログラミングコンテスト2020

C 問題，誤差に関する知識がなさすぎるのに誤差を消そうと頑張って 11WA しました（？） 結局 C 問題は力技で通しました．

久しぶりに茶パフォ取りました．酷すぎます．

D 問題を先に解いておけば良かったです． C 解いた後の脳みそで D 問題を考察していたのがよろしくないです．


A - Kth Term

問題文

コピペして vector に初期値として入れました．

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    vector<int> n = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << n[k-1] << endl;
}



B - Greedy Takahashi

問題文

「サンプルめっちゃ易しいじゃん〜」と H \times W / 2 周辺ということがすぐにわかって調子に乗ったら H = 1 のときと W = 1 のコーナーケースに引っかかって WA 直しました．

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int64 h,w;
    cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1 << endl;
        return 0;
    }
    cout << (h*w+1) / 2 << endl;
}



C - Sqrt Inequality

問題文

予想はしていましたが，誤差で死にました．
どうやって解いたらいいかわかりません．

大きな値のときに誤差が生まれそうだということに気がついたので,
最大公約数で割るという力技で通しました．
大きな互いに素な値が与えられると死にます．

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

typedef long double ld;

int64 gcd(int64 a, int64 b) { return b? gcd(b,a%b):a; }; int64 lcm(int64 a, int64 b) { return a/gcd(a,b)*b; };


int main() {
    int64 a,b,c;
    cin >> a >> b >> c;
    int64 GCD = gcd(a,b);
    GCD = gcd(GCD, c);
    a /= GCD;
    b /= GCD;
    c /= GCD;

    if ( sqrt(a) + sqrt(b) < sqrt(c) ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


この問題はきちんと式変形をすることで整数だけで判定できるらしいです．
自分でやってみると普通に出来ました（最初からやってください）

\sqrt{a} + \sqrt{b} \lt \sqrt{c}
両辺を二乗して (\sqrt{a} + \sqrt{b}) ^ 2 \lt c = a + b + 2\sqrt{ab} \lt c
ここまででも解ける可能性があるけど，念のため全部整数に落とすと，
4ab \lt (c - (a+b)) ^2 で， c - (a+b) がマイナスになるパターンは省く必要があるのでテキトーに条件書くと通るみたいです．

int main() {
    int64 a,b,c;
    cin >> a >> b >> c;

    int64 x = c - a - b;
    if ( x > 0 && 4*a*b < x*x ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



D - String Equivalence

問題文

C で 11 WA した後です．冷静であるはずがありません（？）

N = 3 のときに， 1文字目に b や c が来るのはおかしくて， 2文字目にc が来るのはおかしいなぁと考察していたはずなのに，
実装にしたら頭がバグっていました． こんなかんじ

ちゃんと実装したら結構綺麗に書けました． 1文字目を決めるときは， 'a' + 0 までしかしない．
2文字目を決めるときは， `'a' + 1' までしかしない．

と決めていくと良い感じになりました．

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;
void dfs(string s, const int& t, const int& n, set<string>& ans) {
    if (s.size() == n) {
        ans.insert(s);
        return;
    }

    for (int i=0; i<=t; i++) {
        string ts = s + (char)('a' + i);
        if (i == t)
            dfs(ts, t+1, n, ans);
        else
            dfs(ts, t, n, ans);
    }
}

int main() {
    int n;
    cin >> n;

    set<string> ans;
    dfs("", 0, n, ans);

    for (auto s : ans)
        cout << s << endl;
}



E 問題以降は黄色だったのでまだ見てません．

まとめ

小数は悪