🌊

AtCoder Beginner Contest 343 C - Sum of Numbers Greater Than 備忘録 PHP

2024/05/25に公開

AtCoder

tech

PHPで解いています。

問題はこちら。

解のポイント

累積和は後ろから

１つの値にたいして、値をいくつか格納して何かを確認したいとき
→連想配列に複数の値を格納する

配列に値が存在しなければ新規の配列を作る
→issetが便利

使った関数、演算子

isset:
変数が宣言されていること、そして null とは異なることを検査する。

$d[$ a][] = $i;

$d[$ a] を配列とみなし、その配列の末尾に値 $i を追加する
$d[$ a]に対し、複数の値を格納していくときに使う

例えば…

$d = [
    3 => [0],
    1 => [1, 3],
    4 => [2],
    5 => [4]
];

krsort
配列をキーで降順にソートする

全体コード

※後で自分で復習しやすいようにコメントを多めにいれています

<?php
$N = trim(fgets(STDIN));
$input = trim(fgets(STDIN));
$A = explode(' ', $input);

$d = array();
foreach($A as $i => $a){
    // $aをキーにして、$iを値に持つ配列を作る
    // もし、$aがキーとして存在しない場合は、$aをキーにして空の配列を作る
    if(!isset($d[$a])){
        $d[$a] = array();
    }
    // $aをキーにして、$iを値に持つ配列に$iを追加する
    // 複数の値を持つ配列を作るので $d[$a][]という形にする
    $d[$a][] = $i;
}

// $ans配列を$N個の0で初期化する
$ans = array_fill(0, $N, 0);

// 累積和を保管する変数$sを0で初期化する
$s = 0;

// $dをキーで降順にソートする:大きい順に累積和を計算するため
krsort($d);

foreach($d as $v => $i_list){
    foreach($i_list as $i){
        $ans[$i] = $s;
    }
    // $i_listに入っている値の数だけ$vを足す
    $s += $v * count($i_list);
}

echo implode(' ', $ans) . "\n";

解のポイント

使った関数、演算子

全体コード

Discussion