AtCoder Beginner Contest 169 (A~B)解説
ABC169が 2020/05/31 21:00 - 22:40の期間で行われました！
皆さん、お疲れ様でした！
今回の問題、正直なところこれは知識がかなり必要だったのかなと思っています。
Writerさんには新たな知識を与えていただいたということで感謝しています。ありがとうございます。
そして、B.C問題が解けないからといって 順位表以外の内容をTwitterで言及している方が見られたようです。 正直これはWriterさんに失礼だと思いますし、解いている方に対しても失礼だと思います。unratedになる可能性がある行為ですのでやめましょう。
問題について振り返っていきます。
A問題 - A - Multiplication 1
https://atcoder.jp/contests/abc169/tasks/abc169_a
もはや簡単。を出力するだけの簡単なお仕事 世界一簡単な問題 FA10秒 私は19秒
コード : https://atcoder.jp/contests/abc169/submissions/13774212
B問題 B - Multiplication 2
問題概要:
個の整数で構成された数列
がある。
この時、を出力せよ。
ただし を超える場合は"-1"を出力せよ。
私が最初に提出したコードがこれです。
https://atcoder.jp/contests/abc169/submissions/13781425
判定はWAでした。このコード、いくつかの点で計算量を削減できたのにそれを無視している点があります。さて、どこでしょうか。
では正解(ACした)のコードです。
https://atcoder.jp/contests/abc169/submissions/13812984
画像について誤りがあったので変更しました。 (22:50)
いくつか計算量を削減できるコツがあるので説明します。
ｺﾂ1. 降順ソート
これはTLEになってからいろいろ考えたのですが、大きい方から貪欲的にかけていけば掛ける回数を減らせるのではないかと考えました。よって、A.sort()→A.reverse()ではじめに降順ソート(大きい順にソート)しました。
ｺﾂ2. 0があった場合
数列に0があった場合、どのみち解は0です。ただし、愚直に0が出るまでかけていくと、計算量が増えてしまうので駄目になります。そのため、0が数列に出現していた場合、その時点で0を出力しその後の処理をしないようにしました。
ｺﾂ3. 10^18で処理終了
最後に、乗算し続けた値が、より大きくなったら処理をやめて"-1"を出力しました。これは単純に計算量を減らすためです。
このように、計算量を減らすテクニックは競プロの問題でも頻出です。例えば、かの有名な「Otoshidama」問題であったり、私が先日GCC002のE問題で出題した問題では、全探索を行っても実行時間制限を超過してしまうので、変数を1つ固定するなどして、計算量を減らすテクニックを利用すればACすることができます。
GCC002 - E - Combination
https://www.hackerrank.com/contests/gcc002/challenges/combin
Otoshidama(ABC085)
https://atcoder.jp/contests/abc085/tasks/abc085_c
大量データを処理する現代にとって、高速で動くアルゴリズムは重要ですから 今回のコンテストのみならず なるべく高速に動作するようにプログラムをコーディングするのが大切だと思っています。
以上で、B問題の解説を終わります。
C問題
最終的にはこのようなコードでWAでした。
https://atcoder.jp/contests/abc169/submissions/13857616
(誤差をなるべくなくすために小数の桁数を無理やり多くしましたが、駄目だったようです)
以上、ABC169 (A~B)の解説でした。今回は教育的な問題が多くて良かったと思います。
