Mac先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイムフリーの保存機能を削除していたことに気づきました。ループバック機能を使えば、再生しながら保存することは可能なのだがそれだと番組の放送時間と同じだけ時間がかかってしまいます。他にいいソフトが無いか探してみたのですが、いまいちだったので結局自分でスクリプトを組ことにしました。スクリプトを組むにあたって、radikoの保存手順を調べてみました。key事前準備でダウンロードしたキーとなる画像ファイルから、X-Radiko-KeyOffsetがオフセット、X-Radiko-KeyLengthが長さとなるデータを抽出する。UNIXのddコマンドを使って抽出する。抽出したデータはBase64で文字列に変換する。Japan応答として地域の情報が帰ってくると認証は成功。音声の保存プレイリスト取得用のURL(https://radiko.jp/v2/api/ts/playlist.m3u8)に対して、クエリとして放送局IDと開始、終了時間を指定してするとプレイリストを取得できます。lというクエリには15を指定するらしいのですが、意味は不明です。放送局IDについてはググると出てくると思います。これをffmpegの引数として渡すことで、音声の保存が可能。out.m4aiTunes等で聴けるように、ffmpegのオプションでm4a形式で保存するようにしています。まとめ以上の手順によってradikoのタイムフリーを短時間で保存することが出来ます。最初にログイン処理を挟めばエリアフリーも対応可能です。エリアフリーの場合はこちら。以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。最初、貪欲に操作をシミュレートして解こうと思ったのですが、組み合わせが果てしなくあることに気づき早々に断念。例題の解き方を眺めているうちに、各操作のグルーピングがポイントであることに気づきました。3(1,2)と(2,3)は2で繋がってます。このような場合、p1、p2、p3については何回か操作を繰り返すことで任意の並び順に変えることが出来ます。Findのアルゴリズムを使うことで求められます。グルーピングを行った後、piがiと同じグループに入っているればpi=iとすることが出来るので、その数を数えることで解けます。Findの実装については、以下を参考にさせていただきました。UnionFind木の実装こういう定番のアルゴリズムって、事前に用意して置いた方が良いですね。最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点?って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列挙してしまえば良いことに気づきました。計算量としては、Kが5だったとしても、長さ1、2、3、4、5の部分文字列を求めるだけであり、各部分文字列を求める計算量はO(N)なので、十分間に合います。競技プログラミング問題https://abc097.contest.atcoder.jp/tasks/abc097_b解法bpがX以下になる組み合わせについて考えます。これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N2)で求めることが出来ます。pについては計算結果がXを超えた時点で以降は打ち切ることが出来ます。このようにして求めた冪乗のリストの内、X以下で最大のものを求めることで解けます。競技プログラミング問題https://agc023.contest.atcoder.jp/tasks/agc023_b解法まず、初期状態で「よい盤面」なものについて考える。N=3の場合、以下のような盤面が「よい盤面」である。dとなり、これも「よい盤面」となる。右方向に1、下方向に1ずらしても同じである。「よい盤面」を横方向と縦方向に同じだけずらしたものは同様に「よい盤面」となる。よって、整数A、Bの組み合わせのうち、Bを0に固定し、Aのみ0〜N-1に変えて「よい盤面」になる数を数えて、その結果をN倍すれば解となる。計算量は「よい状態」かどうかのチェックにO(N2)かかるため、全体ではO(N3)となるが、Nは最大300なので一応間に合う。最初に問題を見て、これ本当に200点?って思うくらい悩んだ。a4}の累積和を考える。a4この時、部分数列の和は累積和の差で求められるのがポイント。