なぜ高橋君は母親に数列を上げようとしたの…
一体その数列で何をするの…
なんかそういう本ないだろうか…
続きを読む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だったらそうしていたかな…
ああ、そうすればよかった…
ABC080 A-Parkingの復習
AtCoderの解説動画も見つつ。AtCoder Beginner Contest 080 解説放送 - YouTube
簡単に解ける問題。
やることはこれだけ。
- プラン1のN*Aを計算する
- プラン2のBと比較する
- 小さいほうを出力する
何に時間かかったっけかな…？忘れちゃった…
実行時間0msという謎コードがあったのでのぞいてみる。
scanfで入力を受け付け、printfで出力。 比較は…std::min()使っていますね。標準は基本早い子(例外あり)なので使ったほうがいいようだ。 それとも、私の場合は三項演算子がまずかったのだろうか…？多分そんな気がする。
とにかく、悩むところじゃない。
ABC080の反省
2017年12月8日 21:00。
「競技プログラミングの世界へようこそ！」の夜。
AtCoder Beginner Contest 080が始まりました。 AtCoder Beginner Contest 080 - AtCoder
結果は惨敗…
続きを読む
