AtCoder BC071 C : Make a Rectangle

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_a

解法

長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます（正方形は長方形に含まれる）

　よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番目に長いものと2番目に長いもので長方形を作れば解となります。

　なお、辺の候補が2つ以上無ければ解無しとして0を出力します。

実装

実装としては、同じ長さの棒のカウントにはmap、辺の候補の管理はvectorで行います。

#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;
    vector<ll> a;

    REP(i,N){
        ll tmp;
        cin >> tmp;
        m[tmp]++;
        if(m[tmp] % 2 == 0){
            a.push_back(tmp);
        }
    }
    if(a.size() > 1){
        sort(a.begin(),a.end());
        cout << a[a.size()-1] * a[a.size()-2] << endl;
    }else{
        cout << 0 << endl;
    }

}

AtCoder BC070D: Transit Tree Path

問題

https://beta.atcoder.jp/contests/abc070/tasks/abc070_d

解法

xからKを経由してyに行く最短経路は、xからKへの最短経路とKからyへの最短経路の和になるので、 事前にKから各点への最短経路を求めておけば良い。

最短経路は、対象が閉路の無い木構造なので、幅優先探索や深さ優先探索で求めれば良い。

なお、頂点の数Nが10⁵でありかなり大きいため、隣接情報は隣接行列ではなく、隣接リストで行う必要がある。そうしないと、メモリ制限オーバーとなる。

実装

n = gets.chomp.to_i
edge = Array.new(n+1).map{Array.new}
(n-1).times do
    a, b, c  = gets.chomp.split(" ").map(&:to_i)
    edge[a] << [b, c]
    edge[b] << [a, c]
end

q, k = gets.chomp.split.map(&:to_i)

cost = Array.new(n+1,0)
done = Array.new(n+1,false)

queue = [k]
done[k] = true
cost[k] = 0
while(queue.size > 0)
    v = queue.pop
    
    edge[v].each do |i, j|
        if done[i] == false
            done[i] = true
            cost[i] = cost[v] + j
            queue.push(i)
        else
        end
    end
end

q.times do
    x, y = gets.chomp.split.map(&:to_i)
    puts cost[x] + cost[y]
end

AtCoder BC070 C: Multiple Clocks

問題

https://beta.atcoder.jp/contests/abc070/tasks/abc070_c

解法

T₁からT_Nの最小公倍数を求めれよい。

3つ以上の数の最小公倍数は、最初に2つの値の最小公倍数を求め、その結果と順次最小公倍数を求めていけば良い。

実装

def gcd(a,b)
    return a if b == 0
    gcd(b,a%b)
end

def lcm(a,b)
    a * b / gcd(a,b)
end

ans = 1
n = gets.to_i
n.times do
    t = gets.to_i
    ans = lcm(ans,t)
end
puts ans

AtCoder BC 095 D: Static Sushi

問題

https://beta.atcoder.jp/contests/abc095/tasks/arc096_b

解法

寿司の数が10⁵なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。

考えられるパターンは以下の4ケースに分けられる。

ケース1：時計回りに何個か寿司を食べてそのまま終了する ケース2：時計回りに何個か寿司を食べてからスタート位置に戻り、反時計回りに何個か寿司を食べる ケース3：反時計回りに何個か寿司を食べてそのまま終了する ケース4：反時計回りに何個か寿司を食べてからスタート位置に戻り、時計回りに何個か寿司を食べる

ケース3と4はケース1と2を逆方向にしただけなので、以下ではケース1と2を考える。

ケース1は最大でN個まで寿司を食べる組み合わせしかないのでO(N)で探索可能。

ケース2については、最初に時計回りにi番目まで食べるとすると、スタート位置に戻ってから残ったN-i個の寿司のどこまで食べるかでN-i通り考えられる。

これをそのまま計算するとO(N²)となってしまい部分点しかもらえない。

そこで、事前に残っている寿司がk個の場合にどこまで食べるると最大になるかをkに対して求めておく。 そうすることで、スタート地点に戻ってからの計算量をO(1)に下げることが出来るので、全体としてO(N)に収めることが出来る。

なお、寿司のカロリーについては最初に累積和を求めておき、部分和をO(1)で算出できるようにしておく。

実装

