AtCoder BC073 C: Write and Erase

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_c

解法

数字の出現回数が

・偶数回:消えている
・奇数回:書かれている

ので、mapを使って出現回数をカウントしておき、最後に奇数回のものを数えれば解けます。

これ以外にもsetを使って操作をシミュレートしても良い。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    map<ll,int> m;

    REP(i,N){
        ll a;
        cin >> a;
        m[a]++;
    }

    int ans=0;
    for(auto itr = m.begin(); itr != m.end(); itr++){
        if(itr->second % 2 != 0){
            ans++;
        }
    }

    cout << ans << endl;
}

radikoのエリアフリーを保存する方法

以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。

radikoのタイムフリーを保存する方法
先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイム...

基本的な手順は同じですが、異なるのは最初にログイン処理を行ってCookieをローカルに保存し、以降はそのCookieを送信する点です。

環境

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

実行

ログイン処理

エリアフリーの番組を保存する場合、この手順が必要になります。

最後のmailとpassにプレミア会員登録しているメールアドレスとパスワードを設定します。

$ curl -c cookie.txt 'https://radiko.jp/ap/member/login/login' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30' \
-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 'mail=aaaa@example.com&pass=password'

実行すると、cookie.txtにクッキーが保存されます。

以降のcurlコマンドではこのファイルを-bオプションで指定します。

認証1

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

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

$ curl -b cookie.txt '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 -b cookie.txt '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についてはググると出てくると思います。

curl -b cookie.txt 'https://radiko.jp/v2/api/ts/playlist.m3u8?station_id=MBS&l=15&ft=20181013222500&to=20181013235500' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H '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' \
-H 'X-Radiko-Authtoken: AJReLqXV-Oo4ymYpgRlhow' \
--data 'flash=1'

#EXTM3U
#EXT-X-VERSION:3
#EXT-X-STREAM-INF:PROGRAM-ID=1,BANDWIDTH=52973,CODECS="mp4a.40.5"
https://radiko.jp/v2/api/ts/chunklist/GTgzFQEx.m3u8

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

なお、ffmpegの実行時はCookieを送信する必要はありません。

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/chunklist/GTgzFQEx.m3u8' \
> -vn -acodec copy -bsf aac_adtstoasc out.m4a

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

まとめ

以上の手順によってradikoのエリアフリーを保存することが出来ます。


AtCoder BC072 D: Derangement

問題

https://beta.atcoder.jp/contests/abc072/tasks/arc082_b

解法

左から順にpiをみていきます。

・pi ≠ iの時
何もせずに、右に1つ進む

・pi = iの時
次の数と入れ替えて、右に2つ進む。このとき、次の数(pi+1)がi+1かどうかは特に意識する必要は無い。どちらの場合も、入れ替え後に条件を満たすため。

 なお、数列の右端がpi = iの場合は、一つ前の数と入れ替えればOK。

以上です。

ちょっと400点とは思えないほど簡単です。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    int p[N];

    REP(i,N)cin >> p[i];

    int i = 0;
    int ans = 0;
    while(i < N){
        if(p[i] == i + 1){
            ans += 1;
            i += 2;
        }else{
            i++;
        }
    }

    cout << ans << endl;
}

AtCoder BC072 C: Together

問題

https://beta.atcoder.jp/contests/abc072/tasks/arc082_a

解法

aiがとりうる値は、ai-1、ai、ai+1の3つです。

なのでとりうる値の数をカウントする配列を用意しておき、各aiについてai-1、ai、ai+1の3カ所を1ずつ加算していけば、その最大値が解となります。

実装

aiが0となる場合の扱いを簡略化するため、aiと+1、+2の箇所を加算している。最終的な解は「個数の最大値」であるためこのままでも問題無い。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
 
using namespace std;
 
typedef long long int ll;
 
const ll INF=(ll)1e18;
 
#define MAX 99999
 
int s[MAX+3];
 
int main(){
    int N;
    cin >> N;
 
    REP(i,MAX+3)s[i]=0;
 
    REP(i,N){
        int a;
        cin >> a;
 
 
        s[a]++;
        s[a+1]++;
        s[a+2]++;
 
    }
 
    int ans = 0;
 
    REP(i,MAX+3)ans = max(ans, s[i]);
 
    cout << ans << endl;
}

