コンテストURL: https://yukicoder.me/contests/500
せっかくのオムニバスコンなのに応募締め切りギリギリの時点で３枠しか埋まっていなかったので、ストックから５問提供して参戦させていただきました。今回は２問testerをしている関係で剰余絡みの基本的なDPが★2に出ることが分かっていたので、★1.5を主戦場にしている人達が★2に挑戦する足掛かりとなるように剰余演算子の仕様を問う★1と、合同式の理解（計算の最後に剰余を取るのではなく計算の途中に剰余を取る）を問う★1.5を出題させていただきました。全体的に整数問題が多めになりましたね。
コンテスト開始前の懸念はD問題（★2：繰り上がりなし十進和）とG問題（★2.5：グッドスタイン数列？）です。どちらもそこそこ重実装で、D問題は上級者ほど高度な考察に流れて逆に苦戦しそうな予感、G問題はうまく検索等を駆使して既知の事実に辿り着き考察の道標を得られるかが心配、というところです。ただ今回は普段のコンテストより難易度勾配が緩やかなので、どちらもそれなりに時間を割けるはず、と期待して本番に臨みました。
結果はご覧の通り、D問題は特に事故もなくといった感じですがG問題は難易度反転が置きてしまいましたね・・。もう少しヒントをわかりやすくする必要がありました。反省です。
そろそろ単独コンも開きたいですが、オムニバスコンはオムニバスコンでwriter陣の共同防衛といった感じが面白くていいですね。足を引っ張らないようにしなきゃ！ 共同コンもまた開催してみたいです。writer陣同士でtester作業したり原案を相談したりできるのは楽しいですからね。
それでは参加者の皆様、testerさん方、オムニバスの他のwriterさん方、皆様ありがとうございました！
A: No.2781 A%B問題 ★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2781 tester：Takaさん | ||
| お使いの言語の剰余演算子を完全に理解しているか、または理解している制約内に即座に帰着できるかを問う問題です。 プログラミングを覚えたての人はサンプルを丁寧に処理して剰余演算子の振る舞いを覚えていただければと思います。 | ||
B: No.2782 メルセンヌ数総乗 ★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2782 tester：Takaさん | ||
| 剰余を学んだら、合同式の性質を活かして四則演算を処理してもらいます。 上限付きの整数型を扱う言語をお使いの人に、forループで乗算を計算しながら（計算の最後ではなく）途中で剰余を取っていくことの正当性を学んでいただくための問題です。一方で多倍長整数をお使いの人にはその利点を実感しやすい問題だと思います。 なお解説にあるように、バングの定理を用いれば高速に処理することが可能です。 | ||
D: No.2784 繰り上がりなし十進和 ★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2784 tester：hamamuさん | ||
| ここからは一筋縄ではいかない問題です。まず操作の見た目から、上級者ほど線形代数っぽい解法に食いつきやすいだろうなと思います。 しかしながらこれは★2の問題なので、線形代数は不要です。よく見ると手続き全体が小さい整数でパラメータ付けできるので、愚直に全探索をしましょう。 背景は解説に書いた通りで、より一般の有限アーベル群の部分集合が生成する部分群を同様の方法で決定することが可能です。 | ||
E: No.2785 四乗足す四の末尾の０ ★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2785 tester：MZKiさん | ||
| ４次式の計算問題に見せかけて、上限付きの整数ではオーバーフローします。そこで多倍長整数に切り替えれば何とかなるかというと、素数判定問題が残っています。更に高速素因数分解を持ち出す人もいるとは思いますが、上限付きの整数でオーバーフローするということが逆にヒントです。 オーバーフローしないように割り算結果が計算できるはずなので、与えられた４次式が整数係数多項式として因数分解できるというわけです。整数係数多項式として因数分解できる整数係数多項式に整数を代入した値が非自明な素因数分解を持つか否かは高速に判定できますね。 多項式環の演算が代入と整合的であること（代入が環準同型であること）を意識するための問題でした。準同型は２種類の代数構造を結ぶ重要な概念で、片方の演算が分かりやすい／計算しやすい時はそちらに帰着させる議論が代数学の典型です。 | ||
G: No.2787 グッドスタイン数列？ ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2787 tester：testestestさん, googol_S0さん | ||
| （難易度投票結果を考慮して難易度を★3に変更いたしました） グッドスタイン数列の亜種です。グッドスタイン数列ほどではありませんが、それでも尋常でない停止ステップ数となります。 ０から停止性証明をするのはさすがに難しいと思いますが、タイトルなどにグッドスタイン数列というキーワードを与えているため検索である程度の戦略に到達できることを作問時点で確認しています。オリジナルのグッドスタイン数列を真似て多項式なり位取り記法なりに変換して解きましょう。 基本的に停止性問題は、操作の分かりやすい対象に゙翻訳して処理するのがおすすめです。 | ||