2019年9月15日(日)21:00~22:40に開かれました。AtCoder Beginner Contest 141に取り組みました。
AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。
問題はAからFまでありだんだんと難しくなっていきます。
コンテスト開催時に参加できなかったため、手を付ける気にもなれず放置していました。
時間が空いてしまいましたが、過去問を解くつもりで再度取り組みたいと思います。
今回はD問題が解けなかったです。。。
A – Weather Prediction
晴れ、くもり、雨が周期的に変化するとき、今日の天気を教えられたら明日の天気を出力する問題。
3パターンしかないのでシンプルなif文でいいと思います。
今日が晴れなら明日はくもり → 与えられた文字列が晴れなら出力する値はくもり
<?php
$s = trim(fgets(STDIN));
if($s === "Sunny") {
echo "Cloudy";
} elseif ( $s === "Cloudy") {
echo "Rainy";
} elseif ( $s === "Rainy") {
echo "Sunny";
}B – Tap Dance
文字列Sの奇数文字目RUD、偶数文字目がLUDのいずれかになっているかを調べる問題。
文字列SはLRUDのいずれかであることが制約として決まっているので、踏みやすい文字を調べるよりも、踏みにくい文字があるかどうかを調べる方法で解いた。
$error(初期値0)に踏みにくかった文字があった場合には1を格納し、最終的に$errorが1か0かで踏みやすい文字列だったかどうかを判定する。
for文の中身は$i=0から$i<$len/2まで($lenは文字列Sの長さ)でS[$i2]とS[$i2+1]で奇数と偶数を判定する。
<?php
$s = trim(fgets(STDIN));
$len = strlen($s);
$error = 0;
for($i=0; $i<$len/2; $i++) {
if($s[$i*2] === "L") {
$error = 1;
} elseif ($s[$i*2+1] === "R") {
$error = 1;
}
}
if($error === 0) {
echo "Yes";
} else {
echo "No";
}C – Attack Survival
問題の参加者のうち正解するとポイントは保持、正解できなかったらポイントが1減る、Q回の正解が出たのちに1ポイント以上残っている人が勝ちぬけできる。
正解したらポイントそのまま、正解できなかったらポイントを減らす、とすると減らす動作でコードを書くのが難しそうだな、と思ったので正解した人にポイントを上げる方式で考えれば値を変える要素が1つで済むと思いました。
なのでarray_fill()関数を使用して、ラウンド開始時のポイントはK-Qポイント、すなわち一度も正解できなかった場合のポイント数とし、正解したら1ポイントゲット、最終的に1ポイント以上になっていれば勝ち抜け、という方法で取り組みました。
<?php
fscanf(STDIN, "%d %d %d", $n, $k, $q);
$p = array_fill(0,$n,$k-$q);
for($i=0; $i<$q; $i++) {
fscanf(STDIN, "%d", $a);
$p[$a-1] += 1;
}
for($i=0; $i<$n; $i++) {
if($p[$i] > 0){
echo "Yes"."\n";
} else {
echo "No"."\n";
}
}D – Powerful Discount Tickets
割引券は一番高いものに使いたいのが心情、なので
array_search(max($a), $a);
を使用することで何番目の品物が一番高いのかを調べ、
$a[$expensive] = floor($a[$expensive]/2);
で一番高かった品物を割引きにする。これを割引券の枚数分繰り返す。
<?php
fscanf(STDIN, "%d %d", $n, $m);
$a = explode(" ",fgets(STDIN));
for($i=0; $i<$m; $i++) {
$expensive = array_search(max($a), $a);
$a[$expensive] = floor($a[$expensive]/2);
}
echo array_sum($a);考え方としては間違ってはいないが、無事TLEとなり死亡しました。
解説を見たところやはりこの方法では時間計算量がO(NM)となり間に合いません。とのことなので優先度付きキューを使用してくださいとのこと。
しかし優先度付きキューが分からず終了してしまいました。
他の回答者のコードや適当にググって優先度付きキューについて学習したので追記
書き換えたコードはこちら(ほとんど参考にした回答者のコードそのままですが。。。)
<?php
fscanf(STDIN, "%d %d", $n, $m);
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));
$queue = new SplPriorityQueue();
for($i=0; $i<$n; $i++) {
// $queue->insert(a,b); $queueにaの値を優先度bで挿入
$queue->insert($a[$i], $a[$i]);
}
while($m) {
// $queue->extract(); $queueの最も優先度の高いキューを取り出す(取り出した後はキューから値が消える)
$max = $queue->extract();
$max = intval($max/2);
$queue->insert($max, $max);
$m--;
}
// $queue->count(); $queueの中のキュー数を数える。
$count = $queue->count();
$ans = 0;
for($i=0; $i<$count; $i++) {
$ans += $queue->extract();
}
echo $ans;優先度付きキューを使用して一番高いものを優先度の高いものとしたいため、値段をそのまま優先度として指定しました。
その優先度の最も高いものを取り出し、半額にしたら半額後の値と優先度を再びキューに再挿入。
これをチケットM枚がなくなるまでwhile文で繰り返します。
チケットがなくなったら各キューを足し合わせて終了、優先度付きキューは配列とは違うのでarray_sum()関数は使えないため注意。
余談ですが、標準入力を受け取る際にintval関数にて変換をしていないとWAとなってしまうケースが2つほど出てしまいました。テストケースの入力値が分からないので実際の値を見ることができなかったですが、今後同様の問題が出た際にはintval関数を用いて数値をint型にしておくほうが無難ですね。
コメント