以前にradikoのタイムフリー＆エアフリーを保存するする手順を書きましたが、今回はRuby版です。 takaxyz.hatenablog.com 環境 macOS Mojava ruby 2.5 事前にffmpegとswftoolsを導入しておく httpclient gemをインストールしておく 事前準備 myplayer-releas…

Apache + PassengerでのRails本番環境を作成する手順についてまとめました。 前提 Vagrant のCentOS7.5イメージを利用する Rails のアプリケションはgithub等のリモートリポジトリから取得する Vagrant + Virtual Boxはインストール済みとする 環境 CentOS 7…

問題 https://beta.atcoder.jp/contests/abc074/tasks/arc083_b 解法 ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。 問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて…

問題 https://beta.atcoder.jp/contests/abc074/tasks/arc083_a 解法 質量の合計の最大値が3000gに対して、水は100g単位、砂糖は1g単位です。 なので、全ての組み合わせを試したとしても間に合います。 よって、4重ループで全探索すれば解けます。 実装 A, B…

今度こそは水色へ、と意気込んだABC113。 C完でDも解法はある程度わかったのですが、実装で手間取って例題を通す前に時間切れとなりました。 うーん、水色目前で停滞中です。 A - Discount Fare 問題 https://beta.atcoder.jp/contests/abc113/tasks/abc113_…

問題 https://beta.atcoder.jp/contests/abc079/tasks/abc079_d 解法 各数字を1に書き換えるコストが最小になるようにし、その合計を出せば良い。 「1に書き換える最小コスト」＝「1への最短距離」と考えることが出来るので、事前にワーシャルフロイド法など…

問題 https://beta.atcoder.jp/contests/abc079/tasks/abc079_c 解法 演算子の場所は3カ所で+-の2通りしかない。そのため、全パターン試しても 通りで十分に速い。 全パターン試す実装はビット演算で実施。 実装 #include<iostream> #include<vector> #include<map> #include<algorithm> #inclu</algorithm></map></vector></iostream>…

ABCやARCと違うコンテストに参加するのは今回が初でした。 KLabさん主催とのことですが、ほぼいつもの問題の感じと同じでしたね。 今度こそは水色に、と意気込んだのですが、Cの考察不足で最後までWAが残ってしまいまたもや撃沈でした。。。 A - Measure 問…

問題 https://beta.atcoder.jp/contests/abc073/tasks/abc073_d 解法 訪れる町の数が最大で8のため、訪れる順番の組み合わせは最大でも8!（=40320）通りです。 町の数は最大200であり、事前にワーシャルフロイド法(計算量はO(N3))等でそれぞれの町の間の最短…

問題 https://beta.atcoder.jp/contests/abc073/tasks/abc073_c 解法 数字の出現回数が ・偶数回：消えている ・奇数回：書かれている ので、mapを使って出現回数をカウントしておき、最後に奇数回のものを数えれば解けます。 これ以外にもsetを使って操作を…

以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。 takaxyz.hatenablog.com 基本的な手順は同じですが、異なるのは最初にログイン処理を行ってCookieをローカルに保存し、以降はそのCookieを送信する点です。 環境 O…

問題 https://beta.atcoder.jp/contests/abc072/tasks/arc082_b 解法 左から順にpiをみていきます。 ・pi ≠ iの時 何もせずに、右に1つ進む ・pi = iの時 次の数と入れ替えて、右に2つ進む。このとき、次の数（pi+1）がi+1かどうかは特に意識する必要は無い…

問題 https://beta.atcoder.jp/contests/abc072/tasks/arc082_a 解法 aiがとりうる値は、ai-1、ai、ai+1の3つです。 なのでとりうる値の数をカウントする配列を用意しておき、各aiについてai-1、ai、ai+1の3カ所を1ずつ加算していけば、その最大値が解となり…

問題 https://beta.atcoder.jp/contests/abc071/tasks/arc081_b 解法 左から順にドミノの並びを見ていく場合、並び方は ・縦に1つ置く ・横に2つ重ねる の2パターンです。 そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。 ・「縦に1つ…

問題 https://beta.atcoder.jp/contests/abc071/tasks/arc081_a 解法 長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます（正方形は長方形に含まれる） よって、同じ棒が2本現れる毎に辺の候補に追加し、…

