AtCoder Beginner Contest 112 参戦記

AtCoder

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

ちょっと反省ですね。

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通りしか無いため、約104であり全探索可能です。

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

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

{ \displaystyle H = h+|x-Cx|+|y-Cy| }

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

ここでポイントになるのは、観測値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がa1,a2,..,aNの最大公約数ということは、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で時間をとられすぎて冷静に考えることが出来ませんでした。

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

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

f:id:taka_xyz:20181027193640p:plain