「 2018年11月 」一覧

AtCoder BC074 D: Restoring Road Network

問題

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

解法

ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。

問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて考えます。

  • 道路の構造が存在するかどうか

表Aが「都市間の道路に沿った最短距離を表した表」なので、表Aに対してワーシャルフロイド法を適用し、表内の値が更新されることがあった場合に表Aは矛盾することになります。

例えば、(iからjへの距離)> (iからkへの距離)+(kからjへの距離)のような場合に、表Aはそもそも矛盾することになります。

よってそのような組み合わせが一つでもあれば、’-1’を出力して終了すれば良いです。

  • 存在する道路の長さの和が最小となるようなもの

どのような場合に道路が存在しないといけないかを考えます。

表Aは各都市間の最短経路を表しているので、iからjへの経路を考える場合、

(iからjへの距離)= (iからkへの距離)+(kからjへの距離)

のようなkが存在した場合、k経由で迂回しても距離は変わらないので、iからjへの道路は不要ということになります。

よって、表のサイズと同じ表を用意しておき、道路が必要か不要かをtrue/falseなどで記憶しておき、最後にtrueな経路の距離だけ加算すればよいです。

実装

#include<iostream>

#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;

    ll a[N][N];
    bool f[N][N];

    REP(i,N)REP(j,N)cin >> a[i][j];
    REP(i,N)REP(j,N)f[i][j] = true;

    REP(k,N)REP(i,N)REP(j,N){
        if(a[i][k] + a[k][j] < a[i][j]){
            cout << -1 << endl;
            return 0;
        }else if(a[i][k] + a[k][j] == a[i][j] && i != k && k != j){
            f[i][j] = false;
        }
    }

    ll ans = 0;
    REP(i,N)REP(j,N){
        if(f[i][j])ans+=a[i][j];
    }

    cout << ans / 2 << endl;
}

AtCoder BC074 C: Sugar Water

問題

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

解法

質量の合計の最大値が3000gに対して、水は100g単位、砂糖は1g単位です。

なので、全ての組み合わせを試したとしても間に合います。

よって、4重ループで全探索すれば解けます。

実装

A, B, C, D, E, F = gets.chomp.split(" ").map(&:to_i)

limit = E.to_f / (100 + E)

tmp = 0
max_s =0
max_sw = 0
for a in 0..(F/100/A)
    for b in 0..((F-100*a*A)/100/B)
        next if a + b == 0
        for c in 0..((F-100*a*A-100*b*B)/C)
            for d in 0..((F-100*a*A-100*b*B-c*C)/D)
                sw = c*C+d*D+a*A*100+b*A*100
                s = c*C+d*D
                n = s.to_f / sw
                break if n > limit
                if tmp < n
                    tmp = n
                    max_s = s
                    max_sw = sw
                end
            end
        end
    end
end
if max_s > 0
    puts "#{max_sw} #{max_s}"
else
    puts "#{100*A} #{max_s}"
end

AtCoder Beginner Contest 113 参戦記

今度こそは水色へ、と意気込んだABC113。

C完でDも解法はある程度わかったのですが、実装で手間取って例題を通す前に時間切れとなりました。

うーん、水色目前で停滞中です。

A – Discount Fare

問題

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

解法

X + (Y/2) を出力するだけ

実装

x,y=gets.chomp.split.map(&:to_i)
puts x+y/2

B – Palace

問題

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

解法

各Hi毎に平均気温とA度との差の絶対値を計算し、それが最小の時のiを出力すればよい。

実装

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

m=Float::INFINITY
ans=0
h.each_with_index do |v, i|
    mm = (a-(t-v*0.006)).abs
    if mm < m
        ans = i+1
        m = mm
    end
end
puts ans

C – ID

問題

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

解法

各市を読み込みながら、各県に誕生年を振り分けていく。

全て読み込んだら、各県毎の誕生年をソートして各市の順番(x番目)を決定する。

最後に各市毎に認識番号を出力していく。

ということで、考え方自体はそんなに難しくないが、誕生年の順番をどのように知るかにちょっと工夫が必要。

実装

実装としては、配列とハッシュを使って以下のようにした。

まず、各県ごとに誕生年を配列に格納してから最後にソートする。

その後、配列を先頭から見ていき、誕生年をキー、順番を値とするハッシュに格納する。

認識番号を決める際はこのハッシュを使って誕生年から順番を取得するようにする。

