コンテストURL: https://yukicoder.me/contests/587
久しぶりの単著コンテストです！ 一昨年から他２件単著コンテスト予定をしておりましたが、どちらもtesterさん方がお忙しくしばらく開催の見込みがなかったので何かできないかなと考えていたところです。
去年はそれら２件は一旦置いておいて別のコンテストを計画すれば良いかもしれないと思い小数誤差コンテストを開催させていただいたのですが、それはそれで新たにtesterさんを募集する必要があって界隈のリソースをお譲りしていただきすぎていると感じているため同じ手はあまり繰り返したくありません。
しかし今年は通常コンテストが少なく、このコンテストを開こうと思った時点ではコンテスト予定もスカスカだったため、こういう時期こそコンテスト開催の形で何かしら界隈に恩返しをしたいという気持ちも強いです。
そこでコンテスト概要ページにも記載した通り、コンテストがないくらいならtesterさんなしのコンテストを開催した方が喜んでもらえるのではと思いアンケートを取ってみたところ、歓迎してくれる人もいらっしゃることが分かったので今回のtesterさんなしコンテスト開催に踏み切ったわけです。
すると準備中だった単著コンテストのうちリアクティブコンテストもtester作業が終わったのですが、さすがにコンテスト予定を急に入れ替えるのはtesterさん方のご迷惑となるのでtesterさんなしコンテストとそちらを差し替えることはせず、testerさんありの単著コンテストは別の日程で開催することにいたしました。
testerなしとなると当然ミスが生じる確率も跳ね上がるので、もちろん何度も何度もチェックをし直しました。残念ながら結局B問題で$N$を$n$と書き間違える誤植があり反省をしておりますが、他には特に大きな混乱もなく無事に終わったと思います。
何が起こるか分からないtesterなしコンテストは当日までハラハラが止まらず心臓に悪かったですが、またコンテスト予定に空きがあったらtesterさんなしのコンテスト予定を入れるかもしれません。もちろん今回同様、同日程に他に希望者がいればお譲りしますのでその場合は遠慮なくお声掛けください。
ただ筆者の実力でのtesterさんなしコンテスト開催は参加者に余計な不安を与えてしまうと思いますので、今のところなるべくtesterさんありのコンテストを実施していきたいと思っています。testerさんを募集する際は何卒ご協力いただけますと幸いです。
それでは参加者の方々、皆様ありがとうございました！
A: No.3488 距離の公理 ★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3488 tester：なし | ||
| こちらは3年前に作った問題です。ようやく日の目を見せることができました。 まずは純然たる実装問題で、★1.5のupsolveを重ねた人でもそこそこ苦戦するボリュームだと思います。 ★2以上を主戦場とする人にはどう実装を素早くこなすかが鍵となると思いますが、実装ボリュームに対して手を抜ける箇所が少ないので、複数の言語を習得している場合は実装の軽い言語で望むのが手っ取り早いかもしれません。 参考までに、writer解の提出コードはc++で819[bytes]、Python3で257[bytes]です。 | ||
B: No.3489 あみだくじ作り ★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3489 tester：なし | ||
| こちらも3年前に作った問題で、未出題だった作問ストックの中では最古の問題です。 ★2典型である、順列を隣接項のswapでソートする問題です。基本的には貪欲に大きいものを端に寄せていくだけでよいですが、上下を逆にしないようにサンプルを合わせていきましょう。 この手の問題をある程度こなしていれば実装はあまり迷わないと思いますが、不慣れだと頭がこんがらがってくるかもしれません。 なお競技プログラミング初挑戦でも数学の知識があれば解くことができます。この問題は線形代数や群論で対称群を学ぶ際の頻出問題です。 | ||
C: No.3490 最高経路問題 ★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3490 tester：なし | ||
| 2年前に作った問題です。結構最近作ったつもりだったのですが月日が経つのは早いものです。 序盤から実装がやや重めの問題が続いています。ここで★2.5典型の、max/minで計算する経路長の最小化/最大化問題です。 この手の問題は二分探索＋連結性判定で解くことはできるのですが、当然実装が重くなります。 一方でダイクストラ法やクラスカル法をライブラリー化していればほとんど貼るだけにできるので、実装速度に大幅な差が出ます。 適切にライブラリーを持っておくことで重実装問題との連戦を緩和できる、というところがポイントな問題配置にしてみました。 | ||
D: No.3491 右結合的総乗問題 ★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3491 tester：なし | ||
| こちらは2年半前に作った問題です。元々はタイトルに合った代数寄りの問題文でしたが、コンテスト開催に向けて取り組みやすいように操作ベースの問題文に直してみました。それでもかなり数学寄りな問題文なので、慣れていない人には読みにくかったかもしれません。 ABCまでは考察より実装や典型アルゴリズムが問われる問題となっていたので、ここで一息ついて考察問題です。 集合が少しずつ大きくなっていって最大でどうなるか、という問題なので何かしらの方法で集合を管理してシミュレーションすれば良いことが分かります。 集合を更新していくステップは愚直に処理すると演算$1$回ごとに最悪$MN$のオーダーで時間が掛かるので、集合の更新が止まるまでは最悪$MN^2$のオーダーで時間がかかります。 そこで「直近で新しく追加された要素だけに注目」して集合の更新をしていけばよく、そのためには具体的にどういうシミュレーションをすればよいか、を考えてもらう問題です。 | ||
E: No.3492 区間冪乗加算一点取得問題 ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3492 tester：なし | ||
| こちらは3年前に作った問題です。データ構造が好きなので色々なクエリ処理問題を作ったのですが、なかなか出題する機会がなく埃被ってしまっていました。 改めて見てみるとかなり典型色が強い問題ですが、そもそも3年前の時点では★3を解いた経験に乏しかったので、典型に寄るのも仕方ないですよね。 ちょっとスパイスとなってくれるかもしれないのが、やや数学要素の強い合成数modである点です。二項係数の計算方法で詰まってしまった人は良い機会なので復習しておきましょう。合成数modを問われる頻度は他のwriterさんだとそこまで高くないですが、筆者のコンテストでは定期的に出題させていただいていますのでご贔屓にお願いいたします。 | ||
F: No.3493 等比数列の和の素因数 ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3493 tester：なし | ||
| こちらも3年前に作った問題で、未出題だった作問ストックの中ではB問題の次に古い問題です。 競技プログラミング典型である等比数列の和の公式を素因数に絡めて考察する問題です。★3ではフェルマーの小定理も頻出なので、フェルマーの小定理そのものの理解が問うように原始根周りの議論を思い出す必要があるようにしました。 考察さえできてしまえば実装はシンプルです。コンテスト全体の中で一番実装の軽い問題ですね。 | ||
G: No.3494 一点挿入区間和取得 ★★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3494 tester：なし | ||
| こちらは2年前に作った問題です。★3.5を作るのは今も昔も苦手で、当時も「どうすれば（作問ストックが少なめな）★3.5にできるかな？」と考えながら作った問題でした。何せ★3.5を解いた経験がほとんどないわけですから、苦労するのも当然です。数学寄りの高難易度にすると★4以上になってしまうため、★3.5のバランス感覚が難しいです。 さて、本問は少し変わった更新クエリを処理する問題です。配列の特定の位置に要素を挿入していく問題は★3以下でたまに問われますが、それらは主に挿入位置が先頭・末尾（stackで処理可能）や初期状態の成分の現在位置の前後（双方向リストのイテレータの配列やstackの配列などで処理可能）だと思います。 一方で本問は挿入位置が現在の配列のランダムアクセスで指定されるので、少し工夫が必要です。双方向リストのイテレータの配列やstackの配列だけでは直接処理できないので、データ構造を工夫して構築していきましょう。 | ||
H: No.3495 ２変数半二項展開 ★★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3495 tester：なし | ||
| こちらも3年前に作った問題です。3年半前に作って3年前に出題した[等差二項展開](https://yukicoder.me/problems/no/2396)の類題で、考察は近いですが必要なライブラリーが若干異なります。両方に適用可能なライブラリーを持っている人には大差ないかもしれません。 整数論の考察と、代数構造を扱うライブラリー整備の両方が問うボス問題でした。お楽しみいただければ幸いです。 | ||