AtCoder Beginner Contest 351に参加しました。
結果
A,B,C問題の3問正解でした。
D問題解いてみたらTLEになってて、結局時間内には正解できなかった。でも解説を見てみると解き方の方針自体はTLEになった回答と同じだった... 何か無駄な処理でもあってTLEになったのかなあ... ちょっと納得いかない...
A - The bottom of the ninth
野球が9回表まで終わっているので9回裏のチームは何点以上取れば勝てるかを答える問題。
各回での2チーム分の得点が与えられるのでチーム別に集計して、後攻側のチームが何点取れば先攻側の得点＋１点になるかを計算して出力する。
問題文の通り処理するだけのいつものA問題
B - Spot the Difference
1箇所だけ異なる文字列が1組与えられるので、文字列が異なる位置を答える問題。
文字列から任意の1文字だけを参照する方法を知っていれば解ける問題。 ループで全通りのチェックと文字列比較と文字列から任意の1文字の取得ができれば解ける問題。
C - Merge the balls
数列が与えられるので、空の列に指定された手順で処理しながら1つずつ移動させていき、最終的に列の要素数を答える問題。
空だった列に移した後、最後尾2つを対象に処理を行っていく。
数値2つの値が同じなら2つを取り除き+1した値を数列へ加えて、2つが異なる値だったら次の値を列へ移動させる。
最後尾2つの値を処理したいので空の列としてスタックを使うことにした。 最後尾2つは2回ポップすれば取り出せるので、することがなくて元に戻す時の順番だけ気をつければ今回の問題にあったデータ構造だと思う。
もともとの問題文だと数列の値はで列の最後尾2つの値が同じ時はその数値の和を列に追加するという設定だったけど、
だったのでバカ正直に累乗を計算して値を列に加えていくのは現実的じゃない。そもそも
とか大きさ的に扱える範囲を大きく越えてそう。
指数部分だけ管理すればなんとか扱える範囲で収まるし、同じ数の和を計算すると指数が1増えるだけでするので、わざわざ指数を元に数値を計算して、和を計算して、指数表記だと2の何条になるか求めてってことはしなくて済む。
一通り数列の値を列へ移し終えると、要素数はスタックのサイズを出力するだけで済むので最終的な要素数を1つ1つ数えないで済む。
スタック以外でも配列なら頑張れば対応できると思う。キューで処理するにはちょっと無理がある。
どのデータ構造を使うのかと、そのデータ構造で何を管理するのかを正しく設定できれば後は指定されたとおりに処理するだけの問題になるのでそこまで難しくなくなると思う。
D - Grid and Magnet
グリッドが与えられて、一部のマスには磁石がある。磁石と隣り合うマスに移動するとそれ以上は移動できなくなる。こういった設定のときに、そのマスから移動可能なマスの数をそのマスの自由度と定義する。 この時自由度の最大値を求める問題。
磁石と隣り合わないマス同士が隣り合っていれば、そのマス達の自由度は同じになる。 なので、磁石と隣り合わないマス同士をグループとして1まとめにし、グループごとに自由度を求めて、自由度の最大値を出力すれば解けると考えた。
と言う事で大雑把な方針としては
- Union-Find木で磁石に隣接しているマス以外でグループを作る。
- グループ毎に自由度を求める。
- 求めた自由度の内最大値を出力する。
として解いてみた。 けど、TLEでダメだった。
