Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374） - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

コンテスト時間: コンテスト時間: 2024-10-05(土) 21:00 ~ 2024-10-05(土) 22:40 (100分)

A - Takahashi san 2

Difficulty: ???

解答時間: 2:06

英小文字のみからなる文字列 $S$ が与えられるので、 $S$ がsanで終わっているかどうか判定せよ。
$S$ の末尾3文字を見て判定するだけ。 $S$ の長さを $l$ として、substrを使うなり、S[l-3], S[l-2], S[l-1]をとってくるなりすればよい。

B - Unvarnished Report

Difficulty: ???

解答時間: 5:23

英小文字のみからなる文字列 $S, T$ が与えられるので、両者が等しいならば0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力せよ。
の場合について。先頭から文字目を見ていく。
- $i = |S| \: \mathrm{or} \: i = |T|$ ならその $i$ を出力して終了。
- $S_i \neq T_i$ ならその $i$ を出力して終了。

C - Separated Lunch

Difficulty: ???

解答時間: 6:19

$N$ 個の部署が存在し、 $i \: (1 \leq i \leq N)$ 番目の部署の人数は $K_i$ 人である。それぞれの部署をグループ $A, B$ のいずれか一方に割り当てたとき、グループ $A$ の部署の人数の合計とグループ $B$ の部署の人数の合計のうち、大きい方の値としてあり得る最小の値を求めよ。
各部署を2つのグループに割り振っていくことを考える。こういうときは bit 全探索。
「 $i$ 番目の部署について、フラグが立っていたら $A$ へ、そうでなければ $B$ へ」のように割り振っていけばよい。
制約も $N \leq 20$ なので十分間に合う。

D - Laser Marking

Difficulty: ???

$xy$ 平面に対し、レーザを照射しながら線分を印字する印字機がある。初期状態では、レーザ照射位置は座標 $(0, 0)$ にある。レーザを照射していないときは、レーザ照射位置は 1 秒あたり速度 $S$ で任意の方向に、レーザを照射しているときは $1$ 秒あたり速度 $T$ で印字中の線分に沿って移動できる。これから $N$ 本の線分を印字していくことを考える。 $i$ 本目の線分は、座標 $(A_i, B_i)$ と座標 $(C_i, D_i)$ を結んでいる。このとき、全ての線分を印字完了するまでにかかる時間の最小値を求めよ。
注目すべきは $N$ の小ささで、なんと最大でも $N = 6$ である。したがって、何らかの貪欲法あるいは全探索で解けそうだという見当はつく。巡回セールスマン問題的な？
ここで私は、ある点から他の $2N - 1$ 個の点の距離のリストをソートして持っておき、未訪問の点で最も近い点から訪問していくというような貪欲解を考えたが、うまくいかず撃沈。
実際はそんな複雑ではなくて、「どの順序で線分を書くか」と「どの方向に線分を書くか」のすべてのパターンを調べることで解くことができる。前者は順列全探索、後者は bit 全探索で実現できそう。
ABC369-E がもっと難しくした類題？

結果

Performance: 699

Rating: 603 → 613 (+10)

解けそうで解けなかったD問題。