radikoのタイムフリーを保存する方法

先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイムフリーの保存機能を削除していたことに気づきました。

ループバック機能を使えば、再生しながら保存することは可能なのだがそれだと番組の放送時間と同じだけ時間がかかってしまいます。

他にいいソフトが無いか探してみたのですが、いまいちだったので結局自分でスクリプトを組ことにしました。

スクリプトを組むにあたって、radikoの保存手順を調べてみました。

環境

OS: Mac OS High Sierra
必要なソフト:swftools、ffmpeg (Homebrewより導入)

事前準備

myplayer-release.swfのダウンロード

認証のための事前準備としてswfファイルをダウンロードする

$ curl -O http://radiko.jp/apps/js/flash/myplayer-release.swf

swfファイルから画像ファイルを取り出す

認証にキーとなる画像ファイルをswfextractで取り出す

$ swfextract myplayer-release.swf -b 12 -o authkey.png
$ ls authkey.png
authkey.png

実行

認証1

認証1のURLにアクセスし、HTTPのレスポンスヘッダーから以下の3つの値を取得する

・X-Radiko-AuthToken
・X-Radiko-KeyLength
・X-Radiko-KeyOffset

$ curl 'https://radiko.jp/v2/api/auth1_fms' \
> -XPOST \
> -H 'Content-Type: application/x-www-form-urlencoded' \
> -H 'Referer: http://radiko.jp/' \
> -H 'Pragma: no-cache' \
> -H 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
> -H 'X-Radiko-Device: pc' \
> -H 'X-Radiko-App-Version: 4.0.0' \
> -H 'X-Radiko-User: test-stream' \
> -H 'X-Radiko-App: pc_ts' \
> --data $'\r\n'
X-Radiko-AppType=pc
X-Radiko-AppType2=pc
X-Radiko-AuthToken=AJReLqXV-Oo4ymYpgRlhow
X-Radiko-AuthWait=0
X-Radiko-Delay=15
X-Radiko-KeyLength=16
X-Radiko-KeyOffset=121394

please send a part of key

事前準備でダウンロードしたキーとなる画像ファイルから、X-Radiko-KeyOffsetがオフセット、X-Radiko-KeyLengthが長さとなるデータを抽出する。

UNIXのddコマンドを使って抽出する。なお、抽出したデータはBase64で文字列に変換する。

$ dd if=authkey.png ibs=1 skip=121394 count=16 | base64
16+0 records in
0+1 records out
16 bytes transferred in 0.000669 secs (23916 bytes/sec)
kwMYHYGpTwcgn8OlMjBjyQ==

「kwMYHYGpTwcgn8OlMjBjyQ==」が認証2で使うParticalkeyとなる

認証2

認証2のURLに対して、AuthTokenとParticalkeyをPOSTする

curl 'https://radiko.jp/v2/api/auth2_fms' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
-H 'X-Radiko-Device: pc' \
-H 'X-Radiko-Authtoken: AJReLqXV-Oo4ymYpgRlhow' \
-H 'X-Radiko-App-Version: 4.0.0' \
-H 'X-Radiko-User: test-stream' \
-H 'X-Radiko-Partialkey: kwMYHYGpTwcgn8OlMjBjyQ==' \
-H 'X-Radiko-App: pc_ts'

JP13,東京都,tokyo Japan

応答として地域の情報が帰ってくると認証は成功。

音声の保存

