キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）に参加しました。
結果
A,B,Cの3問正解でした。あと10分遅れでD問題も正解だった。
デバッグに時間がかかってD問題が時間内には解けなかったのが悔しい。計算量削減の方針などは合っていたけどデバッグが間に合わなかった。
A - Batting Average
入力した2数の割り算を少数第4位で四捨五入して小数点以下3桁までを出力させる問題。末尾0埋めで出力させるのが面倒くさい。
計算して少数第4位に5を加えて、少数第3位までを文字列にして出力させた。 よくよく考えたらsetprecisionとかprintfで小数点以下の桁数を指定して出力できるからわざわざ文字列に変換しなくてよかったかも。
B - Line Sensor
マス目に.か#が書かれているから各列の#の数を出力する問題。
2重ループで処理すれば特に困らないと思う。
C - Ameba
2分木を作っていく問題かなと思った。
の子2つに親の値+1を設定していくだけの問題。二分木を配列で実装する場合、親がiとしたとき子のインデックスが2iと2i+1になることを知っていれば特に悩まずに実装できるのかなと思う。
D - Robot Arms 2
指定された条件で点を置いていったときに最後の点が指定した座標に設定できるかどうかを判定する問題。
条件は
- 点
- 点
- 点
は指定された座標(x,y)
- 点
と点
の距離は
- 線分
と線分
が直行するように点
を設定する
愚直に
- 深さ優先探索で順番に点を設定
- 前回X軸にそって点を設定した場合と、前回Y軸に沿って点を設定した場合に分けして処理
でやってみたらTLEだった。
すこし考察してみると、
- X軸に沿って点を設定した場合とY軸に沿って点を設定する場合は交互に起きる
- 各操作でX座標かY座標のどちらかしか変化しない
→処理をX軸に関してとY軸に関してに分離して考えることができる。
と気づいたので愚直に解いたときは2次元で考えていたことを1次元2回に修正して実装した。
それでもTLEだったので
に関して1度チェックした座標は処理を省くように少し修正してみた。
最終的にACできたけど、デバッグ中にコンテストが終わってしまった。デバッグで少し手間取ってケアレスミスを連発していたのがちょっともったいなかった。
ギリギリ時間内にACできただろうなあ。
