AtCoder Beginner Contest197に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが813でした。 D問題は幾何学とか図形の問題っぽい？ E問題はなんとなく解けそうで、でも解けなかった。最小化するの難しい。近い解なら求められるんだけどなあ。
A - Rotate
文字列の扱い方を知っているかどうかという問題だったのかな。 問題だと3文字って制限があるけど、何文字になろうと2文字目から最後までの部分文字列＋最初の文字で新しい文字列を作成すればおしまい。
B - Visibility
マス(X,Y)から上下左右を障害物に当たるまで順番に探索すればいい。 探索の初期値にマス(X,Y)を含むなら重複して数えているのでその分減らして、探索の初期値にマス(X,Y)を含まないならマス(X,Y)分を増やす。
C - ORXOR
区間の作り方がちょっと難しかった。こう言う時のきれいな区間の分け方を知らないので、制約的にNが小さかい点に注目してbit全探索の力技で乗り切った。 2ビット目からビットが1か0かを確認して、ビットが1のときは1ビット前のものと同じ区間に入れる。ビットが0のときは1ビット前とは別の区間とする。ってことにして区間を分けた。 分けれてしまえばあとはOR演算とXOR演算で計算して最小値を求めれば良い。 bit全探索を使っているので全通りの区間の分け方を確認できて最小値をちゃんと求められる。
D - Opposite
図形の問題っぽい。賢い方法がわからなかった。
正多角形だからどの頂点も同心円状にあるとか、Nの制約的に、
は直線状にあるから円の中心は求められるな、円の半径も求められるなとかは思ったけど、
そこから
の座標を確実に求めるのはちょっと難しかった。
E - Traveler
これも解けそうで解けなかった。
問題文的に が小さい順位にボールを集める、反復横跳びみたいにこまめに方向転換してると無駄が多いから同じ色のボールを回収する間は1方向に進んだ方が良いくらいはすぐに思いついてけど、それだけで愚直に実装してみるとサンプルの時点で微妙に答えが違った。
あと1,2個なにか実装方針が必要な気がしたけど何も思いつかなかった。
座標0からスタートして座標0に帰ってるから循環セールスマン問題っぽい気もした。