AtCoder BC 071 D: Coloring Dominoes

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_b

解法

左から順にドミノの並びを見ていく場合、並び方は

・縦に1つ置く
・横に2つ重ねる

の2パターンです。

そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。

・「縦に1つ」→ 「縦に1つ」
 直前の色以外の2色が選べる = 2通り

・「縦に1つ」→ 「横に2つ」
 直前の色以外の2色について、どちらかを上、どちらかを下にする = 2通り

・「横に2つ」→ 「縦に1つ」
 必ず直前の色以外の1色を選ぶことになる = 1通り

・「横に2つ」→ 「横に2つ」
 上に直前の上下の2色以外を選ぶ場合、下は必ず直前の上の色になる = 1通り
 上に直前の下の色を選ぶ場合、下は残りの2色を選べる = 2通り
 合わせて3通りとなる

また、一番左側のドミノについては、

・「縦に1つ」= 3通り
・「横に2つ」= 3 x 2 = 6通り

となる。

よって、左側から順番にドミノの並びを検査していき、上記のパターンをかけていくと解ける。(毎回MODをとることを忘れない)

実装

#include<iostream>
#include<algorithm>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    string s1, s2;

    cin >> s1 >> s2;

    int i = 0;

    ll ans = 0;
    int flag;
    if(s1[i] == s2[i]){
        ans = 3;
        i += 1;
        flag = 1;
    }else{
        ans = 6;
        i += 2;
        flag = 2;
    }

    while(i < N){
        if(s1[i] == s2[i]){
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }
            i += 1;
            flag = 1;
        }else{
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }else{
                ans *= 3;
                ans %= MOD;
            }
            i += 2;
            flag = 2;
        }
    }

    cout << ans << endl;
}

AtCoder BC071 C : Make a Rectangle

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_a

解法

長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます(正方形は長方形に含まれる)

 よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番目に長いものと2番目に長いもので長方形を作れば解となります。

 なお、辺の候補が2つ以上無ければ解無しとして0を出力します。

実装

実装としては、同じ長さの棒のカウントにはmap、辺の候補の管理はvectorで行います。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    map<ll, int> m;
    vector<ll> a;

    REP(i,N){
        ll tmp;
        cin >> tmp;
        m[tmp]++;
        if(m[tmp] % 2 == 0){
            a.push_back(tmp);
        }
    }
    if(a.size() > 1){
        sort(a.begin(),a.end());
        cout << a[a.size()-1] * a[a.size()-2] << endl;
    }else{
        cout << 0 << endl;
    }

}

AtCoder BC070D: Transit Tree Path

問題

https://beta.atcoder.jp/contests/abc070/tasks/abc070_d

解法

xからKを経由してyに行く最短経路は、xからKへの最短経路とKからyへの最短経路の和になるので、
事前にKから各点への最短経路を求めておけば良い。

最短経路は、対象が閉路の無い木構造なので、幅優先探索や深さ優先探索で求めれば良い。

なお、頂点の数Nが105でありかなり大きいため、隣接情報は隣接行列ではなく、隣接リストで行う必要がある。そうしないと、メモリ制限オーバーとなる。

実装

n = gets.chomp.to_i
edge = Array.new(n+1).map{Array.new}
(n-1).times do
    a, b, c  = gets.chomp.split(" ").map(&:to_i)
    edge[a] << [b, c]
    edge[b] << [a, c]
end

q, k = gets.chomp.split.map(&:to_i)

cost = Array.new(n+1,0)
done = Array.new(n+1,false)

queue = [k]
done[k] = true
cost[k] = 0
while(queue.size > 0)
    v = queue.pop
    
    edge[v].each do |i, j|
        if done[i] == false
            done[i] = true
            cost[i] = cost[v] + j
            queue.push(i)
        else
        end
    end
end

q.times do
    x, y = gets.chomp.split.map(&:to_i)
    puts cost[x] + cost[y]
end

AtCoder BC070 C: Multiple Clocks

問題

https://beta.atcoder.jp/contests/abc070/tasks/abc070_c

解法

T1からTNの最小公倍数を求めれよい。