プレイリスト取得用のURL(https://radiko.jp/v2/api/ts/playlist.m3u8)に対して、クエリとして放送局IDと開始、終了時間を指定してするとプレイリストを取得できます。

なお、lというクエリには15を指定するらしいのですが、意味は不明です。

放送局IDについてはググると出てくると思います。

これをffmpegの引数として渡すことで、音声の保存が可能。

ffmpeg \
> -content_type 'application/x-www-form-urlencoded' \
> -headers 'Referer: http://radiko.jp/' \
> -headers 'Pragma: no-cache' \
> -headers 'X-Radiko-AuthToken: AJReLqXV-Oo4ymYpgRlhow' \
-user_agent 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
> -i 'https://radiko.jp/v2/api/ts/playlist.m3u8?station_id=LFR&l=15&ft=20180518010000&to=20180518030000' \
> -vn -acodec copy -bsf aac_adtstoasc out.m4a

iTunes等で聴けるように、ffmpegのオプションでm4a形式で保存するようにしています。

まとめ

以上の手順によってradikoのタイムフリーを短時間で保存することが出来ます。

なお、最初にログイン処理を挟めばエリアフリーも対応可能です。

エリアフリーの場合はこちら。

radikoのエリアフリーを保存する方法
以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。 基本的な手順は同じですが、異なるのは最初...

AtCoder BC097 D: Equals

問題

https://abc097.contest.atcoder.jp/tasks/arc097_b

解法

最初、貪欲に操作をシミュレートして解こうと思ったのですが、組み合わせが果てしなくあることに気づき早々に断念。

例題の解き方を眺めているうちに、各操作のグルーピングがポイントであることに気づきました。

例えば、例題2の場合、

3 2
3 2 1
1 2
2 3

(1,2)と(2,3)は2で繋がってます。このような場合、p1、p2、p3については何回か操作を繰り返すことで任意の並び順に変えることが出来ます。

(xi, yi)のグルーピングについては、Union Findのアルゴリズムを使うことで求められます。

グルーピングを行った後、piがiと同じグループに入っているればpi=iとすることが出来るので、その数を数えることで解けます。

実装

class Node
    attr_accessor :parent, :rank
  
    def initialize(n)
      @parent = n
      @rank = 0
    end
  end
  
class UnionFindTree
  def initialize(n)
    @nodes = (0..n).to_a.map { |i| Node.new(i) }
  end

  def find(x)
    return x if @nodes[x].parent == x

    return @nodes[x].parent = find(@nodes[x].parent)
  end

  def unite(a, b)
    a = find(a)
    b = find(b)
    return if a == b

    if @nodes[a].rank < @nodes[b].rank
      @nodes[a].parent = b
    else
      @nodes[b].parent = a
      @nodes[a].rank += 1 if @nodes[a].rank == @nodes[b].rank
    end
  end
 
  def same?(a, b)
    find(a) == find(b)
  end
  
  def parents
    @nodes.map(&:parent)
  end
end
  
n,m = gets.chomp.split.map(&:to_i)
p = gets.chomp.split.map(&:to_i)
tree = UnionFindTree.new(n)
m.times do
  x, y = gets.chomp.split.map(&:to_i)
  tree.unite(x,y)
end

ans = 0
for i in 1..n
    ans += 1 if tree.same?(i, p[i-1])
end
puts ans

Union Findの実装については、以下を参考にさせていただきました。

[Ruby] UnionFind木の実装

こういう定番のアルゴリズムって、事前に用意して置いた方が良いですね。


AtCoder BC097 C: K-th Substring

問題

https://abc097.contest.atcoder.jp/tasks/abc097_c

解法

最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点?って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列挙してしまえば良いことに気づきました。

計算量としては、Kが5だったとしても、長さ1、2、3、4、5の部分文字列を求めるだけであり、各部分文字列を求める計算量はO(N)なので、十分間に合います。

実装

s = gets.chomp.split("")
k = gets.chomp.to_i

a = []
1.upto(k) do |i|
  s.each_cons(i) {|ary| a << ary.join}
end

puts a.sort.uniq[k-1]

AtCoder BC097 B: Exponential

問題

https://abc097.contest.atcoder.jp/tasks/abc097_b

解法

bpがX以下になる組み合わせについて考えます。

これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N2)で求めることが出来ます。

ただし、pについては計算結果がXを超えた時点で以降は打ち切ることが出来ます。

