Magentor 作問リスト

問題 想定配点 コメント
Simple Math(Returned) 300 簡単な算数枠で作っていたら思っていたよりもペナ率が高かったり、難しかったりしたらしいです ARC-A にありそう
Mean Median Construction 300 序盤のボス問(?)枠　かなり難しそうな見た目をしてたので、飛ばす人が大量に出るだろうと思ったが、意外にもあまり出ない...
衝突予測 300 ★1想定でしたが、場合分けが面倒ということでこの位置に来ました　とても簡潔な別解があるらしいです
A cans -> B cans 400 典型枠です　個数制無しナップサック問題とほぼ同じ
列辞書順列列 500 弱体化前の列辞書順列を提案したところ、難しすぎるということで弱体化されて今のような問題になりました。Rolling Hash をします
Sum Functions Sum 500 一応初作問　主客転倒を頑張ると解けます(畳み込みは不要)
Or Set 500 最初 M \leq 20 を想定していたのですが、 O(NM) で解けるという話があったので制約を強化しました　解法が非常に簡潔です
Range Mex Sum Min 500 数え上げ枠　うまく主客転倒をすれば、最適化パートはかなり容易です
SandGlasses 500 Ants ほぼそのままですが、なぜかあまり解かれていない
列辞書順列 550 作問自体は中一の夏　BITだけで解けます
Line of Light 550 算数　約数包除か添え字gcd畳み込みをします
Cards And Subsequences 600 典型詰め合わせです
Add to Variables 600 O(M) で解けます　シンプルな数え上げ
L to R Graph 600 解法自体は中難易度で見られるアルゴリズムの組み合わせになっています　実装が重い

yukicoder contest 424 開催記

3/29 日に yukicoder にて hirayuu_yc さんと共同 writer のコンテストを開催したので、当日までの流れや各問題の感想を詳しく書こうと思います。

準備

最初、hirayuu_yc さんに共同 writer をしないかと持ち掛けられたので、共同 writer をすることにしました。最初は X の DM 上で原案を出し合う形でしたが、それでは不便なところがあるので、原案がある程度形になってきたあたりから Discord で Writer 作業をすることにしました。

実は原案は10月頃から作っていたのですが、私の方が緑以下コンテストのwriter作業やパ研合宿一日目「Speedrun」のwriter作業で忙しかった影響で、このコンテストの準備が少し疎かになってしまいました。特に、開催当日までパ研合宿があったのはかなり影響が大きかったので、日程は早めに決めましょう。

各問題の感想

A - Simple Math (Returned)

本当はこの問題の前に簡単枠があったのですが、あまり面白くないという理由で没になりました。

解法自体は単純で、筆算のような形であまりを求めることを考えればその値は容易に求めることが出来ます。比較的サンプルが不親切で、単純に 10^{K} - 1 ( K は N を M で割ったあまり) としてしまうとサンプルは通りますが、もちろん WA が出てしまいます。

B - Please Hack Greedy Solution!

珍しく Output Only の課題です。もう少し解かれるだろうと予想していたのですが、あまり解かれていませんでした。構成自体も比較的簡潔です。

C - A cans -> B cans

当時、このような問題の N=1 の場合がTLに流れてきたので、それを改良して現在の形になりました。テストケースがかなり強いので、適当な嘘貪欲はすべて落ちると思います。

解法については、個数制限無しナップサック問題のプログラムを少し改良すれば解くことができます。

D - Nand Nor Matrix

実験ゲーです。私はもう少し難しいだろうと思っていたのですが（ARC力が弱い...）、Tester さんなどの判断によって E と D が入れ替えられました。

ランダムなケースで実験をすると解説の通りに法則を導き出すことができます。類題には これ などがあります。

E - FizzBuzz Letter Counting

適切な解法の判断が必要です。本解では、N の桁数を S としたとき、S 桁未満の整数に対する答えの和と、S 桁の整数に対する答えの和に分けています。S 桁の整数に対する答えを求めるパートでは、余りの扱いに注意する必要があります。

F - L to R Graph

実装が重めです。重要なのは、頂点 S_i から頂点 T_i までの長さと、サイクルの長さであることに注意すると、連結成分ごとにまとめて答えを求めようという発想に至ります。後は、動的計画法などを上手く活用することでこの問題を解くことができます。

G - L to R Graph (Another ver.)

F問題の派生です。頂点 2 が閉路に含まれるかどうかで場合分けが必要ですが、そのどちらでも比較的難しい数え上げや考察が要求されるので、（それぞれのパートはおそらく黄diffくらいだと思われますが）問題全体として見たときにかなり難しくなっています。

サンプルを見るとOEISエスパーが出来そうで、実際サンプルの答えをOEISに入れると数列を発見することができるのですが、それは嘘です。hirayuu_yc さんによると、OEISエスパーを武器にしている人を懲らしめたかったようです。実際、OEISエスパーをしようとして引っかかっている人が散見されました。

まとめ

かなり準備がギリギリになってしまいましたが、全体を通して Clar は一件も来ていませんでした。いつかは ARC のセットを作ってみたいものです。（橙になるどころか2000あったレートが1800まで落ちていますが...）

緑以下コンテストEx - E Moving up

https://yukicoder.me/problems/no/2573

O(W^2 \log^2{W}) で解くことが可能です。

想定解法ではそれぞれの駒からそれぞれのマスへ少なくとも W^2 本の辺を貼る必要があるので、これを削減することを考えます。

f(i,j) をコマ i が (1,j) へ移動するのに必要な最小のコストとします。

f(i,j) は j について傾きが -1,0,1 と変化する区分線形関数となっています。よって、この問題は頂点 S,T,A_1,A_2,\dots,A_W,B_1,B_2,\dots,B_W からなり、以下のように辺が貼られているグラフの S から T への最小費用流に帰着されます。

  • 頂点 S から頂点 A_i への容量 1 , コスト x_i-1 の辺
  • 頂点 B_i から頂点 T への容量 1 , コスト 0 の辺
  • 頂点 B_i から頂点 B_{i+1} への容量 \infty , コスト 1 の辺
  • 頂点 B_{i+1} から頂点 B_{i} への容量 \infty , コスト 1 の辺
  • 頂点 A_i から頂点 B_j への容量 1 , コスト 0 の辺 ( j はコマ i が右上か左上への移動のみで (1,j) に到達できるようなものとする )

このままでは辺数が O(W^2) になりますが、5 行目の j として考えられるものが区間の形になっていることに注目すれば、区間に辺を貼るテクによって辺数が O(W \log W) となるので、計算量 O(W^2 \log^2{W}) でこの問題を解けました。