ARC017 A, B, C 考察

ARC017 A 素数、コンテスト、素数

N が素数かを判定する。 2 から N 未満の数で割り切れたら素数ではない。

https://atcoder.jp/contests/arc017/submissions/15522517

ARC017 B 解像度が低い。

N * K の 2 重ループにしてしまうと K <= N <= 3 * 10^5 なので間に合わない。

真に大きいものが K 個続いているかを確認したいだけなので連続する 2 つの要素が真に大きい関係になっていれば連続している個数を増やしそうでなければ 0 にする。連続している個数が K 個以上になったら答えの個数に加算する。これでだいたいは求まる。だいたいと書いたのは K = 1 のケースは比較さえされないのでよくわからないということ。今回は K = 1 のときは N 個ある扱いらしい (1WA) 。

https://atcoder.jp/contests/arc017/submissions/15521384

ARC017 C 無駄なものが嫌いな人

N <= 32 。使う or 使わない 2 択が N 個のすべての組み合わせ (2 ^ N) を列挙するには 32 は大きすぎる。そこで半分ずつにして処理する。いわゆる「半分全列挙」をする。半分ずつ全列挙して組み合わせる際に高速化できれば間に合う。 2 ^ 16 = 65536 個の BTreeMap を 2 つ用意する。足してちょうど X になる要素がもうひとつの BTreeMap にあるかを調べれば良い。この探索は BTreeMap なので O(logN) 。 2^(N/2) * log(2^(N/2)) 。ごちゃごちゃしてよく分からないけど 6 * 10^5 くらいなので間に合う。

https://atcoder.jp/contests/arc017/submissions/15521499

昨日だけど『平成狸合戦ぽんぽこ』を観た。気晴らしじゃ。

openapi-generator の nodejs-express-server を試したんだけどレスポンスの型がまったく考慮されていなくて微妙……。未使用なのになぜか含まれている npm:openapi-sampler で「自分でつくれ」ということなのだと思ったのでそのとおりにした。強引に services/*.js を書き換えて自動生成したサンプルのレスポンスを返せるようにした。

なんだか腰をやってしまった気がする。痛い。へんなひねりかたをしたんだろうな。