年末年始のAtCoder精進（緑編）
allegrogikenこれをもとにやってます
allegrogiken問題
AtCoder Beginner Contest 035 | B - ドローン
左右上下をそれぞれ LRUD とした文字列をドローンに与えて動かす。
また、ワイルドカードとして ? も使えて、この時ドローンはどの方向にも動ける。
そんな文字列 S から下記を計算する問題。
- ドローンが「元居た場所からできるだけ離れる」ように
Sを解釈したとき、最終的に元居た場所からのマンハッタン距離をいくつにできるか？(T = 1) - 逆に、ドローンが「元居た場所にできるだけ近づく」ように
Sを解釈したとき、
最終的に元居た場所からのマンハッタン距離をいくつにできるか？(T = 2)
考えたこと
答えるのが「最終的な位置」なので、途中の状態は考える必要がなさそう。
なので、 LRUD だけを指示通りに解釈して得られた座標をもとに ? の分を目標に合わせて足したり引いたりすれば良いと考えた。
最大値を求める (T = 1) の場合
? を LRUD のどれかに置き換えて想像する場合、 ? を無視して計算した座標の x がマイナスなら すべて L、そうでないならすべてを R にとする感じで良さそう。距離を最大化するだけなので y 軸の動きを無視しても問題ない。
計算処理としては「? を無視して計算した座標のマンハッタン距離に ? の個数を足す」でOK。
最小値を求める (T = 2) の場合
最大値のケースと概ね同じような考えが適用できるけど、距離はマイナス値をとらないので 0 に収束できるかどうかの判定が追加で必要になる。
?を無視して計算した座標のマンハッタン距離 = d、?の個数 =q とすると、
-
d >= qならd - qが答え - それ以外の場合
-
d - qが偶数 なら0に収束できるので答えは0 -
d - qが奇数 なら 収束できず、答えは1
-
という感じになる。
提出
移動経過も含めた最大値 or 最小値を求めるのかと思って混乱した。25分くらいかかった。
allegrogiken問題
CODE FESTIVAL 2014 決勝 | D - パスカルの三角形
1~10^9 範囲内の整数が渡される。
それがパスカルの三角形に登場するなら三角形のどこか？というのを答える問題。
複数の場所で登場する場合、どの点でもOK。また、登場しないなら -1 を出力する。
考えたこと
パスカルの三角形といえば、 組み合わせ計算 nCk で計算できるけどどう解くのが楽か。
ところで、パスカルの三角形の2列目に着目するとその値は 1 2 3 4 ... と連続した整数になる。
また、出力すべき値は 2 * 10^9 まで許容されている。これは入力の値よりも大きい。
となれば、 2列目に固定して入力の値の応じて行数を答えとするだけ で正しい回答になると思われる。
「登場しない場合は -1」と問題文にはあるが、この制約ならそういったケースは存在しない。
提出
なんだかズルをしてる気分になる回答。
考察がほとんどで、消費時間は 11分ほど。
allegrogiken問題
キーエンス プログラミング コンテスト 2020 | B - Robot Arms
前提
- 直線状に 最大100,000個 のロボットアームがある。
- ロボットアームはそれぞれ、位置
X, 長さLを持ち、X - L < .. < X + Lの範囲をカバーできる。
求めたいもの
- ロボットアーム同士がぶつからないように一部のロボットアームを取り除きたい。
- 取り除いた結果として、ロボットアームができるだけ多い状態にしたい。
- そのときのロボットアームの数を出力せよ。
考えたこと
この手の問題は「区間スケジューリング」という名称で呼ばれる典型的なやつ。具体的には「区間の終端」でソートした後、重複しないように貪欲に区間を選ぶことで区間数を最大化できる。
この問題では、ロボットアームごとに X - L ~ X + L の区間を取るので、その通りに事前処理をしてやることで典型的な形に落とせる。
提出
10分 + 1WA。ロボットアームがマイナス方向にも動くというのに後から気づいた・・
allegrogiken問題
AtCoder Beginner Contest 028 | D - 乱数生成
考えたこと
試行回数が3、つまり奇数なので「中央値がK」を取るためには最低でも 1回 は K が出現していなければならない。また、Kが2回以上出現したとき中央値は間違いなくKになる。などと考えた結果、 Kの出現回数によりパターン分けをして考えるのがよさそう。Kの出現回数が1回の時はさらにパターンができる感じになるであろうからそれを考えていく。
パターン数の算出
全てのパターン数
これは N^3 になる。
Kの出現回数が 0 のパターン数
上の応用で (N - 1)^3 になる。
この時、中央値がＫとなることはない。
Kの出現回数が 1 の場合
中央値が K になるとき、ならないときがありそう。ならないときだけを考えてみる。
多分こんな感じになる・・
[Kより小さい, Kより小さい, K]
あるいは
[K, Kより大きい, Kより大きい]
Kより小さい値は K - 1 個あり、Kより大きい値は N - K 個ある。それをもとに上のパターン数を算出すると
(K - 1) * (K - 1) * 1
+
1 * (N - K) * (N - K)
という感じになるはず。
最後に、登場する順番を問わないので全体に 3C1 を掛けてやると「Kの出現回数が1回で、中央値がKにならない」パターン数が求められる。数式を綺麗にすると、
3 * ((K - 1)^2 * (N - K)^2)
確率の算出
上で算出しなかったパターンはすべて中央値がKとなるので、全体からさっき計算した値を引けば「中央値がKとなるパターン数」を算出できる。ほしいのは確率なので、全パターン数で割ってやれば答えになる。
提出
22分くらいかかった。確率の問題は本番だとだいたい解けない・・
allegrogiken問題
AtCoder Beginner Contest 088 | D - Grid Repainting
-
.と#からなるマス目の情報が渡される。 -
.だけを通って、マス目の左上から右下まで移動することを考える。 - また、通らなくてもよい
.を#に塗り替えることができるらしい。 - 「塗り替えることのできるマス目の最大数」を出力せよ、、 という問題。
- 左上から右下まで移動できない場合は
-1を出力せよ、という例外アリ。
考えたこと
問題文は少々複雑な感じになっているけど、「通らなくてよいマス目の数」は最短経路の長さから逆算できそう。なので、最短経路の長さを幅優先探索などして求めれば良い。
マップ全体の . の数を最初にとっておき、それから「最短経路で使うマス目の数」を引けばOK。
提出
40分 + 1WA。考察はそんなに時間かからなかったので、純粋にコーディングの分。「書くのが遅い」というのもあるけど、こういった実装はテンプレート化しておくべきだなぁ
allegrogiken問題
AtCoder Beginner Contest 166 | E - This Message Will Self-Destruct in 5s
考えたこと
自分の脳では解けなかったので解説を見た・・ 解けてない間に考えたことリスト：
- 全パターンを計算すると死ぬ
- 「番号の差の絶対値」は値の幅が狭い、具体的には
1 .. N-1 - この値を起点に値を事前処理すればいい感じに答えが求まる気がした
- 身長のリストをソートしておいて二分探索とかすれば良いのかと思った
- 二分探索で値が求まったとして、その次に番号の比較が必要なので無理そうな感じ
提出
40分くらい考えて全然分らんかったので解説を見た :worried:
2020/05 に同じようなことをしていたけど残念ながら解き方を全く覚えてなかった模様