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

AtCoder Other Rated Contests

A - Kth Term


こんな問題でも本番だと結構あたふたしてしまいます

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> V = { 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 << V.at(K - 1) << "\n";
}

ためしに配列の初期化をせずKから答えを求められないかなと
数列の意味をググってみましたが頭がおかしくなって死にました

B - Bishop


一度飛ばしてC問題に行って追い返されて開始40分でACしました…
幅1のケースも紙に書いて「あ、さてはこれだな～～」と気付いたのですが
交互に塗り分けて「いや問題ないな…」とかなっていました。問題しかない

#include <bits/stdc++.h>
using namespace std;

int main() {
  long H, W;
  cin >> H >> W;
  if (H == 1 || W == 1) return cout << 1 << "\n", 0;
  cout << ((H * W % 2) ? H * W / 2 + 1 : H * W / 2) << "\n";
}

今回の件から得るべき教訓は
下限入力時問題がないかもっと慎重に考えるということ…

C - Sqrt Inequality


ぱっと見 sqrt(A) + sqrt(B) < sqrt(C) すれば良さそうです
しかし常識的に考えてここでそのような問題が出るでしょうか？
前回ABCのDで安直なWAは出さないと誓ったばかりです

…

f:id:ninoi:20200321141937p:plain

ヨシ！

さて、自分では式変形など出来ないので(雑魚)
Wolfram Alphaで変形させてみたり
適当に誤差の補正を試みたりしましたがダメでした

ちなみに誤差の補正についてはyukicoderのお陰で雰囲気は知っていました

というわけで「平方根 誤差」などでググっていると
sqrtl() なる標準ライブラリの存在を知りました
Wolfram Alphaで変形させた式で sqrtl() を使うとなんか通りました

#include <bits/stdc++.h>
using namespace std;

int main() {
  long A, B, C;
  cin >> A >> B >> C;
  cout << ((sqrtl(A * B) * 2 + A + B < C) ? "Yes" : "No") << "\n";
}

引数が long double なら sqrt() でも
long double で返してくれるのでどっちでもいいようです

解説PDFのなぜεが10の-14乗かですが
long doubleの有効桁数が20桁程度
今回は制約上整数部が5桁を超えることはないので
20桁 - 5桁 で10の-15乗でギリギリちょうど良い補正ができるよう
10の-13乗だと補正しすぎで結果がおかしくなる
10の-16乗だと有効桁数を超えてしまい意味がない
と理解していますが違うかも。奥が深すぎる…

D - String Equivalence


例えば N = 5 のときは
5進数でカウンターを回して
aaaaaに各桁足してあげればいいななどと考えましたが
N = 10のとき確実に死…と悩んでいたら終わってしまいました

サンプルを見ているときにbit全探索的なものが頭をよぎって
終始それに引きずられてしまいました
とはいえDFSに思い至っても書けなさそう

こちらの方の提出が宇宙一解かりやすかったので参考にしました
atcoder.jp

#include <bits/stdc++.h>
using namespace std;

int N;

void dfs(string s) {
  if (s.size() == N) {
    cout << s << "\n";
    return;
  }
  char mx = *max_element(s.begin(), s.end());
  for (char c = 'a'; c <= mx + 1; c++) dfs(s + c);
}

int main() {
  cin >> N;
  dfs("a");
}

char mx を *max_element で探す発想は無かったです。すごい
こんなの本番で書けるようになりたい



おしまい