AtCoder Beginner Contest 162 (感想&反省)後日談
AtCoder Beginner Contest 162が先週日曜日の21:00-22:40に開催されました。
皆さん、お疲れ様でしたー。
結果から申し上げますと3完でした。(D以降が解ける気がしなくて萎えてましたorz)
パフォーマンス ・レーティング変化
コンテスト成績証
| ユーザ名 | Rute |
|---|---|
| コンテスト名 | AtCoder Beginner Contest 162 |
| 順位 | 5450th / 10666 |
| パフォーマンス | 614 |
| レーティング | 440 → 459 (+19) |
というわけでほぼ中央値みたいな順位でしたね()
A問題
https://atcoder.jp/contests/abc162/tasks/abc162_a
様々な解法が考えられます。
を、文字列
と考え、S[0],S[1],S[2]に
が現れれば"Yes"と出力、そうでなければ"No"と出力しましょう。
コード: https://atcoder.jp/contests/abc162/submissions/11787793
B問題
https://atcoder.jp/contests/abc162/tasks/abc162_b
(1,N)の区間で変数iを用いて以下のループを回します：(ans = 0とします)
もしiが3または5で割り切れるなら ans には何も加算しない
そうでなければans にiを加算する。
これにより、時間計算量で処理が可能です。
コード: https://atcoder.jp/contests/abc162/submissions/11791945
C問題
https://atcoder.jp/contests/abc162/tasks/abc162_c
ん...全探索か これはであり、制約
の範囲では最大でも
回だからPythonで間に合うな。
試しにコードテストに投げてみるか
コードテスト大混雑！！
コードテストしてから1分経過しても終わる見込みがない！！(
unratedを覚悟したが、「この現象により、コンテストがUnratedになることは、今のところありません。」ということからあることを思いつく。
コードテストが混雑してるならその時間利用して本気で全列挙してみるか。
ということで、やってみた！！
これでの制約上の全ての答えを出すことが出来ました。
あとはこのリストのK-1番目の要素を出力してしまいましょう！
計算量 驚愕の !!
解法です！(あまり類が無いと思います)
C問題、リストでO(1)で提出 ルンルン数みたいに制約が少なかったのでこの方法でも一応は解けます
— _ℝ ute_ (@rute_not_route) April 12, 2020
提出 #11822785 - AtCoder Beginner Contest 162 https://t.co/w7KBffTPI4#atcoder
ちなみに、後々調べてみると の解法では
Python3ではTLEになるものの、PyPy3ではACになることが判明。
あのときPython3で同様のコードを提出していたらペナルティを与えられたということです()
ちなみに、Python3とPyPyの違いについて、分かりやすくまとめてあると思ったページを以下に掲載しておきます。
https://qiita.com/OKCH3COOH/items/f0c5c4681bc30dddf7f4
D問題
スルー。
E問題
最初、おそらく計算量的に間に合わないことから、Double Factorialのように、何か計算をして出力をすることを思いつきました。
すると、以下のような数列が出来ました。(それぞれのN,Kに対してgcdを計算しました)
(Nを固定して、Kを変化させたときのgcdの総和の数列)
N = 2: 3,5,9,17,33,65 階差: 2+4+8+16+32
N = 3: 6,12,30,84,246,732 階差: 6+18+54+162+486
N = 4: 10,24,76,276,1060,4164 階差:14,52,200,784,3104
N = 2, N = 3のとき、階差が等比数列であると思ったのですが、N = 4の場合なぜか当てはまらず。
N = 5のときもあてはまらず。
結果、残り5分まで考えたものの、解の一般項が思いつかずここで撤退しました。
以上、ABC162の感想・反省などでした。
次回のABCではレーティング500・Highestを目指します！
