AtCoder キーエンスプログラミングコンテスト2024(ABC374) A~D解説

AtCoderの[キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)](https://atcoder.jp/contests/abc374)のA問題からD問題までの解説です。
本記事では、使用するアルゴリズムについての解説は基本的にしておらず、そのアルゴリズムの使用法に至るまでの過程や問題文の解釈に重点を置いています。
筆者は主にC++を使用しているため、それに準じたコードが出てくることがあります。

# A - Takahashi san 2 

>**問題文**
>キーエンスでは、役割や年齢、立場の違いに関係なく「さん」付けして呼ぶという文化があります。
>英小文字のみからなる文字列 S が与えられます。
>S が san で終わっているならば Yes を、終わっていないならば No を出力してください。
>**制約**
>・S は英小文字のみからなる長さ 4 以上 30 以下の文字列
>**出典**
>[キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374) A問題](https://atcoder.jp/contests/abc374/tasks/abc374_a "A - Takahashi san 2")

#### 解説 
問題文の3つ目の文章から、与えられた文字列Sの末尾から3つの文字について判定を行います。
判定内容は`1.末尾から3文字目が's'である`かつ`2.末尾から2文字目が'a'である`かつ`3.末尾から3文字目が'n'である`です。これが真であれば`Yes`、偽であれば`No`と出力します。
これをコードで書くと下記のようになります。

``` s[s_cnt - 3] == 's' && s[s_cnt - 2] == 'a' && s[s_cnt - 1] == 'n' ```

*`s`は入力で与えられた文字列sをそのまま受け取ったstring、`s_cnt`はsの文字数です。
*`&&`はC++で論理積を表します。


# B - Unvarnished Report 

>**問題文**
>英小文字のみからなる文字列 $S,T$ が与えられます。 $S$ と $T$ が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力してください。ただし、 $S,T$ の一方にのみ $i$ 文字目が存在するときも、$i$ 文字目は異なっているとみなすものとします。
>より厳密には、$S$ と $T$ が等しくないならば次の条件のうちいずれかをみたす最小の整数 $i$ を出力してください。
>・$1\leq i \leq|S|$かつ$1\leq i \leq|T|$かつ$S_i\neq T_i$
>・$|S|<i<|T|$
>・$|T|<i<|S|$
>ただし、$|S|, |T|$でそれぞれ$S,T$の長さを、$S_i,T_i$でそれぞれ$S,T$の$i$文字目を表します。
>**制約**
>・$S,T$は英小文字のみからなる長さ 1 以上 100 以下の文字列
>**出力**
>$S$ と $T$ が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力せよ。
>**出典**
>[キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374) B問題](https://atcoder.jp/contests/abc374/tasks/abc374_b "B - Unvarnished Report")

#### 解説
まず、文字が異なる場合というのが`1.S,Tの文字数内で異なる文字がある`と`2.S,Tの一方にのみ存在するi文字目で異なる`の二つに分けられます。そして、文字が一致する場合は`0`を出力する必要があります。
今回、以下のようなロジックで実装しました。
1. `ans`に`0`を入力する
2. 先頭から1文字ずつ一致するかの判定を$S$と$T$の文字数が少ない方の文字数だけ行う。異なった場合、`ans`に`0`を入力し、以降の判定を行わない
3. `2.`で判定後、$S$と$T$の文字数が異なるかつ`ans`が`0`である場合、`SとTの文字数が少ない方の文字数 + 1`文字目をansに代入する
4. `ans`を出力する

##### 補足
実際に実装する際には**解説**のロジックの`3.`についてですが、`2.`の最後の判定終了時にループを抜け出さずにそこで`ans`に`SとTの文字数が少ない方の文字数 + 1`文字目を代入した方がすっきりします。そうすると、`ans`が`0`であるかの判定は必要なくなります。

# C - Separated Lunch
>**問題文**
>キーエンス本社に勤務する人数が増えてきたので、本社に存在する部署を 2 つのグループに分け、昼休みの時間帯を分けることにしました。
>キーエンス本社には $N$ 個の部署が存在し、$i$ 番目 ($1\leq i \leq N$) の部署に所属する人数は $K_i$  人です。
>それぞれの部署をグループ $A, B$ のいずれか一方に割り当て、グループごとに同時に昼休みをとり、 かつグループ $A, B$ の昼休みの時間が重ならないようにしたとき、同時に昼休みをとる最大人数としてあり得る最小の値を求めてください。
>すなわち、グループ $A$ に割り当てられた部署に所属する人数の合計とグループ $B$ に割り当てられた部署に所属する人数の合計 のうち大きい方の値としてあり得る最小の値を求めてください。
>
>**制約**
>* $2\leq N \leq 20$
>* $1\leq K_I \leq 10^8$
>* 入力はすべて整数
>
>**出典**
>[キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374) C問題](https://atcoder.jp/contests/abc374/tasks/abc374_c "C - Separated Lunch")

#### 解説
問題文を読んで、$N$個の部署をグループ$A,B$の**2つ**に分けるという点からbit全探索が浮かびました。制約を確認すると$2\leq N \leq 20$であるため、計算量も大丈夫そうという感想でした。正確に計算量について見ていきます。
$N$個の部署を2つに分ける組み合わせは入れ替えの重複込みで$2^N$通りあります。そして、その$N$個を実際に二つに分けるという作業は$O(N)$で実施できます。
なので、計算量は$O(N\cdot2^N)$(ただし、$2\leq N \leq 2$)ということから速度は問題なさそうです。

# D - Laser Marking 
>**問題文**
>$xy$ 平面に対し、レーザを照射しながら線分を印字する印字機があります。
>* 印字開始時、レーザ照射位置は座標 $(0,0)$ にある。
>* 線分を印字する際は、以下の流れに従う。
>    * まず、レーザ照射位置を線分の端点のうちどちらか 1 つに移動させる。
>        * どちらの端点から描画を始めてもよい。
>    * その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。
>        * 線分の途中で印字を中止することは許されない。
>* レーザを照射していない時、レーザ照射位置は 1 秒あたり速度 $S$ で任意の方向に移動できる。
>* レーザを照射している時、レーザ照射位置は 1 秒あたり速度 $T$ で印字中の線分に沿って移動できる。
>* レーザ照射位置の移動にかかる時間以外の所要時間は無視できる。
>
>高橋君はこの印字機で $N$ 本の線分を印字したいです。
>そのうち $i$ 本目の線分は、座標 $(A_i,B_i)$と座標$(C_i,D_i)$ を結びます。
>なお、複数の線分が重なっていることがありますが、全ての線分についてその都度重なっている部分を印字する必要があります。
>うまく印字機を操作したとき、全ての線分を印字完了するまでにかかる最小の時間は何秒ですか？
>
>**制約**
>* 入力は全て整数
>* $1 \leq N \leq 6$
>* $1\leq T \leq S \leq 1000$
>* $-1000 \leq A_i,B_i,C_i,D_i \leq 1000$
>* $(A_i,B_i) \neq (C_i, D_i)(1\leq i \leq N)$
>
>**出典**
>[キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374) D問題](https://atcoder.jp/contests/abc374/tasks/abc374_d "D - Laser Marking")

#### 解説
$N \leq 6$という制約からすべてのルートについて印字完了までの時間を計算し、その中で最小の時間を求めればよさそうです。
まずは計算量を確認します。$N$本の線分の選び順の種類数は最大で $6!$ 通り、$N$本それぞれの線分について座標が二つあるためその線分の引き方は最大で $2^6$ 通りです。合わせて $6!\times2^6 = 46080$ 通りとなります。この計算量はAtCoderで求められる計算量としては十分高速といえます。
よって、上記の線分の選び順と線分の座標の選び方(線分の引き方)の2つについて、二重ループの構造を作成し、それぞれについて印字完了までの時間を計算して、最小値を求めます。
#### 補足(C++の実装において)
* 線分の選び順の全列挙についてC++では`next_permutation`が便利です。
* 求めた最小値を出力する際、`cout`を使用している場合、`setprecision(n)`(nは表示する桁数)を使用することで標準出力する桁数を指定できます。
* (本問題には関係ない話)浮動小数点での加減を実施する際には絶対値が小さいものから計算を行わないと誤差が発生してしまう可能性があります。