AtCoder Tenka1 Programmer Beginner Contest 参戦記

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

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

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

A - Measure

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a

解法

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

実装

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

B - Exchange

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b

解法

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

実装

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

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

解法

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

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

例えば、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で表すとすると、 $s_1 \geq s_2 \leq s_3 \geq s_4 .... s_N$ のような凸凹の並びになります。

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

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

すると、 $s_1 \leq s_2 \geq s_3 \leq s_4 \geq s_5 \leq s_6$ と $s_1 \geq s_2 \leq s_3 \geq s_4 \leq s_5 \geq s_6$ が考えられます。

それぞれの計算結果は

$2 \times s_2 + 2 \times s_4 + s_6 - 2 \times s_3 - 2 \times s_5 - s_1$

$2 \times s_3 + 2 \times s_5 + s_1 - 2 \times s_2 - 2 \times s_4 - s_6$

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

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

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

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

今度は、 $s_1 \leq s_2 \geq s_3 \leq s_4 \geq s_5$ と $s_1 \geq s_2 \leq s_3 \geq s_4 \leq s_5$ が考えられます。

それぞれの計算結果は

$2 \times s_2 + 2 \times s_4 - 2 \times s_3 - s_5 - s_1$

$2 \times s_3 + s_5 + s_1 - 2 \times s_2 - 2 \times s_4$

となり、両者は異なります。これは、並びの両端に大きい数を配置するか小さい数を配置するかの違いになります。（本番では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

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d

解法

満たすべき条件の対称性や入力例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 = k \times (k-1) \div 2$ となります。

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

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

以下のように考えます。

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

よって、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