2020/10/17、18に開催されたコンテストの感想
AtCoder Begnner Contest 180
A
N個ある。A個とってB個足す。いくつ？
- 計算するだけ。制約的に変なことにはならない
B
N個の点のマンハッタン距離、ユークリッド距離、チェビシェフ距離
- 計算するだけ
- チェビシェフで絶対値ミス。どうせ絶対値で扱うのだから最初に取っておくべきだった
C
N個のシュークリームを分割せずに平等に分けられる人数
- 約数列挙そのもの
- シュークリームである点に意図を感じますね
だからなんでシェアする前提なのに素数なんだよお前は！！！！！！！！！！！！！！ pic.twitter.com/vlfB3uhadZ
— ハヤシ|今クラ60進捗90% (@hayashi_lanturn) 2017年4月21日
D
XをY以上にならないように操作できる回数の最大は？ 操作：A倍 or +B
- A(X+B) > (AX)+B より、かけてから足す
- べき乗はどんどんデカくなるのでかける回数は全部試せる
- あとは何回足せるかをそれぞれ計算するだけ
- Y「以上」にならないがややこしい
- 立式ミスがあってだいぶペナ食らった
E
非対称巡回セールスマン問題を解いてください
- 全探索は間に合わない
- bit DPによる解法があることは有名なのでググると解ける
F
頂点にラベルの付いたN頂点M辺のグラフのうち以下の条件を満たすものはいくつか 条件：自己ループがなく、次数は高々2で、連結成分の最大がL
- 次数2ということは直線か大きな輪っかですが
- ...（無理）
Codeforces Raif Round 1
A
目的の座標まで箱を引っ張る。自分は何マス移動する？
- 直線なら簡単
- 曲がるのは最大でも1回
- 曲がると余計な移動が+2
B
リング状に部屋がつながっており、廊下には逆走できないベルトコンベアがある。別の部屋に移動して帰ってこれる部屋はいくつあるか
- 方向が逆のコンベアがない場合、ぐるっと回って戻ってこれるので全部屋
- ある場合、1周は無理
- 隣に行って帰ってくることができる部屋のみが数える対称
- そういう部屋はどちらかのベルトコンベアが止まっている必要がある
- 計算を横着してオーバーフローしてシステスでおちた。初めてかも
C
AB文字列からABかBBを消せるとき、どこまで短くできる？
- AはABでしか消せないので優先
- 前から見てAとBの数を管理しながらABを消す
- 残りは...BBBAAA...の状態
- BBを消せるだけ消す
D
ブーメランの進行方向を曲げる障害物を各行各列2個まで置ける。各場所から投げたブーメランがai回曲がるような置き方を作れるなら作れ
- a={ ... 2 2 ... } はダメ
- ほかにもダメなパターンがある
- ai=2,3の置き方は右の列にも影響するので矛盾が発生しうる
- 3の右側は{1,2,3}の列における
- 2の右側は{1}の列における
- 目的の列のうち最も左を採用してよい
- 障害物を奥から実装していく
E
長さnの数列を{ai}->{x,ai-x}のようにして要素数kにするとき、aiの二乗和を最小化する数列は
- 解けず
Codeforces Round 676
A
a xor x + b xor x を最小化するx
- 知らんけどaとbのxorっぽい
- 通った
- 2進数にして各桁を見る a xor x と b xor x を両方0にしたいけどその桁が違っていたら無理
- これはxorそのもの
B
S（左上）からG（右下）まで0と1のどちらをたどっても行けないように2回まで迷路を反転させよ
- Sの下と右、Gの上と左のみに注目して、Sをどちらかで固めてGをもう片方で固めると途中に関係なくうまくいく
C
文字列を回文にする操作を出力してください
- 範囲を大きくとって、一回操作するだけでもだいぶ回文に近いものが得られる
- あとは最後の帳尻合わせを頑張る
D
ハチの巣状の二次元座標を目的の場所まで移動する最小コストはいくらか。1マス移動するコストは移動方向によってそれぞれ異なる
- 六角形でも所詮は二次元
- 移動経路が口から〼(ますの字)に変わっただけ
- 上下左右に加え、右上と左下が使える
- 各方向への移動に対して真っ直ぐ向かう方法と一度遠回りする（ように見える）方法の2つの経路がある
- ある方向に移動するコストはこの2つのminになる
- あとは目的の場所に移動するための各方向への移動回数をかける
