AtCoder Beginner Contest #011

ProgrammingContest

AtCoder Beginner Contest #011

今日DP教えてもらったので頑張りました

A問題

何も考えずに実装しました。 （余りを使うとかそんな発想全くなかった）

#!/usr/bin/perl

use strict;
use warnings;

my $N = <STDIN>;
chomp($N);
$N++;
$N = 1 if $N == 13;

print $N."\n";

B問題

Googleに頼り切った解答です。 他の人のを見ると正規表現とかで書けるっぽいですね。

#!/usr/bin/perl

use strict;
use warnings;

my $S = <STDIN>;
chomp($S);

$S = ucfirst(lc($S));

print "$S\n";

C問題

頑張ったやつ。 1から考えてDP使えたの初めてかもしれない。 一番外のループは0〜100まで回さないといけないので、継続条件は$i < 101か$i <= 100ですね。 一回間違えて$i < 100としてしまいWA出しました。 くやしい。

#!/usr/bin/perl

use strict;
use warnings;

my $N = <STDIN>;
chomp($N);
my @NG = ();
my $buf = <STDIN>;
chomp($buf);
push(@NG, $buf);
$buf = <STDIN>;
chomp($buf);
push(@NG, $buf);
$buf = <STDIN>;
chomp($buf);
push(@NG, $buf);

my @dp;
for (my $i = 0; $i < 101; $i++) {
    for (my $j = 0; $j < 301; $j++) {
        $dp[$i][$j] = 0;
    }
}
$dp[0][$N] = 1;
for (my $i = 1; $i < 101; $i++) {
    for (my $j = 0; $j < 301; $j++) {
        for (my $k = 1; $k < 4; $k++) {
            next if ($j + $k > 300);
            next if ($j + $k == $NG[0]);
            next if ($j + $k == $NG[1]);
            next if ($j + $k == $NG[2]);
            $dp[$i][$j] = $dp[$i - 1][$j + $k] | $dp[$i][$j];
        }
    }
}
for (my $i = 0; $i < 101; $i++) {
    if ($dp[$i][0] == 1) {
        print "YES\n";
        exit;
    }
}
print "NO\n";

D問題

これもDPで解こうとしました。 最初、ゴールを含むギリギリの領域しか考慮していなかったせいで上手くいかず超悩みました。 間違えてることに気付いて修正しようとしたんですが、それっぽい解答は出たものの結局解けず。 ACとWAとTLEが入り交じってたので、計算量的に間に合わないのと、ループの範囲を間違えてる可能性が高い気がします。 以下は間違えているコードなので参考にしないでください。

#!/usr/bin/perl

use strict;
use warnings;

my $buf = <STDIN>;
chomp($buf);
my ($N, $D) = split(/ /, $buf);
$buf = <STDIN>;
chomp($buf);
my ($X, $Y) = split(/ /, $buf);

if ($X % $D != 0 || $Y % $D != 0) {
    print "0.0\n";
    exit;
}
$X = $X / $D;
$Y = $Y / $D;

my @dp;
for(my $i = 0; $i < $N + 1; $i++) {
    for (my $j = 0; $j < abs($X) * 2 + 5; $j++) {
        for (my $k = 0; $k < abs($Y) * 2 + 5; $k++) {
            $dp[$i][$j][$k] = 0;
        }
    }
}
$dp[0][abs($X) / 2 + 1][abs($Y) / 2 + 1] = 1.0;

for(my $i = 0; $i < $N; $i++) {
    for (my $j = 0; $j < abs($X) * 2 + 5; $j++) {
        for (my $k = 0; $k < abs($Y) * 2 + 5; $k++) {
            $dp[$i + 1][$j - 1][$k] = $dp[$i + 1][$j - 1][$k] + ($dp[$i][$j][$k] * 0.25) if ($j - 1 >= 0);
            $dp[$i + 1][$j + 1][$k] = $dp[$i + 1][$j + 1][$k] + ($dp[$i][$j][$k] * 0.25) if ($j + 1 <= abs($X) * 2 + 4);
            $dp[$i + 1][$j][$k - 1] = $dp[$i + 1][$j][$k - 1] + ($dp[$i][$j][$k] * 0.25) if ($k - 1 >= 0);
            $dp[$i + 1][$j][$k + 1] = $dp[$i + 1][$j][$k + 1] + ($dp[$i][$j][$k] * 0.25) if ($k + 1 <= abs($Y) * 2 + 4);
        }
    }
}
print $dp[$N][(abs($X) / 2 + 1) + $X][(abs($Y) / 2 + 1) + $Y], "\n";

直した

100点の解答です。 考慮する領域の設定ミスと異常値の判定忘れが原因でした。 最初X,Yのギリギリの領域さえ計算すればいいかと考えて実装してしまったんですが、それだとゴールを通り過ぎてまた戻ってくるパターンが計算されなくてWAになります。 正しい領域設定は、ルール上可能な限り遠くまで移動した場合の位置を含む領域なので、X,Yそれぞれ-N〜Nまでを領域にします。 ただし、それだけだとNよりも遠い位置にゴールがあった場合に領域外参照してしまうので、その辺のチェックを入れましょう。

101点にするにはN=1000を解けないといけませんが、このコードだとたぶんO(N3)（もっと大きいかも）で制限時間内に計算が終わらないので、DPじゃなくて数学的な解き方をする必要があるらしいです。 よくわかりません。

#!/usr/bin/perl

use strict;
use warnings;

my $buf = <STDIN>;
chomp($buf);
my ($N, $D) = split(/ /, $buf);
$buf = <STDIN>;
chomp($buf);
my ($X, $Y) = split(/ /, $buf);

if ($X % $D != 0 || $Y % $D != 0) {
    print "0.0\n";
    exit;
}
$X = ($X / $D) + $N;
$Y = ($Y / $D) + $N;
if ($X < 0 || $Y < 0 || $X > $N * 2 || $Y > $N * 2) {
    print "0.0\n";
    exit;
}

my @dp;
for(my $i = 0; $i < $N + 1; $i++) {
    for (my $j = 0; $j < $N * 2 + 1; $j++) {
        for (my $k = 0; $k < $N * 2 + 1; $k++) {
            $dp[$i][$j][$k] = 0;
        }
    }
}
$dp[0][$N][$N] = 1.0;

for(my $i = 0; $i < $N; $i++) {
    for (my $j = 0; $j < $N * 2 + 1; $j++) {
        for (my $k = 0; $k < $N * 2 + 1; $k++) {
            $dp[$i + 1][$j - 1][$k] = $dp[$i + 1][$j - 1][$k] + ($dp[$i][$j][$k] * 0.25) if ($j - 1 >= 0);
            $dp[$i + 1][$j + 1][$k] = $dp[$i + 1][$j + 1][$k] + ($dp[$i][$j][$k] * 0.25) if ($j + 1 <= $N * 2);
            $dp[$i + 1][$j][$k - 1] = $dp[$i + 1][$j][$k - 1] + ($dp[$i][$j][$k] * 0.25) if ($k - 1 >= 0);
            $dp[$i + 1][$j][$k + 1] = $dp[$i + 1][$j][$k + 1] + ($dp[$i][$j][$k] * 0.25) if ($k + 1 <= $N * 2);
        }
    }
}
print $dp[$N][$X][$Y], "\n";

感想

やっと簡単なDPが使えるようになった。 Cは貪欲法で解いてる人が多いみたいなので、そっちも難なく扱えるようにしたい。 Dみたいな満点取るには数学的な発想が必要になる問題はまだ難しい。