コンテストURL: https://yukicoder.me/contests/511
また久しぶりのオムニバスコンです。オムニバスコンで応募締め切りギリギリまで8問埋まっていない時は難易度勾配的にちょうど良さそうな問題を出題応募するようにしています。
今回はは★1.5,★2,★2.5,★3,★3,★3,★3.5の7問が応募されていたので難易度勾配的には★2.5がちょうど良いかなと思い、D問題の「2集合間距離」を応募させていただきました。
オムニバスコンは複数のwriterが特に難易度の示し合わせもなく出題するので難易度反転が心配なところですが、D問題は運良く難易度反転もなく無事に終わって安心しました。B問題の★2は(★2.5でも要求されない)$\mathbb{F}_2$線形基底を問う問題だったのでC,Dよりyukicoder problems上のDifficultyが上がってしまったようですが、慣れてしまえば$\mathbb{F}_2$線形基底自体は★2.5典型アルゴリズムと比較してそんなに難しくないのでこの調子で線形代数が★2~2.5でも出題される頻度が上がっていけばそのうち★2典型になるかもしれませんね(そうなることをちょっと期待)。
最近はこの手の「ここ1・2年はこの難易度帯で問われなかったようなアルゴリズムが問われる」というパターンが★1~2.5で増えているように感じます(逆に★3では滅多になく、yukicoder contest 414 F問題の Initial Motionで度肝を抜かれたのがいい思い出です)。いわゆるインフレというやつですね。
インフレに対して、作問者としてどう向き合うべきか(1・2年前の過去問と逸脱しないように難易度をつけるべきか、ここ最近のインフレに乗って厳しく難易度をつけるべきか)は結構悩んでいるところです。どちらも長所短所ありますものね。今のところはなるべく過去問に合わせようという結論に落ち着いていますが、そうするならそうするでコンテストでの主観的なインフレ体験が知らない間に自身の難易度評価に影響を与えすぎてブレていないかが心配なところです。
そういう不安もあり、近いうちに客観的な難易度統計を自分で作ってみてそれを参考にして作問していこうかなという気持ちが高まってきています。公開もする予定なので、作問や考察に役立ててくださると嬉しいです。
それでは参加者の皆様、testerさん方、オムニバスの他のwriterさん方、皆様ありがとうございました!
D: No.2897 2集合間距離 ★★☆ | ||
---|---|---|
問題リンク:https://yukicoder.me/problems/no/2897 tester:binapさん | ||
$\min_{(x,y) \in S} \min_{(z,w) \in T} |x-z|+|y-w|$という$2$重の$\min$計算を問うシンプルな問題です。このままだと解きにくそうですが、問題文に記載されている通りグリッド上での距離という意味付けがあるので幅優先探索が使えそう、ということに気付けるかどうかが鍵です。 動的計画法でも解くことができます。むしろ幅優先探索による距離計算は動的計画法そのものですね。 |