2020/11/14、15に開催されたコンテストの感想
AtCoder Grand Contest 049
A
有効グラフの頂点をランダムに選んでその頂点とそこから行ける頂点を全部消す操作を行えるだけ行うときの操作回数の期待値
- 当然まともに操作するような問題ではない
- 求める期待値はすべての操作を考えた時にある頂点を選ぶ回数の期待値の和
- をどうやって計算すればいいかわからなかった
B
01文字列Sを何回の操作でTにできるか 操作:11→00 or 01→10
- 0を右に移動するか、0を2つ生み出すか
- 0の個数は減らない 矛盾があれば不可
- 0の個数の偶奇は変わらない 矛盾があれば不可
- 0は左には移動できない 矛盾があれば不可
- あとはできそう
- 今ある0を右から順にTの0に対応付けて足りない分を左で補充する
- のは最適ではない
- 考えてみると、今ある0をできるだけ近い位置に移動する方法で問題ない
- 足りない分はできるだけいい場所を選んで補充する
AtCoder Beginner Contest 183
A
ReLU(x)を求めよ
- 定義は知っていたのでそのままif文で実装
- max(0,x)でもいいね
B
ビリヤード。スタート→壁→ゴールのためには壁のどの位置に当てればいいか
- めんど
- 二分探索でも行けそうだけど時間かかりそうだし数学的に解く
- 相似な三角形が見えるのでその比を求める
- マイナスの時不安だったけど通った
- 内分点の公式なんて知らない（習ったけど）
C
都市1から出て全都市1回ずつ行って戻ってくる経路のうち経路長Kのものはいくつか
- 制約が小さいので全探索
- いつも通り順列を全部試す
- 気を付ける点とすれば出発点が指定されていること
- 順列生成スニペット忘れて一瞬ヒヤッとした
D
N人の人は[S[i],T[i])の時間P[i]の湯を使う。供給量はWで一定で貯めておけないとき、需要をみたせるか
- 検証すべき時間が長くない
- シンプルなimos法でいい
- お湯貯めれると思っちゃった
- 閉区間だと思っちゃった
E
障害物のある二次元グリッドを左上から右下までチェスのクイーンが移動する。右か下か右下にしか動かないときの経路を数え上げよ
- ある座標への遷移元がおおい
- 累積和とかでいいと思うけどバグる
- 遠い遷移元を気にしたくないので添え字を増やしてDP
- 遠くからの移動は空中を経由しているものとみて座標に仮のz軸を導入する
- dp[z][v][y][x]を座標(x,y,z)でクイーンがvの方向を向いている状態の経路とする
- 空中にいる時は自分の向いている向きにしか移動できない
- あとは自由に空中と地上を行き来できる
定数倍が重いけど何とかなる
実は地上にいる時の向きはどうでもいいね
- というここまでの考えについてちょうどいいツイートを見つけたので貼る
昨日のEのDP、
— てんぷら (@tempura_cpp) 2020年11月16日
「マスi, j に着地している」
「マスi, j の上空を横に移動中」
「マスi, j の上空を縦に移動中」
「マスi, j の上空を斜めに移動中」
の4状態と見ることもできるのね
F
いろんなクラスの児童がいる。児童のグループが合流するクエリと、ある児童のいるグループにこのクラスの児童が何人いるかという質問クエリを処理せよ
- Union-Find一択っぽい
- けどクラスの情報が重い
- vectorではなくmapで持てばいいのでは
- union操作の時にどうやって結びつけるか
- データ構造をマージする一般的なテクに思い至る
- mapのsizeが小さいほうを大きいほうにマージすれば何とかならないか
- というかそれでうまくいってないとこんな人数通してないやろ
- AC
最近こどふぉに全然出てないので出たい
