問題 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とした場…