3つ以上の数の最小公倍数は、最初に2つの値の最小公倍数を求め、その結果と順次最小公倍数を求めていけば良い。

実装

def gcd(a,b)
    return a if b == 0
    gcd(b,a%b)
end

def lcm(a,b)
    a * b / gcd(a,b)
end

ans = 1
n = gets.to_i
n.times do
    t = gets.to_i
    ans = lcm(ans,t)
end
puts ans

AtCoder BC 095 D: Static Sushi

問題

https://beta.atcoder.jp/contests/abc095/tasks/arc096_b

解法

寿司の数が105なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。

考えられるパターンは以下の4ケースに分けられる。

ケース1:時計回りに何個か寿司を食べてそのまま終了する
ケース2:時計回りに何個か寿司を食べてからスタート位置に戻り、反時計回りに何個か寿司を食べる
ケース3:反時計回りに何個か寿司を食べてそのまま終了する
ケース4:反時計回りに何個か寿司を食べてからスタート位置に戻り、時計回りに何個か寿司を食べる

ケース3と4はケース1と2を逆方向にしただけなので、以下ではケース1と2を考える。

ケース1は最大でN個まで寿司を食べる組み合わせしかないのでO(N)で探索可能。

ケース2については、最初に時計回りにi番目まで食べるとすると、スタート位置に戻ってから残ったN-i個の寿司のどこまで食べるかでN-i通り考えられる。

これをそのまま計算するとO(N2)となってしまい部分点しかもらえない。

そこで、事前に残っている寿司がk個の場合にどこまで食べるると最大になるかをkに対して求めておく。
そうすることで、スタート地点に戻ってからの計算量をO(1)に下げることが出来るので、全体としてO(N)に収めることが出来る。

なお、寿司のカロリーについては最初に累積和を求めておき、部分和をO(1)で算出できるようにしておく。

実装

ケース3と4はケース1と2と同じ事を逆方向に実装するだけだが、vとxのベクトルを逆方向にする(vは逆順に並べ換え、xはCから引いてから逆順に並べかえ)ことでケース1と2のロジックを流用できるかなと思ったが、素直にそのまま実装してしまった。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    ll C;

    cin >> N >> C;

    vector<ll> x(N+1), v(N+1), vc(N+1);
    x[0] = 0;
    v[0] = 0;
    FOR(i,1,N+1)cin >> x[i] >> v[i];

    //vの累積和を求める
    vc[0] = v[0];
    FOR(i,1,N+1){
        vc[i] = vc[i-1] + v[i];
    }

    vector<ll> r(N+1);
    r[0] = 0;
    for(int i = 1; i <= N; i++){
        r[i] = max(r[i-1], vc[i]-x[i]);
    }

    vector<ll> l(N+1);
    l[N] = vc[N] - vc[N-1] - (C-x[N]);

    for(int i = N-1; i >= 1; i--){
        l[i] = max(l[i+1], vc[N]-vc[i-1]-(C-x[i]));
    }

    ll ans = 0;
    REP(i,N+1){
        //ケース1
        ll tmp = vc[i] -  x[i];
        if(tmp > ans)ans = tmp ;

        //ケース2
        if(i < N){
            tmp = vc[i] - 2 * x[i] + l[i+1];
            if(tmp > ans)ans = tmp ;
        }
    }

    for(int i = N; i >= 1; i--){
        //ケース3
        ll tmp = vc[N] -  vc[i-1] - (C - x[i]);
        if(tmp > ans)ans = tmp ;

        //ケース4
        tmp = vc[N] - vc[i-1] - 2 * (C - x[i]) + r[i-1];
        if(tmp > ans)ans = tmp ;
    }
    cout << ans << endl;
}



AtCoder Beginner Contest 112 参戦記

いよいよ水色が目前と言うことで、気合いを入れて臨んだのですが、逆に空回りしてしまったのか、Cで詰まって爆死しました。

ちょっと反省ですね。

A – Programming Education

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_a

解法

Nが1だったら’Hello World’と出力し、2だったらAとBを読み込んでその和を出力するだけです。

実装

n=gets.to_i
if n == 1
    puts 'Hello World'
else
    a=gets.to_i
    b=gets.to_i
    puts a+b
end

