AtCoder Tenka1 Programmer Beginner Contest 参戦記

ABCやARCと違うコンテストに参加するのは今回が初でした。

KLabさん主催とのことですが、ほぼいつもの問題の感じと同じでしたね。

今度こそは水色に、と意気込んだのですが、Cの考察不足で最後までWAが残ってしまいまたもや撃沈でした。。。

A – Measure

問題

A - Measure
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

入力文字列の長さで分岐させるだけ

実装

s=gets.chomp
if s.size == 3
    puts s.reverse
else
    puts s
end

B – Exchange

問題

B - Exchange
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

二人の操作を愚直にシミュレートしていくだけ

実装

a,b,k=gets.chomp.split.map(&:to_i)
k.times do |i|
    if i % 2 == 0
        if a%2 == 1
            a -= 1
        end
        b += a/2
        a /= 2
    else
        if b%2 == 1
            b -= 1
        end
        a += b/2
        b /= 2
    end
end

printf("%d %d\n",a,b)

C – Align

問題

C - Align
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

整数の数Nはなので、全て列挙する方法だとぜんぜん間に合いません。

よってどういう並びが適切かを考えることになります。

例えば、1、3、5という3つの整数を並べる場合を考えます。

この場合、1 3 5 と3つを昇順に並べるのは、1 5 という並びと等価です。

なぜならば、1 3 5 は (5-3) + (3-1) = 4 であり、1 5は (5-1) = 4 となるため、真ん中に3を入れる意味が無くなります。これは降順についても同じです。

よって、並べ方のうち3つ以上が昇順(または降順)で現れるものは最適ではありません。

そのため、作る列をsで表すとすると、 のような凸凹の並びになります。

この際、整数の数が偶数か奇数かで分けて考える必要があります。

そこで実際にNが偶数の場合として6を考えてみます。

すると、 と が考えられます。

それぞれの計算結果は

となりますが、両者は並び順が異なるだけなので同じとみなせます。

前者を最大にすることを考えた場合、2倍で加算されるやにはなるべく大きい値、2倍で減算されるやにはなるべく小さい値を当てはめるべきです。

よって、事前に与えられた整数をソートしておき、大きい方の半分は2倍して加算、小さい方の半分は2倍して減算していけばよいことがわかります。ただし、中央値の2つの数については1倍のままにする必要があります。

次にNが奇数の場合として5を考えてみます。

今度は、 と が考えられます。

それぞれの計算結果は

となり、 両者は異なります。これは、並びの両端に大きい数を配置するか小さい数を配置するかの違いになります。(本番では2パターンあることに気づかずに片方だけ実装してしまい見事にWAをくらいました。。。)

よって、奇数の場合は両方のケースを計算してみて、結果が大きい方を解とすればよいです。

実装

n=gets.to_i
a = []
n.times do
    a << gets.to_i
end
a.sort!

ans = 0
if n % 2 == 0
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    ans += a[n/2]
    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2-1]
else
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2]
    ans -= a[n/2-1]

    tmp = ans
    ans = 0

    (n/2+2).upto(n-1) do |i|
        ans += a[i] * 2    
    end
    ans += a[n/2]
    ans += a[n/2+1]

    (0).upto(n/2-1) do |i|
        ans -= a[i] * 2    
    end

    ans = tmp if tmp > ans

end
puts ans

D – Crossing

問題

D - Crossing
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

満たすべき条件の対称性や入力例1の結果を見る限り、部分集合に含まれる整数の数は全て等しいと予想されます。

そこで、試しに部分集合のサイズが3になるケースを考えてみます。

すると部分集合の組は {1, 2, 3} {1, 4, 5} {2, 4, 6} {3, 5, 6} となります。この場合、Nは6になります。

さらにサイズが4になるケースを考えてみます。

{1, 2, 3, 4} {1, 5, 6, 7} {2, 5, 8, 9} {3, 6, 8, 10} {4, 7, 9,10} となります。この場合、Nは10になります。

ここで、部分集合の組の数kは部分集合のサイズより1大きい点に気づくかどうかがポイントです。

例えば {1, 2, 3, 4}を基点に考えた場合、他の部分集合との積は必ず1つしかなく、かつ、各整数は各部分集合のうち2つにしか含まれないため、他の部分集合は4つしか作れません。

どの整数も部分集合の組の2つにしか含まれないため、 となります。

よって、この条件を満たさないNが与えられた場合は、解は NO となります。

では次に、具体的な組み合わせを列挙する方法ですが、本番ではここでつまずいてしまいました。。。

以下のように考えます。

を考えた場合、これは必ずユニークな値になります。

よって、iとjを2重ループでまわして組み合わせを列挙していき、そこに整数を1つずつ当てはめていきます。その際に、各部分集合にその整数を割り当てていき、最後に各部分集合に含まれる値を出力すればよいです。

実装

n=gets.to_i

k = 0
1.upto(1000) do |i|
    if i * (i-1) / 2 == n
        k = i
        break
    elsif i * (i-1) / 2 > n
        break
    end
end

if k == 0
    puts "No"
    exit
else
    puts "Yes"
end

s = 1
ans = []
1.upto(k-1) do |i|
    (i+1).upto(k) do |j|
        ans[i] = [] if ans[i] == nil
        ans[j] = [] if ans[j] == nil
        ans[i] << s
        ans[j] << s
        s += 1
    end
end
puts k
1.upto(k) do |i|
    printf("%d ", ans[i].size)
    puts ans[i].join(" ")
end

感想

400点のCはほぼ解法がわかっていたのに、もう一歩考察が足りずにWAとなってしまいました。

500点のDも考え方はあっていたのですが、組み合わせの列挙で躓いてしまった。

ということで、またしても水色手前で足踏み状態です。

コメント

タイトルとURLをコピーしました