■

All Green をDPで解いた

All Green をDPでACしたので、その解説をしたいと思います

DP初心者なので無駄が多いかもしれませんがごめんなさい><

問題概要

 それぞれの問題には、難易度に応じて点数が付けられています。 現在、$1$ 以上 $D$ 以下のそれぞれの整数 $i$ に対して、$100i$ 点を付けられた問題が $p_i$ 問存在します。 これらの $p_1+\dots +p_D$ 問が 問題のすべて。

 ユーザーの総合スコアは、以下の $2$ つの要素の和です。

• 基本スコア: ユーザーが解いた問題すべての配点の合計です。
• コンプリートボーナス: $100i$ 点を付けられた $p_i$ 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス $c_i$ 点を獲得します $(1\le i\le D)$。

 彼の目標は、総合スコアを $G$ 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？

解説

まずはDPテーブル(あってる？)を考えます

僕はdp[i][j](i番目まで見て、合計j個の問題をすでに解いている際における総合スコアの最大値)と定義しました

次に遷移を考えましょう

この問題における状態とは、ある問題を解くか否かの高々2通りです

これをそのままDPの遷移としてあらわしてやればよいです

具体的にDP漸化式を定義すると、(ここでkとはi番目の問題をk個解くという状態を示し、bonusはkがa[i]の時b[i],そのほかでは0として扱うと定義します)

dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+100*(i+1)*k+bonus)

以上の遷移を行い、dp[n][j]>=Gを満たす最小のjを出力すればACを獲得することができます

D<=10 p[i]<=100 であることから十分に間に合います

■

                 AtCoder で水色になるまでの人生

ちょっと前のABCで水色に慣れたので、今更ですが記事を書きます！

かなり緩いです、ごめんなさい

レート推移はこんな感じです～

時々、自分の推移の汚さに嘆くこともあります、、、

人生を振り返る

あんまり自分の人生を振り返る機会ってないので、のんびり振り返ります

【中学】

一切プログラミングの事を知りませんでしたし、知ろうともしてませんでした

ただ学業をしてた

【高専一年春】

C言語という言葉すら知らずに入学した明石高専

まず僕を苦しめたのは友達と会話できないことです

友達が何を言ってるかわからないんですよ

コンパイル？Linux？今なんの話してる？とか思いながら、話を合わせようとするも無理でしたね

【高専一年夏】

友人にAtCoderをやってみないかと言われました

本当にいい友人を持ったと思います

何も知らない僕を誘ってくれて…

当時持ってた知識はifとfor(繰り返せるんや～くらいしかしらないので書けない)

最初はそこまでやる気もなくて楽しみ程度にコンテストに参加してました

【高専一年秋】

この辺から僕は多少変わります(ほんとか？)

僕にAtCoderを進めてくれた友人にカンファレンス的なやつに行こうと誘われて、行ってみました

そこで感じたのは「登壇者の発言してる単語の意味が分かんねえ」ってことです

そこで僕は登壇者が言ってるわけのわからない言葉を全部メモって一個一個Googleに聞いて多少、勉強っぽいことをしました

おかげで今ではプロが話してることは大体わかります()

競プロ関連でも事件(?)が起きます

僕は学業の加減もあり、長い間コンテストに参加してなかったのですが、久しぶりに出たろと思ってABCに出ました

結果は、僕が1完、友人たちは15分とかで3完してました

こんなに差をつけられていたのか、俺よりも後に始めたやつに抜かれてる、しかも1完、、と酷く落ち込んでしまいました

で僕は決めたんです

一回ガチで競プロをやっていつかこいつら全員を抜かしてやると

当時は僕がレート100くらいで、その友人たちは茶色に到達してましたね(多分)

【高専一年冬】

冬ぐらいから結構精進し始めました

初めてC問題をACすることができたのもこの時期だったような気がします

めっちゃ嬉しくて、頑張ってよかったと少し思いました

そして友達にもAtCoderを布教しました

【高専二年(?)春】

またしても事件(?)が

僕が布教した友達が数回しかコンテストに出ていないにもかかわらずC問題を通し、僕は2完みたいなことがありました

自分の無能さに嫌気がさし、でもそこで逆に落ち込まずに燃えたんです

こやつらには絶対に負けないぞと

そしてあえてライバルであるその友人たちとAtCoder頑張ろうぜ見たいなグループを作って一緒に結構精進しました

このころに出会ったのがけんちょ○さんのDPの記事です

DPという未知の世界と触れ合う楽しさ、わくわくを味わうとともに、そのほかの典型アルゴリズムにも興味をもっていろいろ頑張りました

もうひとつモチベーションを保てた原因があって、くちも○とくらさんの存在です

当時、彼は引くぐらい(褒めてます)精進してて、「こんな人いるんだ、、俺もこの人ぐらいやらんと伸びんぞ」みたいな感じでモチベーションを保ててました

【高専二年夏】

ここで人生最大の冷えを経験してしまいます

レート-41

このコンテスト以降、一週間は元気が出ませんでしたね

そして、この後も数週、+=0みたいな状態で、もう僕は水色になれないんだなと思いました

でも突然、ABCで全完できるようになってきて、水色になれました～

みたいな感じです

かなりゆるーーい記事で申し訳ないです

青にむけてまた頑張ります