京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)に参加しました。

結果

A,B,C,Dの4問正解でした。
E問題が難しかった。答えを出すだけならできたけどTLEになって、時間内に解ける方法が思いつかなかった。

E問題がグラフの問題で解き方考えている時にふと思ったけど、経路探索する時、幅優先探索だと実装が慣れてて楽だからよく使っているけど、深さ優先でも同じくらい気軽に書けるようにならないとなあ。

A - Water Station

5km間隔で給水所がある中で現在地点を与えられるので、1番近い給水所は何km地点のものかを答える問題。

簡単めな計算とifとかで大小比較ができれば解ける問題だと思う。

1番近い給水所は1つ先か1つ手前の2択。なので、まずはその2つの位置が何kmなのかを計算して、現在地点との距離が小さい方を答えれば良い。

給水所は5km間隔であるので、現在地を5で割った余りを5から引いた答えを現在地に足せば1つ先の給水所の位置が算出できる。 1つ手前はそこから5を引けば良い。（現在地点を5で割って小数点以下を切り捨てたものに対して5を掛けても良さそう。5で割り切れた時の考慮が必要だからひと手間かかる気もする。）

数直線上にいくつか点がありその中の2つが指定されるので、その2点の距離を答える問題。
解き方はいろいろあると思う。

各点の位置はテストケースに関わらず一定で、隣の点との間隔は問題文中で与えられているので、一番端の点を0としてそこから各点の座標を予め計算しておいた。指定された2点の座標は事前計算した結果から取得して、そこから2点の距離を答えた。

グリッドの中に長方形状にクッキーが並べられている中でランダムに1枚取り除かれるので、取り除かれたクッキーの位置を答える問題。

グリッドのサイズ的に全探索しても十分間に合うのでまずは全探索して長方形の範囲を探して、次にその範囲の中でクッキーの無いマスを探して答えを出力した。

最低でも縦横2マスはクッキーが置かれているので4マスずつ調べていっても良さそう。

ある時点からの起床時間と就寝時間が与えられるので指定された期間の睡眠時間を答える問題。

割りとよく見かける気がする累積和を使えば簡単に解ける問題。

起床や就寝のイベントのタイミング毎にそれまでの睡眠時間の和を計算しておき、その結果を利用しながら指定された時間の睡眠時間を計算し答えた。

グラフが与えられて、一部の頂点に体力hの警備員がいる。警備員は距離h以下の頂点を警備する。
警備されている頂点の数と頂点番号を答える問題。

警備員がいる頂点を根として深さに制限のある経路探索をしてみたけどTLEになった。単純な経路探索だとTLEになりそうな気がしたので他の方法やデータ構造を考えてみたけどうまくいきそうな方法は思いつかなかった。