📌

AtCoder Beginner Contest 064 C - Colorful Leaderboard 覚書 PHP

2024/05/01に公開

競技プログラミング

tech

PHPで解答を作成しています。
初期の問題でした。今のAtCoderと比較して計算量は気にならない問題でした。
200番以上の問題を解いた方が良いのだろうか。

問題のリンク

こちらを参考にしました。
Colorful Leaderboard [AtCoder Beginner Contest 064 C]

解のポイント

区間をもっておくときは片方だけを配列にするといい
$line = array(1, 400, 800, 1200, 1600, 2000, 2400, 2800, 5050);
3200以上の数をカウントしておく
最小、最大、極端な例ではどうなるのかを考える
今回は全ての数が3200以上の場合、3200以下の数が保持する色が0、そして3200以上の数の色の種類は最小が1であり、少し計算が変わってしまう。
これを判断に盛り込まないといけない。
$min = max(count($ color), 1); // 色の種類の最小値は、$colorの数、もしくは1

使用する関数/演算子

array_unique
配列の重複を削除しその結果を配列として返す

max
$min = max(count($ color), 1);
配列 $colorの要素数と1のうち、大きい方の値を変数$ minに代入する

continue
現在のループ反復処理を終了して次の反復処理に進む。
ループからは抜けない。

全体コード

<?php
$line = array(1, 400, 800, 1200, 1600, 2000, 2400, 2800, 5050);


$N = trim(fgets(STDIN));
$A = array_map('intval', explode(' ', trim(fgets(STDIN))));

$color = array(); // $Aのそれぞれの値がどのレート=色かを格納する配列
$non = 0; // 3200以上の人数

// 3200以上の人数をカウント
foreach ($A as $a) {
  if ($a >= 3200) {
    $non++;
    continue;    
  }

  for ($j = 0; $j < 8; $j++) {
    // $lineの中で、$aがどの範囲に入るかを調べる
    // もし、$a=レートが$line[$j]以上$line[$j+1]未満なら、$colorに$jを追加
    if ($a >= $line[$j] && $a < $line[$j + 1]) {
      $color[] = $j;
    }
  }
}

// この時点で、$colorには、$Aのそれぞれの値がどのレート=色かが格納されている

$color = array_unique($color); // 配列の重複を削除しその結果を配列として返す
$max = count($color) + $non; // 数の種類の最大値は、$colorの数+3200以上の人数:なぜなら3200以上の人は、どの色でも良いから
$min = max(count($color), 1); // 色の種類の最小値は、$colorの数、もしくは1
echo "$min $max\n";

解のポイント

使用する関数/演算子

全体コード

Discussion