「 2018年03月 」一覧

AtCoder RC093 C: Traveling Plan

問題

https://arc093.contest.atcoder.jp/tasks/arc093_a

解法

観光スポットに行かないケースを毎回計算していると、O(n^2)の計算量になってしまいます。

そこで以下のように考えます。

観光地が5カ所の場合、全ての観光地に行くケースの総距離は、

$$総距離 = |A_2 – A_1| + |A_3 – A_2| + |A_4 – A_3| + |A_5 – A_4|$$

となります。そして仮にA3に行かないとすると

$$A_3に行かない場合 = |A_2 – A_1| + |A_4 – A_2| + |A_5 – A_4|$$

となります。これは以下のように総距離からの計算することが出来ます。

$$A_3に行かない場合 = 総距離 – |A_3 – A_2| – |A_4 – A_3| + |A_4 – A_2|$$

よって、事前に総距離を計算しておけば、各ケースは定数時間で算出することが可能です。

なお、以下の実装では配列の先頭と末尾に座標0を設定することで、実装をシンプルにしています。

実装

gets
x = Array.new
x[0] = 0
gets.chomp.split(' ').each{|n| x.push(n.to_i)}
x.push(0)

total_dist = 0
for i in 0..(x.size-2)
  total_dist += (x[i+1] - x[i]).abs
end

for i in 1..(x.size-2)
  p total_dist - (x[i+1] - x[i]).abs - (x[i] - x[i-1]).abs + (x[i+1] - x[i-1]).abs
end

AtCoder RC089 C: Traveling

問題

https://arc089.contest.atcoder.jp/tasks/arc089_a

解法

時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると

・次の場所との距離(X座標とY座標の差の絶対値の和)が時刻の差に等しい

がまず最もシンプルな条件になります。

また、時刻の差が距離より大きい場合は、一旦次の場所に着いてから「隣の座標に移って戻る」を繰り返せば良いので

・次の場所との距離(X座標とY座標の差の絶対値の和)と時刻の差が正の偶数である

というのがもう一つの条件になります。

上記の条件に合うかどうかを順次チェックしていけば解けます。

実装

t = Array.new
x = Array.new
y = Array.new

t[0] = x[0] = y[0] = 0

STDIN.gets
STDIN.each_line do |line|
    n = line.chomp.split(' ')
    t.push(n[0].to_i)
    x.push(n[1].to_i)
    y.push(n[2].to_i)
end

for i in 0..t.size-2

    dist = (x[i+1] - x[i]).abs + (y[i+1] - y[i]).abs
    if dist > (t[i+1] - t[i]) || (t[i+1] - t[i] - dist) % 2 == 1 then
        puts "No"
        exit
    end
end
puts "Yes"


ABC090

AtCoder Beginner Contest 090の解説です。

A – Diagonal String

問題

https://atcoder.jp/contests/abc090/tasks/abc090_a

解説

1行目は1文字目、2行目は2文字目、3行目は3文字目を出力しておわり。

実装

3.times do |i|
  print gets.split("")[i]
end
puts

B – Palindromic Numbers

問題

https://atcoder.jp/contests/abc090/tasks/abc090_b

解説

AからBの整数について、一つずつ回文数かどうかをチェックしてカウントするだけです。

実装

A,B = gets.chomp.split.map(&:to_i)
ans = 0
A.upto(B) do |i|
  ans+=1 if i.to_s == i.to_s.reverse
end

C – Flip,Flip, and Flip……

問題

https://arc091.contest.atcoder.jp/tasks/arc091_a

解説

実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N^2)になってしまって現実的では無いです。

そのため、計算で解くことにします。

まず基本的な考え方です。最初はカードは表を向いているので、全ての操作を終えた後に「カードを偶数回操作していたら表」「カードを奇数回操作していたら裏」となります。

カードの操作回数 = カードが隣接(上下左右と斜め方向)するカードの枚数+1(自分)

これをカードの場所毎に場合分けして考えると、

・周囲が全て囲まれている場合:9回(奇数)
・四隅:4回(偶数)
・端:6回(偶数)

具体例として5×5のケースのを見てみると、以下のようになります。

偶偶偶偶偶
偶奇奇奇偶
偶奇奇奇偶
偶奇奇奇偶
偶偶偶偶偶

つまり、5x5の場合は、(5 – 2) x (5 – 2) = 9 となります。
よって、NとMが3以上の場合は、(N – 2) x (M – 2)で一般化できます。

これを表にまとめると、以下のようになります。

M
1 2 3≤
N 1 1 0 M-2
2 0 0 0
3≤ N-2 0 (N-2)x(M-2)

あとは、NとMの場合分けで実装・・・ということになるのですが、もっとシンプルにすることが出来ます。

まず、NまたはMが2の場合、(N – 2) x (M – 2) は0になります。
また、N=1かつM=1の場合は、(-1) x (-1) = 1になります。
よってこの場合は一般化した式がそのまま使えます。

残りの「N=1かつMが3以上」と「Nが3以上かつM=1」の場合ですが、これはそのまま一般化した式で計算すると値が負になるのですが、符号を反転させればそれが正解になります。

