naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 114

12/2(日) 21:00-22:40

いつも通りD→C→B→Aの順で(全完89位)
今回は問題名が全て/75[3456]/だった

D - 756 (400)

  • 75=25*3=15*5=3*5*5 なので、素数p,q,rがあるとして七五数(約数をちょうど75個持つ正の整数)x は以下の4パターンのいずれかで表すことができる
    • x=p^{75-1}
    • x=p^{25-1}q^{3-1}
    • x=p^{15-1}q^{5-1}
    • x=p^{3-1}q^{5-1}r^{5-1}
  • N!を素因数分解したもの(1からNまでを素因数分解したやつを足し込んだもの)を用意
  • 素因数分解したやつの中から素数を1つ2つ3つ選んで(総当たりで大丈夫)、上記の乗数を満たせるものをカウント

→AC 28:14
https://beta.atcoder.jp/contests/abc114/submissions/3704565

C - 755 (300)

  • 桁DP書くべしみたいな誘惑に負けてはいけない
  • 3^9=19683だし、/[753]{1,9}/を全部作って愚直に七五三数チェックしてしまおう

→AC 37:24
https://beta.atcoder.jp/contests/abc114/submissions/3704987

後学のために桁DPでも書いてみた

ABC 114 Cを桁DPでも解いてみた - naoya_t@hatenablog

B - 754 (200)

  • 3連続で取り出しうる文字列(というか整数X)を全部見て\min |X-753| を出す

→AC 42:07
https://beta.atcoder.jp/contests/abc114/submissions/3705140

A - 753 (100)

  • switch文書きました

→AC 42:07
https://beta.atcoder.jp/contests/abc114/submissions/3705216