キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）に参加しました。
結果
A,B,C,E問題の4問正解でした。
D問題がちょっと難しいなと思ってE問題を見てみたらグラフの問題でした。グラフなら解けそうな気がしたのでD問題を飛ばして、先にE問題を解いてみた。
A - Takahashi san
名字と名前が与えられるので名字 sanと出力する問題。
使用する言語の標準入出力ができるなら特に困らないと思う。
久々にこういった標準の入出力ができれば解ける内容のA問題が出た気がする。
個人的にはこれくらいの内容がA問題らしいA問題だと思う。
B - World Meeting
N箇所の拠点の人数と世界標準時からの時差が与えられるので、 現地時間で09:00-18:00の間でどこか1時間会議を開くとき最大で何人が会議に参加できるかを答える問題。
世界標準時で0時から23時それぞれの時間帯に会議を開催した場合に何人参加できるかを数えて、1番人数が多いときは何人かを答えれば良い。
現地時間は(世界標準時＋時差)mod24で考えると、世界標準時+時差が24時以降になっても対応できる。
C - Sensors
問題文にはセンサーがとか連動してとかあるけど、要するにH×Wの画像のうち一部の画素が黒い画像があって、8連結で考えるときに連結成分が何個あるかを答える問題。
連結成分の数を答えれば良いので、Union-Find木で解くことにした。 黒い画素に番号を振って、連結している画素同士は連結していき、最終的に連結線分が何個できているかを答える。
Union-Find木以外だと幅優先とか深さ優先で連結している画素を辿っていきつつ、連結成分数を数えていけば答えられると思う。
E - Our clients, please wait a moment
コストの最小値を求めるグラフの問題。
都市1から途中までは車で移動して、どこかの都市から都市Nまでは電車で移動するとき、都市１から都市Nまでの最短の移動時間はどれくらいになるかを答える。
途中で移動手段を電車に切り替えるとそれからは電車しか使えないと言う設定がちょっと面倒だと思う。
結論としては都市１から各都市への車で移動したときの最短移動時間と、都市Nから各都市へ電車で移動したときの最短移動時間を計算する。 そこが分かれば、２種類の最短移動時間を組み合わせて 都市１から都市iまでは電車で移動し、都市iから都市Nまでは電車で移動した場合の最短移動時間がO(1)で計算できるようになる。 なのでiを1~Nの全通りで試して最短移動時間を探して答える。
