AtCoder AtCoder BC073 D: joisino’s travel
問題
解法
訪れる町の数が最大で8のため、訪れる順番の組み合わせは最大でも8!（=40320）通りです。
町の数は最大200であり、事前にワーシャルフロイド法(計算量はO(N3))等でそれぞれの町の間の最短...
takashi
AtCoder AtCoder AtCoder BC073 C: Write and Erase
問題
解法
数字の出現回数が
・偶数回：消えている
・奇数回：書かれている
ので、mapを使って出現回数をカウントしておき、最後に奇数回のものを数えれば解けます。
これ以外にもsetを使って操...
Mac radikoのエリアフリーを保存する方法
以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。
基本的な手順は同じですが、異なるのは最初にログイン処理を行ってCookieをローカルに保存し、以降はそのCookieを送信する点です。
環...
AtCoder AtCoder BC072 D: Derangement
問題
解法
左から順にpiをみていきます。
・pi ≠ iの時
何もせずに、右に1つ進む
・pi = iの時
次の数と入れ替えて、右に2つ進む。このとき、次の数（pi+1）がi+1かどうかは特...
AtCoder AtCoder BC072 C: Together
問題
解法
aiがとりうる値は、ai-1、ai、ai+1の3つです。
なのでとりうる値の数をカウントする配列を用意しておき、各aiについてai-1、ai、ai+1の3カ所を1ずつ加算していけば、その最大値が...
AtCoder AtCoder BC 071 D: Coloring Dominoes
問題
解法
左から順にドミノの並びを見ていく場合、並び方は
・縦に1つ置く
・横に2つ重ねる
の2パターンです。
そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。
・「...
AtCoder AtCoder BC071 C : Make a Rectangle
問題
解法
長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます（正方形は長方形に含まれる）
よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番...
AtCoder AtCoder BC070D: Transit Tree Path
問題
解法
xからKを経由してyに行く最短経路は、xからKへの最短経路とKからyへの最短経路の和になるので、
事前にKから各点への最短経路を求めておけば良い。
最短経路は、対象が閉路の無い木構造なので、幅...
AtCoder AtCoder BC070 C: Multiple Clocks
問題
解法
T1からTNの最小公倍数を求めれよい。
3つ以上の数の最小公倍数は、最初に2つの値の最小公倍数を求め、その結果と順次最小公倍数を求めていけば良い。
実装
AtCoder AtCoder BC 095 D: Static Sushi
問題
解法
寿司の数が105なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。
考えられるパターンは以下の4ケースに分けられる。
ケース1：時計回りに何個か寿司を食べてそのま...