2015-05-16から1日間の記事一覧
問題 Problem - C - Codeforces 解法 まずl番目の値がtより大きい場合はどうしようもないので-1を返す。 そうでない時は二分探索する。r番目の数まで0にすることのできる必要十分条件は,s[r] C++の場合オーバーフローに注意(全部10^6で抑えられるのでlong lo…
これは面白い問題だなぁ。 問題 No.210 探し物はどこですか? - yukicoder 解法 実際に最適な動きをシミュレーションする。具体的には,・現時点で一番ある確率が高い部屋に探しに行く。今までに部屋iにx回通っていたとすると,その部屋でものを見つける確率は…
見た目から動的計画法だろうと思ったけど出題時は☆2で,「もっと簡単な方法があるのかなぁ」とか悩んでしまった。 問題 No.209 Longest Mountain Subsequence - yukicoder 解法 問題設定がちょっと複雑だが,とりあえずという方から考える。 dp[cur][pre] := (…