B – Time Limit Exceeded

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_b

解法

cとtを読み込みながら、tがT以下の場合のcの最小値を求めます。

いろいろやり方があると思いますが、今回はtがT以下のcを順次配列に詰め込んでおき、最後にソートして最小値を出力するという方法をとりました。なお、配列が空の場合は’TLE’を出力。

実装

n,t=gets.chomp.split.map(&:to_i)
c = []
n.times do
    cc, tt = gets.chomp.split.map(&:to_i)
    if tt <= t
        c << cc
    end
end
if c.size > 0
    puts c.sort[0]
else
    puts "TLE"
end

C – Pyramid

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

今回、一番ハマってしまった問題です。どうしても1つだけテストケースが通らずに、WA連発してしまいました。

考え方としては、CxとCyが0〜100の整数という点ですね。

この組み合わせは高々101×101通りしか無いため、約104であり全探索可能です。

よって、Cx、Cyの組み合わせについて、全ての観測値が条件を満たすかどうかをチェックして、OKであれば出力して終了となります。

調査値のhは max(H-|x-Cx|-|y-Cy|, 0) であることから、h>0 の場合に推測される高さHは、

$$ H = h+|x-Cx|+|y-Cy| $$

となるので、これが残りの調査値を全て満たすかどうかを調べることになります。

ここでポイントになるのは、観測値hが0になるケースですね。

hが0に場合はHを推測することが出来ないので、最初にhが0で無い場合のxとyを使ってHを推定してから、改めて全ての調査値について h = max(H-|x-Cx|-|y-Cy|, 0) を満たすかどうかを調べるのが正解です。

最初、h=0のケースは無視して進めてしまったため、テストケースが通らずにハマってしまいました。

解説動画見ていても同じようなハマり方している人多かったみたい。

実装

N=gets.to_i
x = []
y = []
h = []

tmpx = 0
tmpy = 0
tmph = 0
N.times do
    xx,yy,hh = gets.chomp.split.map(&:to_i)
    x << xx
    y << yy
    h << hh
    if hh > 0
        tmpx = xx
        tmpy = yy
        tmph = hh
    end
end


0.upto(100) do |i|
    0.upto(100) do |j|
        hh = tmph + (tmpx - i).abs + (tmpy - j).abs

        flag = true;
        0.upto(N-1) do |k|
            if h[k] != [0, hh -  (x[k] - i).abs - (y[k] - j).abs].max
                flag = false
                break
            end
        end      

        if flag == true
            printf("%d %d %d\n", i, j, hh)
            exit
        end
    end
end

D – Partition

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_d

解法

求める解をDとします。

Dがa1,a2,..,aNの最大公約数ということは、DはMの約数でもあります。

つまり、M = B x D となるBが存在します。

次に、BとNの関係について考えます。

BがNより小さい場合、数列aを作ることが出来ないのでNGです。
BがNに等しい場合は、数列aは全てDとなりOKです。
BがNより大きい場合が少しややこしいのですが、この場合は、N-1個のDとM-(N-1)xDで数列を作れば良いです。

よって、M/DがN以上であれば良いです。

例えば、テストケースのM=14、N=3の場合、D=2とすると2が2個と10が1個で条件を満たします。

これを全てのMの約数についてチェックして、条件を満たす最大のものをもとめることで解けます。

なお、Mの約数の探索については、1からルートMまで調べれば良いです。

何故なら、M=AxBとした場合、AがルートM以下なら対応するBはM/Aで求めることが出来るからです。

実装

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

ans = 0
1.upto(Math.sqrt(m).to_i) do |i|
    next if(m%i != 0);
    
    if m >= i * n
        ans = i if ans < i
    end

   if m >= m/i * n
        ans = m/i if ans < m/i
    end

end
puts ans

結果

Cでハマってしまったので焦ってしまい、結果的にDも解けませんでした。最初に全探索でOKということに気づくのが遅かったのと、hが0の扱いをミスってしまったのがまずかった。反省ですね。

Dは落ち着いて考えればそんなに難しく無かったんですけど、Cで時間をとられすぎて冷静に考えることが出来ませんでした。

ということで、水色目前にして初のレートダウンになりました。

水色入りは次回にお預けですね。