よって、全てのケースについて、(N – 2) x (M – 2) の絶対値を返すことで結果が得られます。

実装

ほぼワンライナーのようなコードになりました。

n,m=gets.chomp.split.map(&:to_i)
puts ((n-2)*(m-2)).abs

D – Remainder Reminder

問題

https://arc091.contest.atcoder.jp/tasks/arc091_b

解説

a mod b が K 以上になるN以下のa、bの組み合わせを数える問題です。

まずKが0の場合はN^2が解となるので、以降はKが1以上の場合で考えます。

bで割った余りなので、まずはbを固定して考えます。

bの取りうる範囲はK+1〜Nです。(理由:bがK以下の場合、絶対に a mod b のはK以上にならないため)

aの取りうる範囲は1〜Nですが、これに対して a mod b は次のような数列になります。

1, 2, … , b-1, 0, 1, 2, … , b-1, 0, .., N mod b

よって、このうちK以上のものの数を数えればよいです。

そしてこれを定数時間で求めることが出来れば、K+1〜Nのbに対してそれぞれ計算して合計をとれば答えになり十分間に合います。

それでは、bを固定した場合のaの数え方について続いて考えます。

前述の数列の 1, 2, …, 0 (長さb)の繰り返しに着目します。この中で、K以上のものは b-K 個です。

そして 1, 2, …, 0 の繰り返しは N/b 個出現します。

また、N/bが割り切れない場合の最後の端数の部分は 1〜N mod bとなり、このうちK以上のものはmax(0, (N mod b)-(K-1)) 個になります。

つまり、bを固定したときのaの組み合わせは、以下の式で求められます。

N/b*(b-K)+max(0, (N%b)-(K-1))

これを各b(K+1〜N)に対して計算して和をとれば解になります。

実装

N,K=gets.chomp.split.map(&:to_i)
ans=0

if K==0
  puts N*N
  exit
end

(K+1).upto(N) do |b|
  ans += N/b*(b-K)
  ans += N%b-(K-1) if N%b-(K-1) > 0
end
puts ans

GCJ 2016 Qualification Round B: Revenge of the Pancakes

問題

+ と – からなる文字列Sが与えられる。以下の操作を繰り返して、+ のみの文字列に変換するための最小回数を求める。

・文字列Sのi番目までの+と-を反転させて、なおかつ、逆順にする。

例: 文字列Sが ++–+ でi=3の場合、++- を反転(–+)して逆順(+–)にする。
 その結果、文字列Sは +—+ になる。

https://code.google.com/codejam/contest/6254486/dashboard#s=p1

方針

操作の制約として、必ず先頭から指定した範囲の文字列を反転させることになるので、最後の操作の直前の状態は、以下のように「-の連続と+の連続」または「-のみ」の状態になる。

----++++ (-の連続と+の連続)
-------- (-のみ)

つまり、文字列の前の方から順番に+や-が連続する状態を作っていくようにする。

・先頭が+の場合、順番に文字をチェックしていき、-が出現したら直前までの文字列に対して操作を行う

+++--++
↓ 先頭が+なので4番目に-を見つけた時点で3番目までを操作対象にする
-----++

・先頭が-の場合、上記の逆の操作をする

以上を繰り返すと、文字列の前半が+の連続、-の連続を交互に繰り返すことになり、最終的に+のみになったら処理終了となる。

実装

最初は文字列を実際に反転させる処理を実装し、毎回文字列を先頭からチェックするような実装にしていた。(計算量は O(N^2))

しかしながら、動作確認をしていて、i番目までを処理した時点でそれより前の文字列は + or – の連続になっていることは分かっているので、先頭に戻らずそのままi番目以降の文字をチェックすれば良いことに気づいた。(計算量は O(N))

def solve(cakes)
    n = cakes.size
    return 0 if cakes.count{|c|  c == "+" } == n

    c = cakes[0]
    count = 0
    i = 1
    while(i < n)
        if cakes[i] != c then
            count += 1
            c = (c == "+" ? "-" : "+")
        end
        i += 1
    end
    count += 1 if c == "-" 
    return count
end

i = 1
STDIN.gets
STDIN.each_line do |line|
    line.chomp!
    cakes = Array.new
    line.chars {|c| cakes.push(c)}

    printf("Case #%d: %d\n", i, solve(cakes))
    i += 1
end

GCJ 2016 Qualification Round A: Counting Sheep

問題

与えられた非負整数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が全て出そろうので、結果は 90 となる。

https://code.google.com/codejam/contest/6254486/dashboard

方針

特に最適な解法というのが思いつかなかったので、単純にNの倍数を上げていきチェックする方法をとった。

なお、INSOMNIA になる条件は N=0 の場合とした。

実装

require 'set'

def solve(n)
    return 0 if n == 0

    digits = Set.new
    i = n
    while(true)
        i.to_s(10).chars { |c| digits.add(c) }
        return i if digits.size == 10
        i += n
    end
end

STDIN.gets

i = 1
STDIN.each_line {|line|
    ret = solve(line.to_i)
    if ret == 0 then
        printf "Case #%d: INSOMNIA\n", i
    else
        printf "Case #%d: %d\n", i, ret
    end
    i += 1
}