今回は簡単だったようで、もっと解かなきゃいけなかったみたいだけど、問題文がちょっと分かりにくかったせいもあって厳しかった。（Eが分かりにくいという声が多いみたいだけど、私にはDの方が分からなかった）
No.1702 count good string
結局読解できなかった。
正しく読み解くと、
・Sの部分列で、"yukicoder", "?ukicoder", "y?kicoder", ..., "yukicode?"のいずれかとなるものが何個あるか？
という問題だった。
一旦分かってしまえば、確かに問題文もそう読めるのだけど、私は「良い部分列のうち Tに含まれる部分列」というのが解釈できなくて止まってしまった。
サンプルの説明は書いて欲しかったなぁ……。と思うけど、コンテスト中に90人くらいに解かれているのだから、自分の読解力がまずいのでしょう。（とはいえ、読解力ってどうすれば鍛えられるか分かりにくいんだよねぇ）
題意が読み取れればDPで解けます。
No.1704 Many Bus Stops (easy)
これは誤読していた。
1.5秒かけて別のバス停に到着したらまたすぐ動き出すものと思い（ただし、同じバス停に残ったものは1秒後に動き出すのかと考えていた。不思議）、行列累乗だとは思ったものの、遷移を書くのが難しいな……と考えていた。
うーん、質問の「iは整数」というのも読んだはずなのに、こんな誤読をするのは良くない。
行列累乗と分かれば、
・バス停xにいるか
・バス停xに向かう途中か
という6状態を考えて行列累乗すればOK。
さらに、バス停A以外を区別する必要はなく、Aとそれ以外にだけ分ければOKと気付けば（これに気付かず、一回MLEなコードを投げてしまった）、hardの方も解ける。
0 件のコメント:
コメントを投稿