n,m=gets.chomp.split.map(&:to_i)
p = []
y = []

py = Array.new(n+1).map{Array.new()}

m.times do |i|
    pp, yy = gets.chomp.split.map(&:to_i)
    p << pp
    y << yy

    py[pp] << yy
end

ph = Array.new(n+1).map{Hash.new()}
py.each_with_index do |v, i|
    v.sort!
    v.each_with_index do |vv, j|
        ph[i][vv] = j+1
    end
end

0.upto(m-1) do |i|
    printf("%06d%06d\n", p[i], ph[p[i]][y[i]])
end

D – Number of Amidakuji

問題

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

解法

あと一歩で解けなかったD問題。

取りかかってから10分ぐらいで動的計画法を使うっていうのは分かったんだけど、実装に手間取って例5を通すことが出来なかった。

この問題のポイントは、動的計画法の漸化式をどうたてるか、と、各縦線の数に対して有効な横線の引き方が1段について何通りあるか、です。

  • 漸化式の考え方

i番目の行まで横線が引き終わっている時にj列目に存在するときの組み合わせをDP[i][j]とします。

すると、i+1番目でj列にいく組み合わせは

DP[i+1][j] = DP[i][j-1] x (j-1とjの間に線を引くときの組み合わせ)+ DP[i][j] x (j-1とjとj+1の間に線を引かない組み合わせ)+ DP[i][j+1] x (jとj+1の間に線を引くときの組み合わせ)

で求められます。

例を使って説明します。

i+1番目で4列目にいけるのは、i番目で3列目、4列目、5列目にいる場合です。

3列目にいる場合は、3列目と4列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、2列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。

4列目にいる場合は、3列目と4列目、及び、4列目と5列目の間に横線を引いてはいけません。この場合、それ以外の場所については、左側は1、3列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。

5列目にいる場合は、4列目と5列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、3列目の間、右側はこれ以上横線は引けません。

  • 有効な横線の引き方

では、あみだくじとして有効な横線の引き方をどう算出するかです。

これも漸化式の考え方で求めることが出来ます。

縦棒の数がi本の時の一行分の線の引き方をSiとします。

このとき、漸化式は以下のようになります。

これは、i列目とi+1列目に横棒を引く場合はi-1列目とi列目に横棒は引けないのでそれより左側の組み合わせはSi-1通りとなり、i列目とi+1列目に横棒を引かない場合はそれより左側の組み合わせはSi通りになるためです。

ちなみにこれはフィボナッチ数列になります。なお、今回の問題は縦棒は8本までしかないので、数列はハードコードしてしまってます。

実装

以下の実装では、左端と右端は場合分けしていますが、両端に0の列を追加すればもう少し綺麗なるかも。

h,w,k=gets.chomp.split.map(&:to_i)
dp=Array.new(h+1).map{Array.new(w)}

MOD = 1000000007

nn = [1,2,3,5,8,13,21,34]

dp[0][0] = 1
1.upto(w-1) do |i|
    dp[0][i] = 0
end

if w == 1
    puts 1
    exit
end

1.upto(h) do |i|
    0.upto(w-1) do |j|
        dp[i][j] = 0
        if(j==0)
            dp[i][j] += dp[i-1][j] * nn[w-2]
            dp[i][j] += dp[i-1][j+1] * nn[[0,w-3].max]
        elsif(j==w-1)
            dp[i][j] += dp[i-1][j] * nn[w-2]
            dp[i][j] += dp[i-1][j-1] * nn[[0,w-3].max]
        else
            n = nn[[0,j-2].max]
            n *= nn[[0,w-2-j].max]
            dp[i][j] += dp[i-1][j-1] * n

            n = nn[j-1]
            n *= nn[[0,w-2-j].max]
            dp[i][j] += dp[i-1][j] * n

            n = nn[j-1]
            n *= nn[[0,w-3-j].max]
            dp[i][j] += dp[i-1][j+1] * n
        end
        dp[i][j] = dp[i][j] % MOD
    end
end

puts dp[h][k-1] % MOD

結果

Cまでは順調だったんですが、Dで躓いてしまいました。

しかも、Dは動的計画法の漸化式まではある程度思いついたんですが、結局実装しきれませんでした。

とはいえ、動的計画法は苦手分野だったので、途中まで書けただけでも成長したかなという感じです。

いずれにせよ、水色手前でなかなか上がれません。

やはり400点問題は確実に解けるようにしたいところですね。