自分の理解力のなさと、どこにも吐き捨てることのできない思いを
チラ裏として、ここに放ちます、駄文で失礼します。読むだけ時間の無駄かと思います。
AtCoder ABC 263 B 問題を解こうとしました。
https://atcoder.jp/contests/abc263/tasks/abc263_b
問題文を読んで、さっぱり理解ができなかったため、
ページ下部の入力サンプルをみて動きを確認しようとしたところ
以下のような形式
N
1 2 ... N-1
の二つしかありませんでした。(N=3,10のパターンの2種、以下入力例）
入力例1
3
1 2
入力例2
10
1 2 3 4 5 6 7 8 9
この二つの例なら N-1 でいいじゃんと思ったらWrong Answer
解説見ても、解説動画見ても,
解くには動的計画法を使うんだ！！としか書かれていませんが
問題をかみ砕くところから解説までの話が飛躍しすぎていると感じます。
とりあえずいいサンプルがないかを探した結果、Qiita解説記事(@sano192)に
7
1 1 3 3 5 5
とあり、そういう入力もあるんだと思う一方で、どうやって思いつくのと思いました。
こういった問題を初見でかみ砕くのは無理ではと思い、最初は質問にでも乗せようかと思いましたが、期待される回答が来る気がしなかったのでチラ裏としてここに記載しました。
この問題が解けている人は初見で問題文を読み解くことができるのかが疑問です。
単純に問題のタイトルがAncestor:祖先であり、祖先をたどる問題は基本的に動的計画法で解く というふんわりした概念があるから理解できているだけなのじゃないかと思っていますが、どうなんですかね。
X.comでも同じように問題文理解できない人が少しは散見されましたので、過去の先輩方に同情を馳せつつ、
本日の、この問題に費やした２時間は無駄だったなと思ってこの記事を閉じたいと思います。（問題解く5分 解説読む1時間半 記事書く15分ぐらい）
要するに何が言いたいのか
AtCoder ABC 263 B - Ancestor のサンプル例どうにかならなかったのか