ganmo::cout

競技プログラミング始めました

「みんなのプロコン 2019」

3完早解きで青パフォ(1743, highest)だった！
…が、あともう少しでDが解けそうだったのとFが逆詐称だったので手を出しておけばよかった、で不完全燃焼だった。

A - Anti-Adjacency (100点)

問題: A - Anti-Adjacency
これは２つのペア＋端１つを選ぶに等しいので{\lfloor \frac{N+1}{2} \rfloor \ge K}を満たしている時に"YES"、そうでなければ"NO"を出力してAC。O(1)。

拙解 (C++): Submission #4204392 - Yahoo Programming Contest 2019

B - Path (200点)

問題: B - Path
4頂点3辺の無向グラフを考えればいい。次数が0か3の点が存在するとオイラー路が構成できないので、全部の次数が１か２なら"YES"、そうでないところがあれば"NO"を出力してAC。O(1)。

拙解 (C++): Submission #4206692 - Yahoo Programming Contest 2019

C - When I hit pocket... (400点)

問題: C - When I hit my pocket...
A枚以上ビスケットがあるとき、2回の操作で「2回ポケットを叩いてビスケット2枚を手に入れる」か「ビスケットA枚→1円→ビスケットB枚と交換してビスケットB-A枚を手に入れる」ができるので、得なほうをできなくなるまでやるのが最適。すると、最初にA-1回ポケットを叩き、{\lfloor \frac{K-(A-1)}{2} \rfloor}回だけ\max\{2,B-A\}枚手に入れ、最後に1回残っていればポケットを叩くと手に入るビスケットの枚数が最大になる。これを出力してAC。O(1)。

拙解 (C++): Submission #4209454 - Yahoo Programming Contest 2019

D - Ears (600点)

問題: D - Ears
全体の区間[0,L]を、(通らない区間,偶数回通る区間,奇数回通る区間,偶数回通る区間,通らない区間)という具合に分ける。これは、往復1回で通る回数が２回増えるので、各整数の間を通るのは「０回か、奇数回か、偶数回か」しか区別されず、加えて、

　　　　┌―――――発　　　　　着←――┐
　　　　└―――――――――――――――┘
００００偶偶偶偶偶偶偶奇奇奇奇奇偶偶偶偶偶００００００
のように通ればよいため。よって、(通らない区間,偶数回通る区間,奇数回通る区間,偶数回通る区間,通らない区間)をそれぞれ状態(0,1,2,3,4)として、
\displaystyle dp[i][s] := 地点i-0.5まで見て状態sのときに必要な操作回数の最小値
というようにして、状態の数字が小さくなるように遷移することはないのを念頭にDPすればAC。状態の数がO(1)、地点がO(L)なので、O(L)。

拙解 (C++, 終了後に解説AC): Submission #4218259 - Yahoo Programming Contest 2019

まとめ

DのDPをdp[l,r]:=lからrまで散歩するときに必要な操作回数の最小値としてしまってO(L^3)になり、セグ木を疑うもモノイドじゃないしなーと思って１時間半椅子を暖めたのは痛い。EDPCでも「状態遷移があったらDPするだけ」な問題を散々やったしそもそもDP = DAGな感覚が染みついていなかった。
でも最近WA連打みたいなことをせずにちゃんと考えるようにしてからあまり極端に冷えなくなったのでちゃんと考えてやるのは続けていこうと思った（小並感）