このようにして求めた冪乗のリストの内、X以下で最大のものを求めることで解けます。

実装

a = []
for i in 1..1000
    for j in 2..1000
        m = i ** j
        break if m > 1000
        a << m
    end
end
x = gets.chomp.to_i

b = a.sort.uniq.select{|v| v <= x}
puts b[-1]

AtCoder GC023 B: Find Symmetries

問題

https://agc023.contest.atcoder.jp/tasks/agc023_b

解法

まず、初期状態で「よい盤面」なものについて考える。

例えば、N=3の場合、以下のような盤面が「よい盤面」である。

a b c
b d e
c e f

これを右方向に1、下方向に1ずらすと

f c e
c a b
e b d

となり、これも「よい盤面」となる。さらに右方向に1、下方向に1ずらしても同じである。

つまり、「よい盤面」を横方向と縦方向に同じだけずらしたものは同様に「よい盤面」となる。

よって、整数A、Bの組み合わせのうち、Bを0に固定し、Aのみ0〜N-1に変えて「よい盤面」になる数を数えて、その結果をN倍すれば解となる。

計算量は「よい状態」かどうかのチェックにO(N2)かかるため、全体ではO(N3)となるが、Nは最大300なので一応間に合う。

実装

n = gets.chomp.to_i
s = []
n.times do
    s << gets.chomp
end

st = s.transpose

ans = 0
n.times do
    ans += 1 if s == st
    n.times {|i| st[i].rotate!}
    s.rotate!
end
ans *= n

puts ans

AtCoder GC023 A: Zero-Sum Ranges

問題

https://agc023.contest.atcoder.jp/tasks/agc023_a

解法

最初に問題を見て、これ本当に200点?って思うくらい悩んだ。

とりあえず、累積和をとってみる。

例えば、サイズ4の数列:{a1 a2 a3 a4}の累積和を考える。

S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
S4 = a1 + a2 + a3 + a4

この時、部分数列の和は累積和の差で求められるのがポイント。

例えば、{a3 a4} は、S4 – S2 で求めることが出来る。
つまり、{a3 a4} の和が0になるのは、S4 – S2 = 0、つまり、S4 = S2 な場合といえる。

よって、累積和のうち、等しいものの組み合わせを数え上げることになる。

入力例1:{1 3 -4 2 2 -2}の場合、累積和は{1 4 0 2 4 2}なので、等しいものは、2が2個と4が2個となり、

2C2 + 2C2

となる。さらに、累積和自体が0の場合はそれ単独でも組み合わせの一つとなり得る。

この場合、累積和の先頭に0を追加してやり、{0 1 4 0 2 4 2}とすることで、同様に扱うことが出来る。

2C2 + 2C2 + 2C2

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

s = [0]
for i in 0..(n-1)
    s[i+1] = a[i] + s[i]
end

h = Hash.new(0)

s.each do |v|
    h[v] += 1
end

ans = 0
h.each do |k, v|
    next if v == 1
    ans += v * (v-1) / 2
end
puts ans

GCJ 2017 Qualification Round B: Tidy Numbers

問題

与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。

例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。

https://code.google.com/codejam/contest/3264486/dashboard#s=p1

方針

Nから順にデクリメントして条件にあうかチェック、、、みたいな実装だとSmallはクリアできてもlargeは時間がかかりすぎてしまう。

よって、単なる数字の並びの規則性という観点でロジックを考えると、

・左から数字をチェックしていき、降順になる箇所が見つかった場合、前の数字を一つ小さくし、以降の数字を全て9に変更する
 例:14548 -> 14499
・上記操作によりさらに一つ前の数字との大小関係が変わる場合は、同様の処理をもう一つ前の数字についても行う。これを繰り返す。
 例:14438 -> 14399 -> 13999

となる。

実装

