コンテストへのリンク
No.994 ばらばらコイン
一見難しいけど実は簡単、という問題。このタイプは結構得意にしているつもりなんだけど、これは手間取ってしまった。
No.995 タピオカオイシクナーレ
まず、求める答えは各タピオカの美味しさの期待値の総和です（これが期待値の線形性っていうやつのはず）。
あとは、漸化式を立て行列累乗する問題。
……と思ったら、解説のwriter解は行列累乗を使ってなくて驚いた。
No.996 Phnom Penh
解説AC。
基本的には、phnomomomomomみたいなやつのomの数を数えればいいのだけど、omの間にeやhが含まれていると、操作の途中でそれらが消えて、操作が行えるようになる、というところが難しい。
ただ、解説にあるように「最適な操作」が定まっていることに気付くと、実際にそれを数回やってみることで解決する。邪魔だったhやeが消えれば、omの数を数える問題になる。
・何回か操作をすると定常状態に落ち着く
から、そこまでシミュレーションしてから考える、という方針で上手くいくことは結構あるはず。
No.997 Jumping Kangaroo
tester解と同じ行列累乗でACしました。
形式的冪級数を使う方法が解説に書いてありますね。なるほど、こういうときに使うのですね。
0 件のコメント:
コメントを投稿