2019年9月28日(日)21:00~22:40に開かれました。AtCoder Beginner Contest 141に取り組みました。
AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。
問題はAからFまでありだんだんと難しくなっていきます。
コンテスト開催時に参加できなかったため、手を付ける気にもなれず放置していました。
時間が空いてしまいましたが、過去問を解くつもりで再度取り組みたいと思います。
相変わらず自力だとD問題がACにならない。。。
A – Odds of Oddness
整数Nの中からランダムに1つの数字aを選んだ時のaが奇数である確率
奇数か偶数かのいずれかなので確率は2分の1、ではなく、Nが奇数の場合は奇数の数が偶数の数より1つ多いため確率が少し違う。
Nが偶数の時は奇数の数はN/2個、Nが奇数の時は奇数の数はN/2の商+1個ある。
これをそのまま実装すると
<?php
fscanf(STDIN, "%d", $n);
if ($n % 2 === 0) {
$oddNum = $n / 2;
echo $oddNum / $n;
} else if($n % 2 === 1) {
$oddNum = intdiv($n, 2) + 1;
echo $oddNum / $n;
}ただ少し長いのでスッキリさせたいならNが奇数であろうと偶数であろうとceil()関数を使用すれば、ceil(N/2)で奇数の数になる。
B – Roller Coaster
要は、N個の中の要素からK以上のものが何個あるかを調べる問題。
for文でi番目の値がK以上であれば$ansを1追加、最終的な$ansが答え
<?php
fscanf(STDIN, "%d %d", $n, $k);
$h = explode(" ",fgets(STDIN));
$ans = 0;
for($i=0; $i<$n; $i++) {
if($h[$i] >= $k) {
$ans++;
}
}
echo $ans;こういう問題はfor文で解きがちだけど実際はforeach文を使ったほうがいいのか、ぱっと見ほかの人の解答コードを見ると大体の人がforeach文を使用している。for文使いがちなのでforeachも使っていきたいなとは思っている。
C – Go to School
生徒の登校した順番を知りたい。出席番号iの生徒が投稿した時点でAi人の生徒がいる(iの生徒を含む)ということなので、Aiを昇順に並べると教室にいた生徒の数が1人ずつ増えていく並びになる。その時のAiのキーが登校した順番を表しているにすぎない。
<?php
fscanf(STDIN, "%d", $n);
$a = explode(" ",(trim(fgets(STDIN))));
asort($a);
foreach($a as $key => $value) {
echo ($key+1) . " ";
}まずAをソートするが、ソート後の値とキーの関係は崩したくないのでsort()ではなくasort()を使用する。
あとは配列のキーの並びが答えそのものになっているためキーを取得できるforeach文を使用。
D – Disjoint Set of Common Divisors
正の整数A,Bの公約数からいくつか選び、選んだ整数の中のどの異なる2つの整数についても互いに素でなければいけない。
なんか難しそうなこと言ってるけど入力例1を見たら何となくイメージがつかめた。12と18の公約数が1,2,3,6のとき、これらをどのように2つ選んでも互いに素になるように抜き出す。
つまりA,Bの素数の中で共通のものが答え。
<?php
fscanf(STDIN, "%d %d", $a, $b);
$init = 2;
while ($a !== 1) {
$i = $init; while ($i < 0xFFFFFF) {
if ($a % $i == 0) {
$resultA[] = $i;
$a /= $i;
break;
} $i++;
}
$init = $i; }
$resultA = array_unique($resultA);
$init = 2;
while ($b !== 1) {
$i = $init; while ($i < 0xFFFFFF) {
if ($b % $i == 0) {
$resultB[] = $i;
$b /= $i;
break;
} $i++;
}
$init = $i; }
$resultB = array_unique($resultB);
$primeNumber = array_intersect($resultA, $resultB);
echo count($primeNumber) + 1;A,Bに対して素因数分解を行ったのち、素数のみを取り出したいのでarray_unique()関数を使用、その後array_intersect()関数を使用して共通の要素を抜き出す。最後に1を足してこれが答え。
phpで素数を求める方法が分からなかったので、適当にググって出てきた記事を参考にしつつ、実装したコードがこちら、無事TLE。
考え方は間違っていないが、A,Bが非常に数の大きい素数だった場合にループが長くなってしまうと思われる。
じゃあどうするか、とりあえず解説とほかの人の解答を見る。なので0xFFFFFFをceil(sqrt($a))に変えてみたが変わらずTLE(むしろ悪くなった？)
コメント