Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

いもす法

AtCoder Beginner Contest 060 D - Simple Knapsack

Problem Statement You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi. You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W. …

srm705 SuperUserDo

Problem Statement Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies…

累積和とってソートしてBluteForce AtCoder Regular Contest 035 B - アットコーダー王国のコンテスト事情

問題 arc035.contest.atcoder.jp note ペナルティの小さい順にソートして小さい順にペナルティをうけていけばよい。 コード

いもす法 累積和 AtCoder Regular Contest 048 B - AtCoderでじゃんけんを

Problem arc048.contest.atcoder.jp note あらかじめあるレーティングの人が何人いるのかの累積和と、あるレーティングである手をとるプレイヤーが何人いるかを記録しておく。 そうすると、それぞれの勝敗が次のようにO(1)でもとまる。 int win = dp[players…

いもす法を二回する AtCoder Regular Contest 045 B - ドキドキデート大作戦高橋君

問題 arc045.contest.atcoder.jp note まず累積和を使って、担当が1人しかいない掃除場所を探し出す。 その後、担当が1人しかいない場所を1、それよりも多い掃除場所を0として累積和をとればO(1)で任意の掃除の区間をサボれるかわかる code

いもす法 AtCoder Beginner Contest 017 C - ハイスコア

問題 abc017.contest.atcoder.jp note 累積和を用いて、ある宝石を選ぶことになった際のスコアの合計を求める。すべての宝石をゲットする場合得られる総合点から、ある宝石を選ぶ場合のスコアの最小値が答え。

いもす法 AtCoder Beginner Contest 001 D - 感雨時刻の整理

問題 以下略 abc001.contest.atcoder.jp note 文字列の扱いがめんどくさいだけ。雨がふっている時間を管理する配列をいもす法をつかって保持してやればいい。おしまい。 いもす法の解説は http://imoz.jp/algorithms/imos_method.html とかがわかりやすい。 …