2020/11/21、22に開催されたコンテストの感想

こどふぉ全然でれてねぇ

AtCoder Regular Contest 108

A

N+M=SかつNM=Pなる整数(N,M)は存在するか

• 掛け算のほうが候補しぼれる
• てか制約が明らかに√Pをしてくれと言っている
• 約数を全探索するだけ

B

文字列から"fox"を消して残りを連結する操作を何回でも行えるとき文字列は何文字まで減らせるか

• dfsに行きかけたけどそれはちょっときつい
• stackに入れたり出したりするだけでいい
• xをトリガーにしてstackの上がfoになってたらカウント変数++でfoを消す
• |S|-3*cnt
• emptyなのにpopしようとしてRE吐いたのは反省
• C++のstackってclear()ないんですか（驚き）

C

自己ループがないが多重辺のありうる連結無向グラフがある。辺にはラベルが付いている。頂点に数字を書き込んで、次の操作をしても連結であるようなグラフの構築を（可能なら）せよ

操作：両端の頂点に書かれた数字の片方だけとラベルが一致している辺のみ残し、あとは除去する

• 可能なら？
• 可能やろ、不可能サンプルないし
• 木は連結
• 適当な全域木をつくれれば他の辺はどうでもいい
• 簡単な場合を試したら全部構築できる
• 反例見当たらないしこれでいいやろ
• 根を適当にとって番号1を振る
• bfsしながら頂点に番号を振っていく
• 反対側の頂点の番号とラベルが一致している場合をそうでない場合の場合分け

D

文字列ABに挿入操作を繰り返してできる長さNの文字列の総数、挿入できる文字は挿入する位置の左右の文字によって決まっている

解けず。一般的に解くのではなくて挿入文字によって16通りの場合分けをすればいいらしく、その発想がなかった

AtCoder Beginner Contest 184

A

2*2行列式

• ad-bcですね、問題文にかいてあるのでそのまま

B

X点持っている。クイズに正解すると+1、不正解だと-1、ただし0未満にはならないとき、最終的には何点になるか

• 時系列に沿って処理するだけ
• 正解の時、X++
• 不正解の時、X=max(0,X-1)←これにしとくと余計なifが減る

C

3歩以内の範囲と斜め無限に進める「超竜馬」が目的の座標に進むには何手かかるか

• 強いので手数そんなにかからない
• 0手（忘れないように気を付けよう）と1手は自明、そうでないケースを考える
• 座標(x,y)に対してf(x,y)=x+yとしてこれの偶奇が一致すれば2手
• 一致しなくても目的のマスの隣までは行けるので最大3手なことがわかる
• 斜め1手で近い位置に行けても2手
• 6歩以内も2手
• 後は3手
• 困るのは「斜め1手で近い位置に行ける」
• 目的座標から3歩以内を全列挙してそのどれかに1手で行けるかで判定した

D

袋の中に金,銀,銅貨がA,B,C枚。ランダムに1枚出して同じのを2枚入れるときどれかが100枚になるまでの操作回数の期待値

• 最難やろこれ、投げました
• A,B,Cの枚数を状態にもつDP
• 実装めんどいことをしてバグり散らすわ時間もロスしたわで散々

E

障害物のある2次元グリッドの2点間最短距離問題、ただし文字が降られたマスからは同じ文字の振られたマスに移動できる

• F解いてからこっち来た。間に合わなかった
• 基本はbfsないしはダイクストラっぽいけどワープをどうするか
• 間に合わないから同じ文字の全点対に辺張って間に合ってくれをしたがやはり間に合わない、それはそう
• 全部のマスに同じ文字書いてあったら頂点二乗になって計算量まずいもんね
• てことで拡張ダイクストラです
• a書いてあるマスから仮想的な頂点Aに辺が生えていて、Aからもすべてのaに辺が生える、これでa-a間のワープを少ない辺で実現できる
• 間に合うけど実行時間結構きつい 01bfsでもさして変わらん
• ご丁寧に辺全部張ってるから？適宜張る感じにすると速かったりする？

F

N要素の数列Aから選んで足して作れるT以下の最大の数、Nは40以下

• Dあきらめてこっち来てたまげた
• 半分全列挙そのままじゃん
• 書いて、終わり