gets
n = 1
STDIN.each_line do |line|
    digits =  line.chomp.chars.map(&:to_i)
    prev = digits[0]
    for i in 1..(digits.size-1)
        if digits[i-1] > digits[i] then
            digits[i] = 9
            digits[i-1] -= 1
            j = i - 1
            while(j > 0) do
                if digits[j-1] > digits[j] then
                    digits[j] = 9
                    digits[j-1] -= 1
                end
                j -= 1
            end

            for j in (i+1)..(digits.size-1)
                digits[j] = 9
            end
            break
        end
    end
    printf "Case #%d: ", n
    digits.select{|c| c > 0}.each  do |c|
        print c
    end
    printf "\n"
    n += 1
end

AtCoder RC093 C: Traveling Plan

問題

https://arc093.contest.atcoder.jp/tasks/arc093_a

解法

観光スポットに行かないケースを毎回計算していると、O(n^2)の計算量になってしまいます。

そこで以下のように考えます。

観光地が5カ所の場合、全ての観光地に行くケースの総距離は、

$$総距離 = |A_2 – A_1| + |A_3 – A_2| + |A_4 – A_3| + |A_5 – A_4|$$

となります。そして仮にA3に行かないとすると

$$A_3に行かない場合 = |A_2 – A_1| + |A_4 – A_2| + |A_5 – A_4|$$

となります。これは以下のように総距離からの計算することが出来ます。

$$A_3に行かない場合 = 総距離 – |A_3 – A_2| – |A_4 – A_3| + |A_4 – A_2|$$

よって、事前に総距離を計算しておけば、各ケースは定数時間で算出することが可能です。

なお、以下の実装では配列の先頭と末尾に座標0を設定することで、実装をシンプルにしています。

実装

gets
x = Array.new
x[0] = 0
gets.chomp.split(' ').each{|n| x.push(n.to_i)}
x.push(0)

total_dist = 0
for i in 0..(x.size-2)
  total_dist += (x[i+1] - x[i]).abs
end

for i in 1..(x.size-2)
  p total_dist - (x[i+1] - x[i]).abs - (x[i] - x[i-1]).abs + (x[i+1] - x[i-1]).abs
end

AtCoder RC089 C: Traveling

問題

https://arc089.contest.atcoder.jp/tasks/arc089_a

解法

時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると

・次の場所との距離(X座標とY座標の差の絶対値の和)が時刻の差に等しい

がまず最もシンプルな条件になります。

また、時刻の差が距離より大きい場合は、一旦次の場所に着いてから「隣の座標に移って戻る」を繰り返せば良いので

・次の場所との距離(X座標とY座標の差の絶対値の和)と時刻の差が正の偶数である

というのがもう一つの条件になります。

上記の条件に合うかどうかを順次チェックしていけば解けます。

実装

t = Array.new
x = Array.new
y = Array.new

t[0] = x[0] = y[0] = 0

STDIN.gets
STDIN.each_line do |line|
    n = line.chomp.split(' ')
    t.push(n[0].to_i)
    x.push(n[1].to_i)
    y.push(n[2].to_i)
end

for i in 0..t.size-2

    dist = (x[i+1] - x[i]).abs + (y[i+1] - y[i]).abs
    if dist > (t[i+1] - t[i]) || (t[i+1] - t[i] - dist) % 2 == 1 then
        puts "No"
        exit
    end
end
puts "Yes"


ABC090

AtCoder Beginner Contest 090の解説です。

A – Diagonal String

問題

https://atcoder.jp/contests/abc090/tasks/abc090_a

解説

1行目は1文字目、2行目は2文字目、3行目は3文字目を出力しておわり。

実装

3.times do |i|
  print gets.split("")[i]
end
puts

B – Palindromic Numbers

問題

https://atcoder.jp/contests/abc090/tasks/abc090_b

解説

AからBの整数について、一つずつ回文数かどうかをチェックしてカウントするだけです。

実装

