ABの二完でした。解説を聞いてしまえば、C～Eのどれも解けてもおかしくなかった問題に思えるのだけど、実際には一つも解けていないので厳しい。
（自分にとっての）難易度はE<D<Cだった気もするけど、どれに時間を割くべきか判断するのは難しいので、解ける問題を増やすしかなさそう。
C - Sequence Scores
公式解説放送を見てAC。
解説を聞いても難しく感じた……。
本番中は、DPをメインに考えていたものの、各マスにおける寄与数みたいなことも考えた。けれど、まずN個の区間に分けた場合の総和からペナルティ分を引くという発想にはなれなかった。
そもそも、
・同じ数字が二回現れていて
・その間の数字が全てそれより大きい
ときにペナルティ、という数え方が思いつけていない。
数列Aのf(A)を求めるとき、あるindexで+1される条件……みたいなことは結構考えていて、その際、「+1されないとき」を考えた方が上手くいきそう、とは思ったのだが、その条件を簡単に言い表すことができなかったのが敗因か。
DPを念頭に置いていたとしても、このあたりは考えなくてはいけない内容なので、単純に考察が足りていなかったと思う。だが、この考察は結構難しく思える。
D - Moving Pieces on Line
公式解説放送を見てAC。
本番では、面倒そうだからと回避したけど、解法は意外とシンプルでした。
ただ、T（赤と青の端点）の各点について、左が赤なのか青なのか、で場合分けが必要そうに見える（コンテスト中は、そこの考察が大変で時間がかかりそうだから避けた）ので、そこから抜け出すのが難しそう。
また、その部分が考察できても、DPすると思えたかも自信がないので、本番中こっちを頑張ったとして解けたか、というと厳しいかも。
ただ、地道な考察の積み重ねでACに結び付けられる問題に思えたので、考える価値はあった気がする。
AC人数を見てDを考えるのははじめから避けてしまったけど、それはもったいなかった。（とはいえ、じゃあ何を参考にすれば良いかというと悩ましい。問題文を読んだ時点でいけそう、と思えたら解いてたと思うので）
E - Paper Cutting 2
公式解説放送を見てAC。
これはシンプルですね。
ある直線での切断が行われる確率は？ を求めようと思えば、解法に至るのは難しくない。
四次元のDPテーブルを持つDPが見えるので、FFTなどを用いてそれを高速化していこう（という方針でも本当は解けるらしいけど）、などという方針に惑わされないことが重要だった気がする。
Cと似た方針だけど、こっちの方がCより簡単な気がする。もっとちゃんと考えるべきだったか。
F - Permutation Division
公式解説放送を見てAC。
解説放送を聞くと、自然な考察の積み重ねで解けているように感じてしまったため、本当に難しいのがどこなのか今一つ理解できていない。
もうちょっと考えてから解説を聞くべきだったか。
0 件のコメント:
コメントを投稿