ケース3と4はケース1と2と同じ事を逆方向に実装するだけだが、vとxのベクトルを逆方向にする（vは逆順に並べ換え、xはCから引いてから逆順に並べかえ）ことでケース1と2のロジックを流用できるかなと思ったが、素直にそのまま実装してしまった。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    ll C;

    cin >> N >> C;

    vector<ll> x(N+1), v(N+1), vc(N+1);
    x[0] = 0;
    v[0] = 0;
    FOR(i,1,N+1)cin >> x[i] >> v[i];

    //vの累積和を求める
    vc[0] = v[0];
    FOR(i,1,N+1){
        vc[i] = vc[i-1] + v[i];
    }

    vector<ll> r(N+1);
    r[0] = 0;
    for(int i = 1; i <= N; i++){
        r[i] = max(r[i-1], vc[i]-x[i]);
    }

    vector<ll> l(N+1);
    l[N] = vc[N] - vc[N-1] - (C-x[N]);

    for(int i = N-1; i >= 1; i--){
        l[i] = max(l[i+1], vc[N]-vc[i-1]-(C-x[i]));
    }

    ll ans = 0;
    REP(i,N+1){
        //ケース1
        ll tmp = vc[i] -  x[i];
        if(tmp > ans)ans = tmp ;

        //ケース2
        if(i < N){
            tmp = vc[i] - 2 * x[i] + l[i+1];
            if(tmp > ans)ans = tmp ;
        }
    }

    for(int i = N; i >= 1; i--){
        //ケース3
        ll tmp = vc[N] -  vc[i-1] - (C - x[i]);
        if(tmp > ans)ans = tmp ;

        //ケース4
        tmp = vc[N] - vc[i-1] - 2 * (C - x[i]) + r[i-1];
        if(tmp > ans)ans = tmp ;
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 112 参戦記

いよいよ水色が目前と言うことで、気合いを入れて臨んだのですが、逆に空回りしてしまったのか、Ｃで詰まって爆死しました。

ちょっと反省ですね。

A - Programming Education

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_a

解法

Ｎが1だったら'Hello World'と出力し、2だったらＡとＢを読み込んでその和を出力するだけです。

実装

n=gets.to_i
if n == 1
    puts 'Hello World'
else
    a=gets.to_i
    b=gets.to_i
    puts a+b
end

B - Time Limit Exceeded

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_b

解法

cとtを読み込みながら、tがT以下の場合のcの最小値を求めます。

いろいろやり方があると思いますが、今回はtがT以下のcを順次配列に詰め込んでおき、最後にソートして最小値を出力するという方法をとりました。なお、配列が空の場合は'TLE'を出力。

実装

n,t=gets.chomp.split.map(&:to_i)
c = []
n.times do
    cc, tt = gets.chomp.split.map(&:to_i)
    if tt <= t
        c << cc
    end
end
if c.size > 0
    puts c.sort[0]
else
    puts "TLE"
end

C - Pyramid

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

今回、一番ハマってしまった問題です。どうしても1つだけテストケースが通らずに、WA連発してしまいました。

考え方としては、CxとCyが0〜100の整数という点ですね。

この組み合わせは高々101x101通りしか無いため、約10⁴であり全探索可能です。

よって、Cx、Cyの組み合わせについて、全ての観測値が条件を満たすかどうかをチェックして、OKであれば出力して終了となります。

調査値のhは max(H-|x-Cx|-|y-Cy|, 0) であることから、h>0 の場合に推測される高さHは、

となるので、これが残りの調査値を全て満たすかどうかを調べることになります。

ここでポイントになるのは、観測値hが0になるケースですね。

hが0に場合はHを推測することが出来ないので、最初にhが0で無い場合のxとyを使ってHを推定してから、改めて全ての調査値について h = max(H-|x-Cx|-|y-Cy|, 0) を満たすかどうかを調べるのが正解です。

最初、h=0のケースは無視して進めてしまったため、テストケースが通らずにハマってしまいました。

解説動画見ていても同じようなハマり方している人多かったみたい。

実装

N=gets.to_i
x = []
y = []
h = []

tmpx = 0
tmpy = 0
tmph = 0
N.times do
    xx,yy,hh = gets.chomp.split.map(&:to_i)
    x << xx
    y << yy
    h << hh
    if hh > 0
        tmpx = xx
        tmpy = yy
        tmph = hh
    end
end


0.upto(100) do |i|
    0.upto(100) do |j|
        hh = tmph + (tmpx - i).abs + (tmpy - j).abs

        flag = true;
        0.upto(N-1) do |k|
            if h[k] != [0, hh -  (x[k] - i).abs - (y[k] - j).abs].max
                flag = false
                break
            end
        end      

        if flag == true
            printf("%d %d %d\n", i, j, hh)
            exit
        end
    end
end

D - Partition

問題

https://beta.atcoder.jp/contests/abc112/tasks/abc112_d

解法

求める解をDとします。

Dがa₁,a₂,..,a_Nの最大公約数ということは、DはMの約数でもあります。

つまり、M = B x D となるBが存在します。

次に、BとNの関係について考えます。

BがNより小さい場合、数列aを作ることが出来ないのでNGです。 BがNに等しい場合は、数列aは全てDとなりOKです。 BがNより大きい場合が少しややこしいのですが、この場合は、N-1個のDとM-(N-1)xDで数列を作れば良いです。

よって、M/DがN以上であれば良いです。

例えば、テストケースのM=14、N=3の場合、D=2とすると2が2個と10が1個で条件を満たします。

これを全てのMの約数についてチェックして、条件を満たす最大のものをもとめることで解けます。

なお、Mの約数の探索については、1からルートMまで調べれば良いです。

何故なら、M=AxBとした場合、AがルートM以下なら対応するBはM/Aで求めることが出来るからです。

実装

n,m=gets.chomp.split.map(&:to_i)

ans = 0
1.upto(Math.sqrt(m).to_i) do |i|
    next if(m%i != 0);
    
    if m >= i * n
        ans = i if ans < i
    end

   if m >= m/i * n
        ans = m/i if ans < m/i
    end

end
puts ans

結果

Cでハマってしまったので焦ってしまい、結果的にDも解けませんでした。最初に全探索でOKということに気づくのが遅かったのと、hが0の扱いをミスってしまったのがまずかった。反省ですね。

Dは落ち着いて考えればそんなに難しく無かったんですけど、Cで時間をとられすぎて冷静に考えることが出来ませんでした。

ということで、水色目前にして初のレートダウンになりました。

水色入りは次回にお預けですね。

AtCoder BC102 D: Equal Cut

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_b

解法

長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせは_n-1C₃通りあります。Nは最大2x10⁵であるため、全ての組み合わせを試すのは現実的ではありません。

「P、Q、R、Sの最大値と最小値の差の絶対値が最小になる」は言い換えると、「P、Q、R、Sの大きさが出来るだけ近い場合」ということです。最適なのは、数列の総和の1/4になる場合ですが、実際にはなるべく1/4に近い値を目指すことになります。

ここで数列の三つの切れ目をi1、i2、i3とおきます。

そしてi2を固定した場合を考えます。

この時、PとQ、RとSの差が最小になる切れ目がi1とi3であったとします。

次に、i2を右に一つずらす場合を考えます。

この時、i1とi3は「そのまま」か「右にずれる」ことになります。（つまり単調増加）

そして、PとQ、RとSの差が最小になる新しいi1とi3に更新していきます。

このような処理をi1=0、i2=1、i2=3を初期状態として繰り返しながら、「P、Q、R、Sの最大値と最小値の差の絶対値が最小」になる値を求めることで解けます。

なお、配列の部分和については、累積和を事前に求めておくことで定数時間で計算できますので、全体としてはO(N)で解くことが出来ます。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

# aa = 累積和
aa = [a[0]]
1.upto(n-1) do |i|
    aa << aa[-1] + a[i]
end

i1 = 0
i2 = 1
i3 = 2

ans = 10 ** 9

while(i2 < n-2) do
    while i1 < i2 - 1 do
        if (aa[i1] - (aa[i2] - aa[i1])).abs > (aa[i1+1] - (aa[i2] - aa[i1+1])).abs
            i1 += 1
        else
            break
        end
    end

    while i3 < n - 2 do
        if (aa[n-1] - aa[i3] - (aa[i3] - aa[i2])).abs > (aa[n-1] - aa[i3+1] - (aa[i3+1] - aa[i2])).abs
            i3 += 1
        else
            break
        end
    end
    pqrs = [aa[i1], aa[i2] - aa[i1], aa[i3] - aa[i2], aa[n-1] - aa[i3]]

    ans = (pqrs.max - pqrs.min) if ans > (pqrs.max - pqrs.min)


    i2 += 1
end

puts ans

AtCoder BC102 C: Linear Approximation

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

解法

以下の数式の値を最小にするbをどのようにして求めるかという問題です。

これは、Bi = Ai - 1 とすると

と書き換えることがが出来ます。

これが最小になるのは、数列Bの中央値をbとした場合です。

図にしてみるとよく分かります。 （見やすくするためにBはソート済みとしています）

Nが奇数の場合、bがB3より大きく（小さく）なるとその分合計値が増加します。

Nが偶数の場合、B2〜B3の間から外れると、その分合計値は大きくなります。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

0.upto(n-1) do |i|
    a[i] -= (i+1)
end
a.sort!

m = a[n/2]

ans = 0
0.upto(n-1) do |i|
    ans += (a[i] - m).abs
end

puts ans