AC時間は開始14分ぐらい。長さNの数列S、整数Kがある。Sのうち、すべての要素の値の積がK以下となるような、連続した部分列の最長の長さを求める問題。Sに0が含まれる場合、解はNとなる。Sに0が含まれ、かつK>0の場合、要素の積がK以下となるような配列sと、その積mを作成する。数を一つ取得するたびにmを再計算する。m>Kの間、先頭の要素をpopしてmを再計算する。この際、sの長さの最大値を保存しておく。だいたいの方針は上の通り。再計算に関して、はじめ、数の出入りがあるたびにすべての要素について再計算していてTLEした。考えて、出入りする数に関してだけ計算すれば良いと気づき変更した。変更の際、出入りする要素が0のとき、mがnilのときに注意する必要があった。(2REした)尺取り法なるアルゴリズムがあって、それに似たようなものになったと思う。AC時間は開始65分ぐらい。ナップサック問題3つの条件があって、それらの条件に応じて適切なアルゴリズムを用いてナップサック問題を解く問題。ナップサック問題の解法は蟻本を写経したものが手元にあったので、それをコピペしたらいけるやろとか思ってたらそんな甘くなかった。条件によってアルゴリズムが変わるのは面白いと思った。さいごにできれば全完したかったができなかったので悔しい。初心者でやることがたくさんあるのはわかっているので(蟻本、チーター本、ABCの過去問など)、練習を重ねて上達していきたい。余談だが、サンプルケースをコピペするのがめんどくさいと思いrubyでそのへんやってくれるatcoder_greedyなるgemを作ったんだが、本番でうまくサンプルを取得してくれなかった。»プロフィールid:brookbach情報理工学科の大学生です。(1)はてなブログをはじめよう!brookbachさんは、はてなブログを使っています。あなたもはてなブログをはじめてみませんか?はてなブログをはじめる(無料)はてなブログとは鉄分は大事。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。