2019年10月19日(土)21:00~22:40に開かれました。AtCoder Beginner Contest 143に参加しました。時間内にできたのは久方ぶりです。この記事を書いているのはさらに遅いですが・・・
AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。
問題はAからFまでありだんだんと難しくなっていきます。
コンテスト開催時に参加できなかったため、手を付ける気にもなれず放置していました。
時間が空いてしまいましたが、過去問を解くつもりで再度取り組みたいと思います。
相変わらず自力だとD問題がTLE、いつになったらACできるのか。
A – Curtain
窓の長さA、カーテンの長さBのときカーテンで隠せない窓の残り部分の長さを出す。
A-2*Bがその長さだが、長さは負にならないので、負になってしまうときは0を出力する。
<?php
fscanf(STDIN, "%d %d", $a, $b);
$ans =0;
$ans = $a - 2*$b;
if($ans >= 0) {
echo $ans;
} else {
echo 0;
}
if文で書くのもいいけどmax($ans, 0)を出力すると$ansが正の場合は$ans、負の場合は0を出力してくれるのでスマートでかっこいい。
B – TAKOYAKI FESTIVAL 2019
N個のたこ焼きのうちおいしさx,yのたこ焼きを食べるとx*yの体力が回復する。
全通りの体力回復を求めて、その総和を求める問題。
N個の要素を持つ配列の2つの要素を掛け合わせたものを全部足すので、for文の中にfor文を入れる入れ子構造を作ればOK
<?php
fscanf(STDIN, "%d", $n);
$d = explode(" ", trim(fgets(STDIN)));
$ans = 0;
for($i = 0; $i < $n; $i++) {
for($j = $i+1; $j < $n; $j++) {
$ans += $d[$i] * $d[$j];
}
}
echo $ans;i=0のときj=1 ~ n-1までの回復量を求めればjがいくつになろうとi=0の場合はもう終わっているので数えなくていい。なので、例えばi=4の時はj=5から始まる。ゆえに二つ目のfor文は$j = $i + 1から始まる。
C – Slimes
隣のスライムの色が同じであれば融合、最終的に残るスライムは何匹か。
文字列Sを左から調べ、文字が変わったら融合できないので種類が1増える。
それを最後までやればOK
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%s", $s);
$fusion = 0;
for ($i = 0; $i < $n-1; $i++) {
if($s[$i] === $s[$i+1]) {
$fusion++;
}
}
echo $n - $fusion;なぜか色が変わったらカウントではなく、融合してしまったスライムの数を数えて、最後に最初にいたスライムの数から融合して消えたスライムの数を引くことで答えを出していた。
どっちのがいいのかよくわからないが、できたのでまあいいか。
D – Triangles
N本の棒から、ランダムに3本選んだ時、その3本が三角形を作ることができるかどうかを調べる問題。
三角形ができる条件は3本の棒の長さをa,b,cとすると条件は以下の通り。
- a < b + c
- b < c + a
- c < a + b
この条件があるが、ここにa<b<cをいう制約をつけると
c < a + b のみでよいことが言える。つまりa + b – c > 0
入力された数値Lをsort()すればなんとなくこの条件が使えそうだと思ったので、この条件を使ってfor文の入れ子構造を作成して解いてみる。
<?php
fscanf(STDIN, "%d", $n);
$l = explode(" ", trim(fgets(STDIN)));
sort($l);
$count = 0;
for($i = 0; $i < $n-2; $i++) {
for($j = $i+1; $j < $n-1; $j++) {
for($k = $j+1; $k < $n; $k++) {
if(($l[$i] + $l[$j] - $l[$k]) > 0) {
$count++;
} else {
break;
}
}
}
}
echo $count;入れ子構造に入れ子構造を入れているので察しの通りTLE、ここでタイムアップとなってしまったので解説を見てみる。
どうやら二分探索法を使用して解けばいいみたい。
ない脳みそ必死に絞って二分探索法ってこういうことなの？？？と思いながら頑張って実装したコードがこちら（一ミリもあってなかったけど・・・）
<?php
fscanf(STDIN, "%d", $n);
$l = array_map('intval', explode(' ', trim(fgets(STDIN))));
sort($l); // 棒の長さを短い順にソート
$count = 0;
function checkTriangle($a, $b, $c) { // $a < $b < $cの制約付き
if($a + $b - $c > 0) {
return true;
} else {
return false;
}
}
for($i = 0; $i < $n-2; $i++) {
for($j = $i+1; $j < $n-1; $j++) {
$startNumber = $j + 1; // 調査する左端を初期化
$endNumber = $n - 1; // 調査する右端を初期化
$goalNumber = floor(($j + $n) / 2); // 調べる初期値
reCheck:
if(checkTriangle($l[$i], $l[$j], $l[$goalNumber]) && !checkTriangle($l[$i], $l[$j], $l[$goalNumber + 1])) {
$count += $goalNumber - $j;
break;
} else if (checkTriangle($l[$i], $l[$j], $l[$goalNumber]) && checkTriangle($l[$i], $l[$j], $l[$goalNumber + 1])) {
$startNumber = $goalNumber;
$goalNumber = ceil(($goalNumber + $endNumber) / 2);
goto reCheck;
} else if(!checkTriangle($l[$i], $l[$j], $l[$goalNumber]) && !checkTriangle($l[$i], $l[$j], $l[$goalNumber + 1])) {
$endNumber = $goalNumber;
$goalNumber = floor(($startNumber + $goalNumber) / 2);
goto reCheck;
}
}
}
echo $count;せっかく頑張って書いてみたのに入力例すら正解を出すことができなかったので悲しくなってやめてしまいました。やめやめ。他の人のコードを参考しようとしましたが、PHPでこの問題を解けている人がまじで少なすぎたのでもういいか、ってなってしまいました。
久しくやってなかったorCまでしかとけていないのでレーティングは下がってしまいました。悲しい。
D問題がサラリと解けるようになる日が来るのだろうか。
コメント