AtCoder Tenka1 Programmer Beginner Contest 参戦記
ABCやARCと違うコンテストに参加するのは今回が初でした。
KLabさん主催とのことですが、ほぼいつもの問題の感じと同じでしたね。
今度こそは水色に、と意気込んだのですが、Cの考察不足で最後までWAが残ってしまいまたもや撃沈でした。。。
A - Measure
問題
https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a
解法
入力文字列の長さで分岐させるだけ
実装
s=gets.chomp if s.size == 3 puts s.reverse else puts s end
B - Exchange
問題
https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b
解法
二人の操作を愚直にシミュレートしていくだけ
実装
a,b,k=gets.chomp.split.map(&:to_i) k.times do |i| if i % 2 == 0 if a%2 == 1 a -= 1 end b += a/2 a /= 2 else if b%2 == 1 b -= 1 end a += b/2 b /= 2 end end printf("%d %d\n",a,b)
C - Align
問題
https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
解法
整数の数Nはなので、全て列挙する方法だとぜんぜん間に合いません。
よってどういう並びが適切かを考えることになります。
例えば、1、3、5という3つの整数を並べる場合を考えます。
この場合、1 3 5 と3つを昇順に並べるのは、1 5 という並びと等価です。
なぜならば、1 3 5 は (5-3) + (3-1) = 4 であり、1 5は (5-1) = 4 となるため、真ん中に3を入れる意味が無くなります。これは降順についても同じです。
よって、並べ方のうち3つ以上が昇順（または降順）で現れるものは最適ではありません。
そのため、作る列をsで表すとすると、 のような凸凹の並びになります。
この際、整数の数が偶数か奇数かで分けて考える必要があります。
そこで実際にNが偶数の場合として6を考えてみます。
すると、 と
が考えられます。
それぞれの計算結果は
となりますが、両者は並び順が異なるだけなので同じとみなせます。
前者を最大にすることを考えた場合、2倍で加算されるや
にはなるべく大きい値、2倍で減算される
や
にはなるべく小さい値を当てはめるべきです。
よって、事前に与えられた整数をソートしておき、大きい方の半分は2倍して加算、小さい方の半分は2倍して減算していけばよいことがわかります。ただし、中央値の2つの数については1倍のままにする必要があります。
次にNが奇数の場合として5を考えてみます。
今度は、 と
が考えられます。
それぞれの計算結果は
となり、 両者は異なります。これは、並びの両端に大きい数を配置するか小さい数を配置するかの違いになります。（本番では2パターンあることに気づかずに片方だけ実装してしまい見事にWAをくらいました。。。）
よって、奇数の場合は両方のケースを計算してみて、結果が大きい方を解とすればよいです。
実装
n=gets.to_i a = [] n.times do a << gets.to_i end a.sort! ans = 0 if n % 2 == 0 (n/2+1).upto(n-1) do |i| ans += a[i] * 2 end ans += a[n/2] (0).upto(n/2-2) do |i| ans -= a[i] * 2 end ans -= a[n/2-1] else (n/2+1).upto(n-1) do |i| ans += a[i] * 2 end (0).upto(n/2-2) do |i| ans -= a[i] * 2 end ans -= a[n/2] ans -= a[n/2-1] tmp = ans ans = 0 (n/2+2).upto(n-1) do |i| ans += a[i] * 2 end ans += a[n/2] ans += a[n/2+1] (0).upto(n/2-1) do |i| ans -= a[i] * 2 end ans = tmp if tmp > ans end puts ans
D - Crossing
問題
https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d
解法
満たすべき条件の対称性や入力例1の結果を見る限り、部分集合に含まれる整数の数は全て等しいと予想されます。
そこで、試しに部分集合のサイズが3になるケースを考えてみます。
すると部分集合の組は {1, 2, 3} {1, 4, 5} {2, 4, 6} {3, 5, 6} となります。この場合、Nは6になります。
さらにサイズが4になるケースを考えてみます。
{1, 2, 3, 4} {1, 5, 6, 7} {2, 5, 8, 9} {3, 6, 8, 10} {4, 7, 9,10} となります。この場合、Nは10になります。
ここで、部分集合の組の数kは部分集合のサイズより1大きい点に気づくかどうかがポイントです。
例えば {1, 2, 3, 4}を基点に考えた場合、他の部分集合との積は必ず1つしかなく、かつ、各整数は各部分集合のうち2つにしか含まれないため、他の部分集合は4つしか作れません。
どの整数も部分集合の組の2つにしか含まれないため、 となります。
よって、この条件を満たさないNが与えられた場合は、解は NO となります。
では次に、具体的な組み合わせを列挙する方法ですが、本番ではここでつまずいてしまいました。。。
以下のように考えます。
を考えた場合、これは必ずユニークな値になります。
よって、iとjを2重ループでまわして組み合わせを列挙していき、そこに整数を1つずつ当てはめていきます。その際に、各部分集合にその整数を割り当てていき、最後に各部分集合に含まれる値を出力すればよいです。
実装
n=gets.to_i k = 0 1.upto(1000) do |i| if i * (i-1) / 2 == n k = i break elsif i * (i-1) / 2 > n break end end if k == 0 puts "No" exit else puts "Yes" end s = 1 ans = [] 1.upto(k-1) do |i| (i+1).upto(k) do |j| ans[i] = [] if ans[i] == nil ans[j] = [] if ans[j] == nil ans[i] << s ans[j] << s s += 1 end end puts k 1.upto(k) do |i| printf("%d ", ans[i].size) puts ans[i].join(" ") end
感想
400点のCはほぼ解法がわかっていたのに、もう一歩考察が足りずにWAとなってしまいました。
500点のDも考え方はあっていたのですが、組み合わせの列挙で躓いてしまった。
ということで、またしても水色手前で足踏み状態です。
AtCoder BC073 D: joisino's travel
問題
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
解法
訪れる町の数が最大で8のため、訪れる順番の組み合わせは最大でも8!（=40320）通りです。
町の数は最大200であり、事前にワーシャルフロイド法(計算量はO(N3))等でそれぞれの町の間の最短距離を求めておけば、全ての組み合わせを試しても十分に間に合います。
実装
#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; ll d[201][201]; int main(){ int N, M, R; cin >> N >> M >> R; vector<int> r; REP(i,R){ int tmp; cin >> tmp; r.push_back(tmp); } sort(r.begin(),r.end()); REP(i,N+1)REP(j,N+1)d[i][j] = INF; REP(i,M){ int a,b,c; cin >> a >> b >>c; d[a][b] = c; d[b][a] = c; } REP(i,N+1)REP(j,N+1)REP(k,N+1){ d[j][k] = min(d[j][k], d[j][i] + d[i][k]); } ll ans = INF; do { ll tmp = 0; REP(i,R-1){ tmp += d[r[i]][r[i+1]]; } ans = min(ans,tmp); } while (std::next_permutation(r.begin(), r.end())); cout << ans << endl; }
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のタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。
基本的な手順は同じですが、異なるのは最初にログイン処理を行って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
認証１の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==」が認証２で使うParticalkeyとなる
認証２
認証２の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; }
