ABC325（AtCoder Beginner Contest 325）を解いてみた

# はじめに
先日初めて**競技プログラミング**というものに挑戦してみたので、今回は取り組んだ問題と私の解答を紹介します。

## 競技プログラミングとは
>「競技プログラミング」とは、プログラミングの能力や技術を競い合うコンテストの一つです。
大会では、参加者にコンピュータサイエンスや数学などをテーマにした同じ課題が出題され、この要求を満たすプログラミングを早く、正確に記述することを競います。

「競技プログラミング」と聞いた時には、まだ駆け出しエンジニアの私が参加するようなものではないのでは？と思ってしまいましたが、そんなことはありませんでした。


## AtCoderとは
>日本のAtCoderは、問題が日本語で提供されることもあり、国内で数千人が参加する人気の高い競技プログラミング大会です。
AtCoderには定期開催コンテストのほか、初心者/初級者向けの「AtCoder Beginner Contest」(ABC)、中級者/上級者向けの「AtCoder Regular Contest」 (ARC)、上級者向けの「AtCoder Grand Contest」 (AGC)などがあります。
AGCでは上位8名が「AtCoder World Tour Final」に進出できます。


公式：[AtCoder.jp](https://atcoder.jp/?lang=ja)
参考：[競技人口が増加中！ いま注目の「競技プログラミング」の世界とは？](https://www.qbook.jp/column/1420.html)

上記にあるように、私が参加した AtCoder の大会では、レベル別にコンテストが開かれており、初心者でも参加できるような形式になっています。
無料で参加でき、オンラインで100分程の制限時間内に多くの問題を正確に解答することを競います。

初心者向けのコンテストの中でも、A 問題から G 問題の７問、簡単な問題から難しい問題まで段階別に準備されているので、「まずは B 問題まで解けるように頑張ろう！」といった目標を立てて取り組むことができます。

## 参加したコンテスト
今回私が参加したのは、2023年10月25日（土）に開催された、キーエンスプログラミングコンテスト2023秋 - AtCoder Beginner Contest 325（略称 ABC 325 ）です。
ABC には過去問が豊富にあり、チュートリアルも用意されているため、事前にチュートリアルでフォームの使い方や問題への取り組み方などを体験してから臨みました。

## この記事で取り扱う問題
ABC 325で出題された問題のうち２番目に易しい B 問題「World Meeting」について、私の解答を紹介させていただきます。
ちなみに、制限時間は100分なのですが時間内には解ききれず、コンテスト終了後まで粘ってなんとか解き終わりました。

AtCoder 公式：[World Meeting](https://atcoder.jp/contests/abc325/tasks/abc325_b)

## World Meeting
配点 : 250 点

### 問題文
キーエンスには世界各地に $N$ 個の拠点があり、$1$ から $N$ までの番号が付けられています。 拠点 $i$ には $Wi$ 人の社員が所属しており、世界標準時で 0 時のとき拠点 $i$ は $Xi$ 時です。

あなたはキーエンス全社で 1 時間の会議を開きたいです。
各社員は、会議の開催時間帯が所属する拠点における 9:00-18:00 の時間帯に完全に含まれる場合にのみ会議に参加できます。

なるべく多くの社員が参加できるように会議の開催時間帯を決めるとき、会議に参加できる社員の数の最大値を求めてください。

### 制約
- $1 ≤ N ≤ 1000$
- $1 ≤ Wi ≤ 10^6$
- $0 ≤ Xi < 24$
- 入力は全て整数

### 入力
入力は以下の形式で標準入力から与えられる。

$N$
$W\_1$ $X\_1$​
$W\_2$ $X\_2$
⋮
$W\_N$ $X\_N$

### 出力
会議に参加できる社員の数の最大値を出力せよ。

---

### 入力例１
```
3
5 0
3 3
2 18
```

### 出力例１
```
8
```
世界標準時で 14:00-15:00 の時間帯に会議を開催することを考えます。

- 拠点 1 における 14:00-15:00 の時間帯に会議が開催されるため、拠点 1 に所属する 5 人の社員は会議に参加できます。
- 拠点 2 における 17:00-18:00 の時間帯に会議が開催されるため、拠点 2 に所属する 3 人の社員は会議に参加できます。
- 拠点 3 における 8:00-9:00 の時間帯に会議が開催されるため、拠点 
3 に所属する 2 人の社員は会議に参加できません。

よって、合計で 5+3=8 人の社員が会議に参加できます。 これより多くの社員が参加できるような会議の開催時間帯はありません。

---

### 入力例２
```
2
1 10
1000000 20
```

### 出力例２
```
1000000
```
---

### 入力例３
```
6
31 3
20 8
11 5
4 3
47 14
1 18
```

### 出力例３
```
67
```


## 私の解答
### 最終解答
```
<?php
// 店舗数を取得
$num = fgets(STDIN);

// 店舗の数だけ情報を取得
for ($i = 0; $i < $num; $i++) {
    // 取得した文字列を変数に分割
    fscanf(STDIN, "%d %d", $a, $b);
    // 店舗情報を配列に格納 [人数,時差]
    $stores_info[] = [$a, $b];
}

// 会議の配列 [ 開始時間 => 参加人数 ] を準備しておく
$participation = [];

// 24時間全検索
for ($hour = 0; $hour < 24; $hour++) {

    // 店舗情報の配列から、一店舗ずつ取得
    foreach ($stores_info as $store_info) {

        // 店舗情報から人数を取得
        $member = $store_info[0];

				// 標準時間 $hour 時の時、現地時間は何時か
        $time = $hour + $store_info[1] % 24;

        // 現地時間が 9 ~ 17 時か判定
        $isWorkingHour = 9 <= $time && $time <= 17;

        // 開始時刻も終了時刻も問題なければ
        if ($isWorkingHour) {
            // すでに「その時間の参加人数」に人数が登録されている場合
            if (isset($participation[$hour])) {
                // 「その時間の参加人数」に人数を加算
                $attend_members = $participation[$hour];
                $attend_members += $member;
                $participation[$hour] = $attend_members;
            } else {
                // まだ登録されていない場合、人数を登録
                $participation[$hour] = $member;
            }
        }
    }
}

echo max($participation);
```
### 解説
#### 標準入力
AtCoder では、プログラム実行時に標準入力で値を渡し、プログラムが仕様通りの挙動をするかどうか自動でテストされ、その場で正解/不正解が判定されます。
そのため、標準入力の受け取り方を理解し、使えるようにすることが必須です。

今回の入力形式を見てみましょう。

$N$
$W\_1$ $X\_1$​
$W\_2$ $X\_2$
⋮
$W\_N$ $X\_N$

$i$やら$N$やら出てくるのでややこしく感じますが、問題文を読み替えるとこういうことになります。
```
<店舗数>：N 店舗
<店舗１>：<従業員◇人> <時差◆時間>
<店舗２>：<従業員★人> <時差〇時間>
⋮
<店舗 N >：<従業員☆人> <時差△時間>
```

標準入力は以下で取得することができます。
```
$num = fgets(STDIN);
```
参考：[fgetsとかSTDINとか標準入力がわからなくてPaizaスキルチェックを始められない方へ](https://qiita.com/kakudaisuke/items/df05f73c510fe247e59f)

競技プログラミングでは不要な空白が入ってくることを想定する必要はないかもしれませんが、⇧の記事にもあるように、空白を取り除く trim 関数も使うべきだったかなと思います。

まず入力の一行目で店舗数を渡されるので、それを取得。
その後は↑で取得した店舗数だけ情報を受け取る必要があるので、for文でループを回して取得しました。
```
// 店舗数を取得
$num = fgets(STDIN);

// 店舗の数だけ情報を取得
for ($i = 0; $i < $num; $i++) {
    // 取得した文字列を配列に分割[人数,時差]
    $line = explode(" ", fgets(STDIN));
    // 店舗情報を配列に格納
    $array[] = [$line[0], $line[1]];
}
```
取得した文字列は[人数,時差]の形式で与えらえるので、それらを使えるようにスペースを区切りに分割するため explode関数を使用しています。
それを配列にまとめました。

#### 答えへの持って行き方
最終的に求めるべきは一番多い参加人数、ということなので、時間別の参加人数の配列を作り、最後に max 関数で配列の最大値を求めればいいかなと考えました。
```
// 会議の配列 [ 開始時間 => 参加人数 ] を準備しておく
$participation = [];
⋮
⋮
echo max($participation);
```
#### 24時間を全検索する
先ほどの方針で、24時間の各開始時間において、参加者がそれぞれ何人になるか考えていきます。
まず24時間分for文でループを回して、その中で各店舗について処理をしていく構造になっています。
```
// 24時間全検索
for ($hour = 0; $hour < 24; $hour++) {

    // 店舗情報の配列から、一店舗ずつ取得
    foreach ($array as $store) {




    }

}
```

#### 時差をどう考えるか
ここで、時差によって各地で異なる時間をどう扱うかが問題になります。時間をどこかに合わせて考える必要があります。
後で説明しますが、ここが私にとって分かれ道となりました。

私は各店舗の 9:00~18:00 がそれぞれ標準時間の何時にあたるか、標準時間に換算して考えることにしました。
上記のforeachの中身が下記です。
```
    // 店舗情報から人数を取得
    $member = (int)$store[0];
    
    // 店舗情報から、現地9時の標準時間を取得
    $time1 = (int)$store[1] + 9;
    
    // もし24時間を超えるなら、24を引く
    if ($time1 >= 24) {
        $time1 -= 24;
    }
    
    // 店舗情報から現地18時の標準時間を取得
    $time2 = (int)$store[1] + 18;
    
    // もし24時間を超えるなら、24を引く
    if ($time2 >= 24) {
        $time2 -= 24;
    }
    
    // 会議開始時刻が、現地9時より遅いかどうか
    $start = $time1 <= $start_time;
    
    // 会議開始終了が、現地18時より早いかどうか
    $finish = $finish_time <= $time2;
    
    // 開始時刻も終了時刻も問題なければ
    if ($start && $finish) {

        // すでに「その時間の参加人数」に人数が登録されている場合
        if (isset($participation[$hour])) {
        
            // 「その時間の参加人数」に人数を加算
            $members = $participation[$hour];
            $members += $member;
            $participation[$hour] = $members;
    
        } else {
            // まだ登録されていない場合、人数を登録
            $participation[$hour] = $member;
        }
    }
```
最後の if 文の条件式の部分ですが、isset 関数というのを初めて使いました。
これは、指定のキーに値があるかどうかを bool 値で返す関数です。


さて、ここで完成かと思いきや、入力例１と２の出力結果は例の通りでクリアしたにも関わらず、入力例３だけ出力結果の数値がおかしくなりました。

ここで気づいたのが、日付が変わって時間が 23 から 0 になる部分に問題が生じるということです。
時間の大小（早い遅い）は、数直線のイメージで下記のようになります。

★(現地時間 9 時の標準時間) < (開始 標準時間) かつ (終了 標準時間) < ★(現地時間 18 時の標準時間)

標準時間に合わせるため、★の部分を時差を元に変換しました。

ですが、これだと下記のような場合、本当は該当するにも関わらず、数字の大小で比較しているので、成り立たなくなるのです。
20時 (現地9時) < 開始 22 時 かつ 終了 23 時 < 5 時  (現地18時)
最後の 5 という数字が 23 より小さいので、非該当となってしまいます。

ここでしばらく泥沼にハマってしまい、コンテストはタイムオーバーになってしまいました。
そのまま粘って考え続け、しばらくしてやっと答えが出ました。

標準時間に合わせるのではなく、現地時間に合わせればよかったのです。

現地時間 9 時 < ★(開始 現地時間) かつ ★(終了 現地時間) < 現地時間 18時

★の部分を現地時間に換算します。枠が9時～18時に固定されているので、その中で変動する数値を判定するのは容易でした。
日付の変更による時間の数値の大小関係を考慮する必要がなくなったのです。

前者は固定された値に対して枠を動かしてマッチするか、後者は固定した枠の中で変動する値がマッチするか判定しているイメージですね。

時間を換算する際に、２パターンあるということに気づいてどちらを選択するか考える必要があったのだなと、学びになりました。

ということで、修正した部分のコードがこちら。
```

    // 標準時間 $hour 時の時、現地時間は何時か
    $time = $hour + (int)$store[1];
    
    if ($time >= 24) {
        $time -= 24;
    }

    // 現地時間が 9 ~ 17 時か判定
    $workHour = 9 <= $time && $time <= 17;

    // 開始時刻も終了時刻も問題なければ
    if ($workHour) {
    
        // すでに「その時間の参加人数」に人数が登録されている場合
        if (isset($participation[$hour])) {


```

これでやっとテストが通りました！！


### これでもよかった
#### 標準入力の別の方法
後で調べて分かったこととして、標準入力の取得には fscanf 関数を使う方法もあるということがありました。
```
// 取得した文字列を変数に分割
fscanf(STDIN, "%d %d", $a, $b);
// 店舗情報を配列に格納 [人数,時差]
$stores_info[] = [$a, $b];
```

#### 24時を過ぎた時間の扱い
時差の計算で24時を過ぎた場合に、24を引くというif文を使って処理をしましたが、こんな方法もありました。
```
// 標準時間 $hour 時の時、現地時間は何時か
$time = $hour + $store_info[1] % 24;
```
24で割ったあまりで考えるというものです。
24時間を超えない場合はそのままの数字があまりになるので、if 文で分岐させる必要がなくてスッキリしますね。

## まとめ
はじめての競技プログラミングでしたが、私にとっては B 問題でもかなり解きごたえがあって、非常に学びになりました。
私が現在所属している内定直結型のエンジニア実習「[アプレンティス](https://apprentice.jp/)」において、「AtCoderの過去問を毎日１問解く」というのが来週から課題として始まります。
このような過去問を毎日解くことを続けていけば、私のような駆け出しエンジニアにとって確実に力になると感じています。