2019年8月18日(日)21:00~22:40に開かれました。AtCoder Beginner Contest 138に参加しました。
AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。
問題はAからFまでありだんだんと難しくなっていきます。
今回で4回目の参戦になります。
前回のABC137ではCの解答がTLEになってしまい終了となってしまったため、今回こそはCをクリアしつつDに挑みたいところ。
A Red or Not
入力値aが3200以上であればsをそれ以外であればredと出力するif分を作成。
B Resistors in Parallel
配列に入力値を格納、for文で配列[i] = 1/配列[i]として代入しなおし変数$ansとしてこれに足していく。
最終的に$ansの逆数が答えになります。
C Alchemist
入力例にもあるけど、こういう問題であれば入力される数が少なかったらどうなるかを考えるとイメージがしやすくなると思う。
2個であれば足して÷２するだけで終了。
3個の場合(a,b,c)の場合
(a/2+b/2)/2+c/2=a/4+b/4+c/2となるのでcが一番大きければOK
入力値は必ずどこかで2で割られるので、価値の高い具材(数字が一番大きいもの)はなるべくその価値を残しておくために最後に鍋に入れたい。
とすると価値の低い具材同士から鍋に入れてできた具材とその次に価値の低い具材を鍋に入れていけば最終的に残る具材の価値が最大化されるはず！
というわけで入力値を配列に格納し、sortで配列内を小さい順に並び替えをする。
その後、配列[i+1]に要素[i]と[i+1]の平均を入れることで小さい具材同士を鍋に入れて生成されていくことになると思います。
<?php
fscanf(STDIN, "%d", $n);
$v = explode(" ",fgets(STDIN));
for($i=0; $i<$n; $i++) {
$v[$i] = intval($v[$i]);
}
sort($v);
for($i=0; $i<$n-1; $i++) {
$v[$i+1] = ($v[$i]+$v[$i+1])/2;
}
echo $v[$n-1];
?>この解答をするときに
$v[$i] = intval($v[$i]);
を入れなかった場合、テストケースで一つだけWAとなってしまった。型はいまだによくわからん。
D Ki
残念ながらこの問題で時間切れ、相変わらずDが解けない。
考えとしては節点が持つ値を上から足し合わせていけばいい、ということには気づいたのですがいかんせん技術力不足と発想力がなくてプログラムでどう実現すればいいのかわからなかった。
今回の成績
Cまで解けたといってもレートはあまり上がらないですね、、、
本当に上げようと思うなら過去問に取り組みながらD、Eも解けるようにしていかないと
(そもそもコンテストが開催される時しかやってないので腕が上がるはずもない)
コツコツ地道にやっていきたいと思います。
それではまた次回
コメント