問題 https://beta.atcoder.jp/contests/abc070/tasks/abc070_d 解法 xからKを経由してyに行く最短経路は、xからKへの最短経路とKからyへの最短経路の和になるので、 事前にKから各点への最短経路を求めておけば良い。 最短経路は、対象が閉路の無い木構造な…

問題 https://beta.atcoder.jp/contests/abc070/tasks/abc070_c 解法 T1からTNの最小公倍数を求めれよい。 3つ以上の数の最小公倍数は、最初に2つの値の最小公倍数を求め、その結果と順次最小公倍数を求めていけば良い。 実装 def gcd(a,b) return a if b ==…

問題 https://beta.atcoder.jp/contests/abc095/tasks/arc096_b 解法 寿司の数が105なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。 考えられるパターンは以下の4ケースに分けられる。 ケース1：時計回りに何個か寿司を食べてそ…

いよいよ水色が目前と言うことで、気合いを入れて臨んだのですが、逆に空回りしてしまったのか、Ｃで詰まって爆死しました。 ちょっと反省ですね。 A - Programming Education 問題 https://beta.atcoder.jp/contests/abc112/tasks/abc112_a 解法 Ｎが1だっ…

問題 https://beta.atcoder.jp/contests/abc102/tasks/arc100_b 解法 長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせはn-1C3通りあります。Nは最大2x105であるため、全ての組み合わせを試すのは現実的ではありません。 「P、Q、R、Sの…

問題 https://beta.atcoder.jp/contests/abc102/tasks/arc100_a 解法 以下の数式の値を最小にするbをどのようにして求めるかという問題です。 これは、Bi = Ai - 1 とすると と書き換えることがが出来ます。 これが最小になるのは、数列Bの中央値をbとした場…

久しぶりにリアルタイムで参戦できたので結果のまとめです。 A - ABC333 問題 https://beta.atcoder.jp/contests/abc109/tasks/abc109_a 解法 A x B x C が奇数になりうるということは、少なくとも A x Bは奇数でなくてはいけません。 また、Cは1 or 2 or 3…

[mathjax] 問題 https://beta.atcoder.jp/contests/abc108/tasks/arc102_a 解法 a+b、b+c、c+aが全てkで割り切れると言うことは、 $$(a+b)\%k=(b+c)\%k=(c+a)\%k=0$$ ということです。 ここで、aに着目した場合、以下の2通りが考えられます・ ・aがkで割り切…

問題 https://beta.atcoder.jp/contests/abc103/tasks/abc103_d 解法 最初に(ai, bi)の組み合わせについて、a→bの順番でソートします。 そして、ソート後の組み合わせについて、昇順に橋を落とす範囲を求めていきます。 その場合、i番目とi+1番目について、…

問題 https://beta.atcoder.jp/contests/abc103/tasks/abc103_c 解法 m mod ai が最大になるのは、mがaiの倍数-1の時で、余りはai-1になる。 よって、mがa1,a2,,,anの最小公倍数-1の時にf(m)は最大になる。 最大値を求めるだけなら最小公倍数自体は求める必…

問題 https://beta.atcoder.jp/contests/abc103/tasks/abc103_b 解法 文字列の長さが最大100と短いため、全パターンを確かめて比較するだけでOK 実装 s = gets.chomp t = gets.chomp n = s.size n.times do |i| ss = s[i, n-i] + s[0, i] if ss == t puts "Y…

問題 https://beta.atcoder.jp/contests/agc020/tasks/agc020_a 解法 各自がとるべき戦略を考えるにあたり、まずはどのような状態で勝敗が確定するかを考えます。 勝敗が確定するのは、以下のように片方が端っこに追いやられた状態で、次のターンがまわって…

問題 https://abc098.contest.atcoder.jp/tasks/arc098_a 解法 ある人をリーダーに選んだ場合、 西から東に向きを変える人の数 ＝ 選んだ人より西の人の内、西を向いている人の数 東から西に向きを変える人の数 ＝ 選んだ人より東の人の内、東を向いている人…

問題 https://abc098.contest.atcoder.jp/tasks/abc098_b 解法 文字列のサイズが最大でも100なので、全ての切断箇所のパターンで「どちらにも含まれる文字」の種類を数え上げれば解けます。 Rubyの場合、配列の「＆」をとると共通部分が求められるので、実装…

先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイムフリーの保存機能を削除していたことに気づきました。 ループバック機能を使えば、再生しながら保存することは可能なのだがそれだ…