ABC128_C(Switches)
問題
考えたこと
- 問題文が異常に難解なのと入力パターンも難解
- とりあえず全てのスイッチのパターン試す必要がありそう
- 制約が小さいため
bit全探索が頭をよぎる- 途中で 配列同士のand演算を使いたかったので numpy も使用する
ABC127_D(Integer Cards)
問題
考えたこと
- 少ない数値を大きい数値に変換し続ければ良い
- カードをソートして, 入力値を二分探索, その中で小さい方から更新していけば良さそう？
- 制約も
だし行けそうな気がする
- 先にオチを言うと
TLEでした
- 先にオチを言うと
ABC132_D(Blue and Red Balls)
問題
考えたこと
- 組み合わせ系の問題
- i = 1 を考えると 青いボールが連続して並んでいる場合だけ.
- 例えば赤いボールと青いボールがそれぞれ3個ずつあった場合には, 赤いボールの隙間に青いボール全部を入れることになるので
の組み合わせ.
- 例えば赤いボールと青いボールがそれぞれ3個ずつあった場合には, 赤いボールの隙間に青いボール全部を入れることになるので
- i = 2 を考えると 赤いボールの隙間のうち, 2箇所に青いボールを入れれば良いことがわかる. つまり
になるはず.
- 青いボールは分割した数 (i = 2 の場合2個) を取り除いて残ったボールの数に, 仕切りの数 (i = 2 なら 仕切りの数は1つ) を足したものの仕切りの位置を選ぶ組み合わせ.
- つまり2回で回収できる組み合わせは
(青いボールの割り振り方) で計算できる.
- 3回目以降も同様. ルール化できたので実装に入る.
ABC129_D(Lamp)
問題
考えたこと
なので 意外と愚直でいけるかも
- 壁の位置を記録しておいて, 明かりをおく点で二分探索すると壁と壁の間の数がわかる
- 縦と横、両方やれば 縦 + 横 - 1 がその点の明かりの強さとなる
- 一度見た明かりと同じ列にいる場合, 既に通っているので計算不要？でも実装が複雑なので一旦保留
- 壁を自前ではやしたほうがわかりやすそうなので, 壁は自前で生やすこととする
ABC140_D(Face Produces Unhappiness)
問題
考えたこと
- 最初は左端から入れ替える、入れ替えないみたいな操作をすることを考えた
- 手計算でも計算量が多くなりすぎるので無理と判断
- 何かしらのロジックで一気に解けそうとは思ったがそれ以上進まず
- 残念ながらわからなかったので解説を見る
Rustでセグメント木を作ってみた
セグメント木
- 競プロer御用達のデータ構造の1つ
- 配列の範囲に対して値を代入したり, 範囲内の合計値や最大値/最小値等を 高速に 取得するためのデータ構造
- AtCoder Beginner Contest 185 にてセグ木の問題が出題された
- 悔しいのでRustで実装することとした