A,B = gets.chomp.split.map(&:to_i)
ans = 0
A.upto(B) do |i|
  ans+=1 if i.to_s == i.to_s.reverse
end

C – Flip,Flip, and Flip……

問題

https://arc091.contest.atcoder.jp/tasks/arc091_a

解説

実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N^2)になってしまって現実的では無いです。

そのため、計算で解くことにします。

まず基本的な考え方です。最初はカードは表を向いているので、全ての操作を終えた後に「カードを偶数回操作していたら表」「カードを奇数回操作していたら裏」となります。

カードの操作回数 = カードが隣接(上下左右と斜め方向)するカードの枚数+1(自分)

これをカードの場所毎に場合分けして考えると、

・周囲が全て囲まれている場合:9回(奇数)
・四隅:4回(偶数)
・端:6回(偶数)

具体例として5×5のケースのを見てみると、以下のようになります。

偶偶偶偶偶
偶奇奇奇偶
偶奇奇奇偶
偶奇奇奇偶
偶偶偶偶偶

つまり、5x5の場合は、(5 – 2) x (5 – 2) = 9 となります。
よって、NとMが3以上の場合は、(N – 2) x (M – 2)で一般化できます。

これを表にまとめると、以下のようになります。

M
1 2 3≤
N 1 1 0 M-2
2 0 0 0
3≤ N-2 0 (N-2)x(M-2)

あとは、NとMの場合分けで実装・・・ということになるのですが、もっとシンプルにすることが出来ます。

まず、NまたはMが2の場合、(N – 2) x (M – 2) は0になります。
また、N=1かつM=1の場合は、(-1) x (-1) = 1になります。
よってこの場合は一般化した式がそのまま使えます。

残りの「N=1かつMが3以上」と「Nが3以上かつM=1」の場合ですが、これはそのまま一般化した式で計算すると値が負になるのですが、符号を反転させればそれが正解になります。

よって、全てのケースについて、(N – 2) x (M – 2) の絶対値を返すことで結果が得られます。

実装

ほぼワンライナーのようなコードになりました。

n,m=gets.chomp.split.map(&:to_i)
puts ((n-2)*(m-2)).abs

D – Remainder Reminder

問題

https://arc091.contest.atcoder.jp/tasks/arc091_b

解説

a mod b が K 以上になるN以下のa、bの組み合わせを数える問題です。

まずKが0の場合はN^2が解となるので、以降はKが1以上の場合で考えます。

bで割った余りなので、まずはbを固定して考えます。

bの取りうる範囲はK+1〜Nです。(理由:bがK以下の場合、絶対に a mod b のはK以上にならないため)

aの取りうる範囲は1〜Nですが、これに対して a mod b は次のような数列になります。

1, 2, … , b-1, 0, 1, 2, … , b-1, 0, .., N mod b

よって、このうちK以上のものの数を数えればよいです。

そしてこれを定数時間で求めることが出来れば、K+1〜Nのbに対してそれぞれ計算して合計をとれば答えになり十分間に合います。

それでは、bを固定した場合のaの数え方について続いて考えます。

前述の数列の 1, 2, …, 0 (長さb)の繰り返しに着目します。この中で、K以上のものは b-K 個です。

そして 1, 2, …, 0 の繰り返しは N/b 個出現します。

また、N/bが割り切れない場合の最後の端数の部分は 1〜N mod bとなり、このうちK以上のものはmax(0, (N mod b)-(K-1)) 個になります。

つまり、bを固定したときのaの組み合わせは、以下の式で求められます。

N/b*(b-K)+max(0, (N%b)-(K-1))

これを各b(K+1〜N)に対して計算して和をとれば解になります。

実装

N,K=gets.chomp.split.map(&:to_i)
ans=0

if K==0
  puts N*N
  exit
end

(K+1).upto(N) do |b|
  ans += N/b*(b-K)
  ans += N%b-(K-1) if N%b-(K-1) > 0
end
puts ans