murnana's diary

のんびり書きます。マサカリまってます(震えながら

ABC080 D - Recording

D - Recording

解説動画: youtu.be

テレビ番組を録画したい

  • N個のテレビ番組を録画したい
  • チャンネルはC個
  • i個のテレビ番組は、時刻s~時刻tまで、チャンネルCiで放送される
  • 録画機は、時刻S~時刻Tまで録画したいとすると、S-0.5~Tまでの時間、他のチャンネルの録画をすることができない(同じチャンネルならできる)
  • N個すべてを録画するとき、必要な録画機の最小数は?

解き方

累積和を使う

  1. 配列aを用意する
  2. 変数bを一つ用意する
  3. すべての番組の最を1とする
  4. その番組の終わりに-1とする
  5. a配列を順に追う 1があったらbに+1,-1なら-1を足していく
  6. bの最大値を求める

ほへーって感じです。ほへー。
累積和はアルゴリズムの一つのようです。

paiza.hatenablog.com

ABC080 C - Shopping Streetの復習

C - Shopping Street

解説放送

youtu.be

問題についてざっくりと。

午前、午後合わせて10回の営業がある。
ただし、午前か午後、必ずどちらかに営業しなければならない。

ほかのお店も営業したりしなかったりしていて、他のお店と予定がぶつかると、それぞれどれくらいの利益になるのかを考えつつ、最大の利益が出せるように営業時間を決めるというはなし。

結論。総当たり。

C - Shopping Street写し

結局if(a~)あたりがよくわからぬ…

ABC080 B - Harshad Number の復習

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の復習

A - Parking

AtCoderの解説動画も見つつ。AtCoder Beginner Contest 080 解説放送 - YouTube

簡単に解ける問題。
やることはこれだけ。

  1. プラン1のN*Aを計算する
  2. プラン2のBと比較する
  3. 小さいほうを出力する

何に時間かかったっけかな…?忘れちゃった…


実行時間0msという謎コードがあったのでのぞいてみる。

scanfで入力を受け付け、printfで出力。 比較は…std::min()使っていますね。標準は基本早い子(例外あり)なので使ったほうがいいようだ。 それとも、私の場合は三項演算子がまずかったのだろうか…?多分そんな気がする。

とにかく、悩むところじゃない。


ABC080の反省

2017年12月8日 21:00。
競技プログラミングの世界へようこそ!」の夜。

AtCoder Beginner Contest 080が始まりました。 AtCoder Beginner Contest 080 - AtCoder

結果は惨敗…


続きを読む

競技プログラミングの世界へようこそ! に行ってみた

ladiespp.connpass.com

これです。 割と大学生多いです(´・ω・`) し、社会人だっているはず…

続きを読む

Numpyで、2つのArrayから直積でArrayを作る


発見までの道

長さlengthの2つの1次元配列から、length×2の配列(行列?)を作りたかったので。 イメージ的にはこう。

import numpy
a = numpy.arange(start=0.0,stop=1.0,いくつか)
b = numpy.arange(start=0.0,stop=1.0,いくつか)
# ほにゃほにゃ
x = # [[0.0,0.0],[0.0,1.0],[1.0,0.0],,,] 

さぱらん*1のでコード書いてみた。
Python3です。

ようやっと直積できた

[[ 0. 0. ] [ 0. 0.5] [ 0. 1. ] [ 0.5 0. ] [ 0.5 0.5] [ 0.5 1. ] [ 1. 0. ] [ 1. 0.5] [ 1. 1. ]]が出力されればおk。

片方の配列の長さが違ってもできる。
次元が違ってもできる(ただしconcatenateの第一引数の、一番最初の配列に合わせるようだ)。


参考

*1:テイルズオブベルセリア内でマギルゥというキャラクターがよく使う言葉。さっぱりわからんの略。