なんじゃこりゃー!
続きを読むABC 083の反省
ABC080 D - Recording
解説動画: youtu.be
テレビ番組を録画したい
- N個のテレビ番組を録画したい
- チャンネルはC個
- i個のテレビ番組は、時刻s~時刻tまで、チャンネルCiで放送される
- 録画機は、時刻S~時刻Tまで録画したいとすると、S-0.5~Tまでの時間、他のチャンネルの録画をすることができない(同じチャンネルならできる)
- N個すべてを録画するとき、必要な録画機の最小数は?
解き方
累積和を使う
- 配列aを用意する
- 変数bを一つ用意する
- すべての番組の最を1とする
- その番組の終わりに-1とする
- a配列を順に追う 1があったらbに+1,-1なら-1を足していく
- bの最大値を求める
ほへーって感じです。ほへー。
累積和はアルゴリズムの一つのようです。
ABC080 C - Shopping Streetの復習
解説放送
問題についてざっくりと。
午前、午後合わせて10回の営業がある。
ただし、午前か午後、必ずどちらかに営業しなければならない。
ほかのお店も営業したりしなかったりしていて、他のお店と予定がぶつかると、それぞれどれくらいの利益になるのかを考えつつ、最大の利益が出せるように営業時間を決めるというはなし。
結論。総当たり。
結局if(a~)あたりがよくわからぬ…
ABC080 B - Harshad Number の復習
ハーシャッド数が分からず、ググったはいいが解き方がわからなかった問題。
ハーシャッド数とは
例えば、195 は各位の和が 1 + 9 + 5 = 15 であり、15 は 195 の約数であるので 195 はハーシャッド数である
あ、なんか聞いたことあるような…?
博士の愛した数式だったかな?
解き方の解説
123456を全部足すと、21になる
ということで、まずは全部足す。
足した合計21で元の数123456を割ったあまりがぴったりだと、ハーシャッド数であるといえる。
とりあえず素直に一桁ずつ取り出す
まず、一の位しかない数字(=10未満の数字)はそのまま使える。
他をどうするのか。
さっきの123456を見てみると、実は
12345 = 123456 / 10
6 = 123456 % 10
ということがわかる。
これにより、一番左端の桁の数字を取り出すことができる。
つまり、再起関数を使ってすべての桁の数を取り出し、計算することができる。
文字列にしてしまえ!
JavaScriptだったらそうしていたかな…
ああ、そうすればよかった…