Dまで四完。
No.2354 Poor Sight in Winter
一応自力でAC。
二分探索＋ダイクストラでいけるんじゃないか？ とは問題を見てすぐ思った。
ただ、a→bのルートに明かりを配置したとき、同時に別のc→dというルートがいけるようになることがある。だから、正当性が怪しい気がして実装せず考え込んでしまった。
コンテスト後、「とはいえ、a→bのルートに明かりをx個配置したとき同時にa→cもいけるようになったとしたら、a→cもx個でいけるようになるな」と思い、やや正当性に自信が持てなかったものの実装したら（REやTLEを経て）ACした。
なお、解説を見ると「明らかに，同じ明かりを二度使うことは最適ではありません．同じ明かりを二度使う場合，1 回目に使用してから 2 回目に使用するまでの間を省略できるからです」と書いており、それはそうか、となった。
No.2355 Unhappy Back Dance
自力AC。
角度が同じものを列挙すれば良いとは思ったが、三乗かかる気がして悩んだ。
ただ冷静になると、それほど工夫は必要なく、「一点を固定し他の全ての点に対して角度を求めたものをdictに入れておく」で二乗でいけた。
No.2356 Back Door Tour in Four Seasons
ちらっと解説を見たけど大体自力でAC。
扉の順番を決めれば、そう進むときの場合の数は求められる。それを使って総和を求めるという方針。
解説ではΣ計算を使っているけれど、DPの気持ちで考えた。
・DP[扉]＝その扉に至るときの場合の数（それが夏の扉なら、どこかの春の扉→ここ、という感じ。その手前の季節の扉までの行き先を指定する）
として、ある夏の扉を使っていく場合の数を考えたとき、春の扉たちの場合の数の和がその値になる。……ということは、春夏秋冬それぞれについて和を取って良い、ということになる。
なお、扉の総数を求めるとき、modで割ってしまいWAを出した。ベキ乗する値にmodを取ってはダメ！
0 件のコメント:
コメントを投稿