yukicoder contest 311のwriterでした。
単独コンテスト開催は2回目となります。前回の単独コンテストを開催したときの記事はこちらです。
各問題の感想
No.1656 Recuperation
簡単枠です。
一度精神を病むと回復には時間がかかるというメッセージを込めて作りました (たぶん)。
最初は $1\le A,B\le 10 ^ 9$ でしたが、C++のコンパイラの最適化により愚直が通るとテスターさんから指摘があったので、はじめから愚直が通る制約に変えました。
No.1657 Sum is Prime (Easy Version)
等差数列の和を計算します。B-A が 0 か 1 であることがポイントです。Easy Version はエラトステネスの篩で解けます。
ARC-A にありそうと思っていました。ARC112A を見て、等差数列の和は一瞬で計算できないと戦うのは大変なんだなと思ったりもしました。
No.1658 Product / Sum
シンプルな問題文でお気に入りです。
最初は積と和が等しくなるような数列について調べていて、それをちょっと発展させてこの問題が生まれました。
積は $K(K+1)(K+N-1) (\le 10 ^ {18})$ 以下になると予想しましたが、証明に失敗したのでジャッジは多倍長整数対応になりました。コンテスト後に数名の方から証明を頂きました。ありがとうございます。
No.1659 Product of Divisors
素因数に関する典型的な問題です。
N,K が具体的な値になっている問題をどこかの数学コンテストで見たような気がします。それをもとに作問しました。
ABC にも似た問題があります。ただしその問題とは違って K の値が大きいので、二項係数を用いるときは適切な方法を用いる必要があります。
No.1660 Matrix Exponentiation
行列の問題に見せかけてグラフの問題です。
この問題が生まれた経緯を書きます。競プロ始めたての頃、LIS の問題に出会いました。当時は LIS の求め方を知らなかったので、「$A_i\le A_j$ のとき $(i,j)$ 成分を 1 にした行列を考えて、行列累乗を計算すれば求められる？」といったことを考えていました (勿論間に合いません)。このときを思い出し、逆手にとって「$A ^ m$ が零行列となるような $m$ を LIS で求められる？」という問題を考えました。$A_i\le A_j$ かつ $A_j\le A_k$ ならば $A_i\le A_k$ なので、はじめはこれに対応した制約が付いていました。のちにこの制約は外せることに気づき、現在の問題ができました。
グラフ問題のテストケース作りは少し大変です。一直線になる場合や、長いサイクルになる場合を用意しました。再帰を使うコードはスタックオーバーフローを起こす可能性があるので注意しましょう (実際何も工夫していない Kotlin はすぐスタックオーバーフローします)。
★2.5 から ★3 に変更しました。
No.1661 Sum is Prime (Hard Version)
$\pi(x)$ を高速に計算する方法を前に Twitter で見かけていたので、この問題に使えることに気づきました。
埋め込みでも解けるようです。
★3.5 にしては多く解かれることは想定していました。
No.1662 (ox) Alternative
今回のボス問です。タイトルの示す通り、元ネタはAGCの問題です。
最初はシングルテストケースで、想定解の計算量は O(D) でしたが、テスターさんが閉じた式で表せることを発見したのでマルチテストケースにしました。テスターさんからのアドバイスで問題が進化するのは初めてだったので嬉しかったです。
おわりに
参加してくださった皆様ありがとうございました！
そして、運営の yuki さん、テスターの harurun さん、LayCurse さん、sak さん、Kazun さん、stoq さん、全体テスターの ygussany さん、ありがとうございました！
次はアドベントコンテストに問題を出そうと思っています。
