問題 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/abc070/tasks/abc070_c 解法 T1からTNの最小公倍数を求めれよい。 3つ以上の数の最小公倍数は、最初に2つの値の最小公倍数を求め、その結果と順次最小公倍数を求めていけば良い。 実装 def gcd(a,b) return a if 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の場合、配列の「＆」をとると共通部分が求められるので、実装…

問題 https://abc097.contest.atcoder.jp/tasks/arc097_b 解法 最初、貪欲に操作をシミュレートして解こうと思ったのですが、組み合わせが果てしなくあることに気づき早々に断念。 例題の解き方を眺めているうちに、各操作のグルーピングがポイントであるこ…

問題 https://abc097.contest.atcoder.jp/tasks/abc097_c 解法 最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点？って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列…

問題 https://abc097.contest.atcoder.jp/tasks/abc097_b 解法 bpがX以下になる組み合わせについて考えます。 これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N2)で求めることが出来ます。 ただし、pについては計算結果…

問題 https://agc023.contest.atcoder.jp/tasks/agc023_b 解法 まず、初期状態で「よい盤面」なものについて考える。 例えば、N=3の場合、以下のような盤面が「よい盤面」である。 a b c b d e c e f これを右方向に1、下方向に1ずらすと f c e c a b e b d …

問題 https://agc023.contest.atcoder.jp/tasks/agc023_a 解法 最初に問題を見て、これ本当に200点？って思うくらい悩んだ。 とりあえず、累積和をとってみる。 例えば、サイズ4の数列：{a1 a2 a3 a4}の累積和を考える。 S1 = a1 S2 = a1 + a2 S3 = a1 + a2 …

問題 与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。 例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。 https://code.google.com/codejam/contest/3264486/dashboard#s=p1 方針 Nから順にデクリメ…

問題 https://arc093.contest.atcoder.jp/tasks/arc093_a 解法 観光スポットに行かないケースを毎回計算していると、O(n2)の計算量になってしまいます。 そこで以下のように考えます。 観光地が5カ所の場合、全ての観光地に行くケースの総距離は、 $$総距離 …

問題 https://arc089.contest.atcoder.jp/tasks/arc089_a 解法 時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると ・次の場所との距離（X座標とY座標の差の絶対値の和）が時刻の差に等しい がまず最もシンプルな条件になります…

問題 https://arc091.contest.atcoder.jp/tasks/arc091_a 解説 実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N2)になってしまって現実的では無いです。 そのため、計算で解くことにします。 まず基本的な考え方です。最初はカードは…

問題 と - からなる文字列Sが与えられる。以下の操作を繰り返して、+ のみの文字列に変換するための最小回数を求める。 ・文字列Sのi番目までの+と-を反転させて、なおかつ、逆順にする。 例： 文字列Sが ++--+ でi=3の場合、++- を反転(--+）して逆順（+--…

問題 与えられた非負整数Nについて、N×1,N×2,…とNの倍数をあげていく。その数の10進表記で見た場合の桁が0～9全て出そろった時の最後の数を出力する。(そろわない場合は"INSOMNIA"を出力) 例：N=2の場合、2×1=2,2×2=4,…,2×35=70,…,2×44=88,2×45=90 で0～9が…

Code Jam Japan 2011の決勝の問題Aを解いてみた。 ■ 考え方 ・最大になる組み合わせを総当たりで計算した場合、間違いなくLargeが解けないので、何らかの法則を見つける必要がある ・まずは三角形の面積について、基本的な計算方法を明確にする。隣り合うエ…