yukicoder で noya2 さんと合同でコンテストを開きました.
yukicoder.me
全体Tester にはまた Nachia さんに来ていただきました. 二回も全体Tester を引き受けていただき本当に感謝しています!!!!
F は特に難しかったので Tester に kaichou243 さんに来ていただきました!!! ありがとうございます!!!!
前回のコンテストは以下です。
yukicoder.me
難易度は ★2.0 - ★2.5 - ★3.5 - ★3.5 - ★4.5 - ★5.0 の 2時間40分 (ジャッジつまりで10分延長!) でした. 前回よりも難しめのセットになっております.
Writer / Tester を除いて, 参加者は 119 人、各問題の正解者は
[A] 105人 / 107 ★2.0
[B] 67人 / 76 ★2.5
[C] 36人 / 47 ★3.5
[D] 26人 / 32 ★3.5
[E] 2人 / 10 ★4.5
[F] 1人 / 4 ★5.0
でした.
FA 者は以下をご覧ください!
yukicoder.me
この記事では, 問題の裏話や, 人々がどんな感じで解いてたかを作問者が覗き見た感じ(?)を書いています.
A - Find Zero (★2.0)
No.2252 Find Zero - yukicoder
最初の問題でいきなり
インタラクティブです。質問の回数を見ればやるべきことを
エスパーすることができますが、それよりも問題文を感覚的に理解するのが辛かったかもしれません。
質問する対象を
エスパーすることができれば、あとは数学的に処理しますが、落ち着いて
と書けば, ならもう
が分かるはずです。
ちなみに, どんなに質問しても
を復元することはできません. たとえば,
,
は質問で全く同じ挙動を示します. ただし, どんな
でも
の位置によって挙動が同じになるわけではなく, たとえば
と
では異なります. 前者は
, 後者は
です.
また, この問題は本質的に
と同型な群の
単位元を特定する問題ですが, 一般の有限アーベル群(さらに一般の有限群)でも同じ
アルゴリズムで群の
単位元を特定することができます. でも, 有限アーベル群の構造の特定には
回が必要だと思っています. ここで, 有限アーベル群の構造は
有限アーベル群の構造定理 - Wikipedia によって
巡回群の直積で表されることが示されています. 有限アーベル群の構造を
回の質問で特定するのはかなりキツイです. 多分 ★4.5 くらいはあるんじゃないでしょうか.
【コンテスト中】
AC率はそこそこ高かったです. 解答の '!' を忘れてて WA を出した人も多いように感じました.
B - Ignore Subtle Differences (★2.5)
No.2253 Ignore Subtle Differences - yukicoder
珍しい形式であるところの
インタラクティブの A に引き続き, また珍しい形式であるところの Output Only が B に来ました. デカめの三角形で, 辺の長さの二乗の max - min がちょうど 1 になるものを求める問題です.
解説で
の整数解を求めるとあったのですが, 実は
Generic two integer variable equation solver というサイトを使えば解を満たす漸化式が出てきます.
上のサイトは競プロでは役に立つことは少ないですが,
Project Euler というコンピュータを使って数学問題を解くサイト(先生!
Project Euler は競プロに含まれますか?)では様々な問題で役に立ちます. お気に入り登録してもいいかも?
解説の他に別解もあるので紹介します.
がほぼ正三角形をなすことを考えます. これは
二等辺三角形なので
か
が成り立てばいいですね.
の値がだいたい
なので, そこらへんを調べます. 三角形のデカさが指定されてるので,
を調べると
が引っかかります. これはギリギリ問題文の制限をクリアしてるので ACです.
【コンテスト中】
だいたい想定解と上に書いた解法が半々くらいでした. WA も意外に多かったです.
C - Reverse Only (★3.5)
No.2254 Reverse Only - yukicoder
これは操作問題です.
ならギャグ,
なら ARC156-A と同じ設定です.
問題としては, 主に解法の部分で結構 ARC にありそうだなと思いました. まず,
と
の多重集合が異なれば(サンプル 3)ダメです. 操作できない場合もあります(サンプル 2)が, 最初から一致してれば ok です.
「
なら全部できる」というのが問題の本質です.(これすごい) これは実験で分かりましたが, 証明は悩みました.
のときは巡回 or 反転して巡回が全部網羅されます. これを判定するのはローリングハッシュですよね!(KMP, Z-algorithm でもできるらしいです)ここのパートは
ABC150 - F のアプローチに似ています.
完全に実装を詰めたときの判定の実装は青 Diff もいかないのではと思ってます.
たまに ARC で WA を連発させるような問題があります. この問題もその種だと思っていて, これがこの問題が ARC らしいなと思った理由です. この種の問題への対応として,
自明なものを最初に場合分けしておくというのがしばしば有効です. この種の問題で WA が連発する原因として, 「自明なものを最初に外さないでおくと, あとあとコーナーケースになっている」ということがあるからです. 今回の場合, 自明なものは「最初から一致している」「
と
の多重集合が異なる」場合で、それぞれ
の場合、
の場合にコーナーケースになります.
最初は ★3.0 でしたが, ぼくが ★3.5 に上げました. どのくらいの人が解いてくれるかな?
【コンテスト中】
WAは(もちろん?)結構多かったです. 判定パートで詰まってそうな人もいた気もします.
D - Determinant Sum (★3.5)
No.2255 Determinant Sum - yukicoder
行列式の問題を錬成してたら生まれました. 最初は
にしてて「最強のギャグ問が出来たww」と思って笑ってました.(
の場合は全部
になります)
のときを考えたら結構いい感じになったので yukicoder に書き始めました. 特に「
行列式の問題なのに最終的には
行列式のライブラリすらいらない」という結果は気に入ってます.
最初は調子に乗って ★4.5 にしてましたがさすがに ★4.0 になり, 全体Testerの Nachia さんの助言で ★3.5 になりました. 爆速で解いていてすごかったです.
【コンテスト中】
結構みんな
はできてました. やはり
が難しいですね. 結構 WA が多かったです.
ちょっと解法が分からないものもありました.(が, 雰囲気はつかみました)
結構おもったより通してる人が多かったです. やっぱり難易度的には ★3.5 で妥当だったと思います.
E - Step by Step (★4.5)
No.2256 Step by Step - yukicoder
パズドラの落としを意識して作った問題らしいです.
はほぼ自明で存在して,
には存在しないのは秒で分かりましたが,
がマジで謎でした.
正直しばらくは
でさえ構成できなくて, 「これ
によってあったりなかったりするのではないか」とか「多分
には無いギャグだ!」とかも考えてました.
実際は
を
で割った余りで場合分けできて, うまく全部構成できました. すごいです.
WAをいっぱい出しながらなんとか突破しました.
考えてた時間は合計で数時間です. 複雑な知識とかは不要ですが, 時間がかなりかかると思います. 最初は ★4.0 になってましたが, Nachia さんの助言で adhoc が強いのと作業量が多いのを加味して ★4.5 になりました.
【コンテスト中】
'-1' だけで出している人がたくさんいて爆笑しました. さすがに疑いますよね.
ペナありでも 5 分くらいならぼくも一度やると思います.
を
で割った余りで場合分けするアプローチもありますが, 実際は
で割った余りで場合分けするのが楽なのがすごいと思いました.
1時間40分後に AC 者が出ました!!!!ありがとうございます!!!!
思ったより通した人は少なかったです.
F - Swim and Sleep (★5.0)
No.2257 Swim and Sleep - yukicoder
最初の問題では
だけが与えられていて
でした. 問題を見たとき, これは「
の約数で約数系包除だな!」と思って
エスパーで解きましたが, 当たり前に WA です.
その後進展がありませんでした. なぜなら
で出現する
URRD
ULLD
RDUR
LDUL
が意味不明で絶望していたからです. 問題の特徴付けをなんとか行ったあと, noyaさんの誘導に甘えながらも証明はできませんでした. 後になって解説を読んで「これは… 正しいけどヤバイ」という謎の感情になりました.
問題が新しくなり, 定数個入力ではなくなってしまいました…!!!難易度は 1.4 倍くらいになった感触があります. 数え上げは丁寧丁寧に実装しましたが 300 行以上書いたこともあって当然 WA を連発しました.
時間制限はかなり余裕だと思います.
Tester の kaichou243さんも苦戦してそうでした.
これを2時間半以内に解ける人はもはや人間ではありません.
【コンテスト中】
サンプルの説明が間違っていました. 何回も確認したはずが, ここは油断していましたね…
コンテスト終了 15 分前に AC 者が出ました!!!!!!!よかった~~~~~~!!!ありがとうございます!!!