2019年9月7日(土)21:00~22:40に開かれました。AtCoder Beginner Contest 140に取り組みました。
AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。
問題はAからFまでありだんだんと難しくなっていきます。
コンテスト開催時に参加できなかったため、手を付ける気にもなれず放置していました。
時間が空いてしまいましたが、過去問を解くつもりで再度取り組みたいと思います。
とはいえ、D問題からは解説を見ながら解いてますが・・・。
A – Password
3桁のパスワードを設定し、使える文字は1以上N以下の数字のみ。
1桁目：N通り
2桁目：N通り
3桁目：N通り
なのでNNNのN^3通りが答え。
$n * $n * $nでもいいが、pow()関数を使用するとちょっとできる風なのでつかってもいいかも。
B – Buffet
N種類の料理を一度ずつ食べ、その満足度の合計を求める。
満足度は
・料理を食べる
・i番目の料理の後にi+1番目の料理を食べると追加で満足度を得る
満足度Bに関しては料理を一度ずつ食べるのが決まっているため、Bを配列に入れて、その合計をarray_sum()関数にて合計を求めた。
満足度Cは決められた順番にのみ満足度が追加される。
ある料理を食べた次の料理の種類が+1されていると満足度Cが得られるため、食べた順番$a[]にて、
$a[$i] + 1 === $a[$i+1]
となっていれば満足度Cを得られる。
<?php
fscanf(STDIN, "%d", $n);
$a = explode(" ",fgets(STDIN));
$b = explode(" ",fgets(STDIN));
$c = explode(" ",fgets(STDIN));
$a = array_map("intval", $a);
$b = array_map("intval", $b);
$c = array_map("intval", $c);
$bs = array_sum($b);
$cs = 0;
$s = 0;
for ($i=0; $i<$n-1; $i++) {
if($a[$i]+1 === $a[$i+1]) {
$cs += $c[$a[$i]-1];
}
}
$s = $bs + $cs;
echo $s;
C – Maximal Value
Bi >= max(Ai, Ai+1)を常に満たす数列Aiの最大値を求める。
言い換えるとAiはBiとBi-1の小さいほうが取り得る最大の値になるので、BiとBi-1を比較して小さいほうをAiに格納(回答ではBiとBi+1になってます。)
<?php
fscanf(STDIN, "%d", $n);
$b = explode(" ",fgets(STDIN));
$a = array();
$b = array_map("intval", $b);
$a[0] = $b[0];
for($i=0; $i<$n-2; $i++) {
if($b[$i]<$b[$i+1]) {
$a[$i+1] = $b[$i];
} else {
$a[$i+1] = $b[$i+1];
}
}
$a[$n-1] = $b[$n-2];
$maxA = array_sum($a);
echo $maxA;
D – Face Produces Unhappiness
L,Rはその人の向いている向きを表しており、前の人が同じほうを向いているとその人は幸福になります。
例えば、LLとなっていれば右のLの人は幸福、RRRとなっていれば左と真ん中の二人が幸福です。端は前に人がいなければ幸福になれません。
結論から言うとLLRLのような列を考えたときに幸福でないRの人に着目するとわかりやすいです。
このRの人がLになることで幸福になる人はR本人と一番右にいるLの人です。
これはLLRRRRRRRRRLの様になっていたとしてもRの列を一人のRとして考えれば同じことで一度の回転で新しく幸福になれる人の数は最大でも2人しかいません。
幸福にしたい人の数を増やしたいので一度操作するたびに2人ずつ増やしていくのが当然の流れ。
最初に幸福な人の数を数え、その後操作の回数*2を足し合わせればそれが求める答えになります。
もしも全員が幸福になったとした時のことを考えてmin(操作後の幸福な人,人数-1)としておけばOK。
<?php
fscanf(STDIN, "%d %d", $n, $k);
$s = trim(fgets(STDIN));
$arrayS = str_split($s);
$h = 0;
for($i=0; $i<$n-1; $i++) {
if($arrayS[$i] == $arrayS[$i+1]) {
$h++;
}
}
$h = $h + 2*$k;
echo min($h,$n-1);E問題、F問題に関しては依然取り組めていないです。時間を見つけて解説を見ながらでも解けるようにしていきたいですね。
コメント