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

HACK TO THE FUTURE 2021 予選(AtCoder)

20*20のマスに置かれた100枚のカードをstackに順番に回収する移動回数を最小化せよ。最終的に順番になればよく、途中で順番が狂うようなpop操作やpush操作を行っても良い

• とりあえず順番に回収してみる
• x->x+1の移動経路にx+2があればそれを回収しておいて、x+1を拾う前にpop
• 10*10に集めてそこから順番に回収（おもってたより強かった）
• 移動するとき近くのものもまとめて拾っちゃう
• 端に移動するとき近くのものをまとめて拾って、中心のほうを通るときに落としていく
• 拾う半径を色々試したり、10*10に収める戦法も考えて最良を選択 みたいなことをやった。バグってたっぽくて順位が全然上がらなかった。TSPとかも一瞬浮かんだけどめんどくてやめた

AtCoder Beginner Contest 182

A

フォロー数制限はフォロワー*2+100. 今のフォロー数Bとフォロワー数Aだとあと何人フォローできるか

• 数式に起こすだけ (A*2+100)-B

B

2以上の整数で数列Aのうち割り切れる要素数を最大化するものをひとつ

• 要素の最大値は1000なのでこれ以下の整数を全部試すだけでいい

C

0を含まない数が与えられる。何桁消すと3の倍数にできるか（全部消さないといけない場合はそれを報告）

• 数学的な考察をしたくない
• DPをすればいい
• 制約はゆるいので適当でいい
• 「i桁見て、j個消して、mod3がkになるものがあるか」でいい
• よく考えるとbit全探索が間に合いますね

D

ロボットが行動する。最も右に至った瞬間の座標は

行動：A1進む→A1進んでA2進む→A1進んでA2進んでA3進む→…

• 累積和は欲しい
• 累積和によって毎行動後にどの座標に至るかはそれぞれO(1)で求まる
• 単一の行動中最も右に至る瞬間はいつか
• 累積和の累積maxを持っておけば簡単

E

H*Wマスにブロックと電球が置いてある。電球の光が届くマスはいくつか

• 愚直は
• さすがにTLE そのための2.5secではないらしい
• すでに光が届いてる場所を考える必要はない
• そのマスにあたっているのが縦の光か横の光か区別しないと変なところで打ち切ることになるのでそこは注意

F

コインA1=1<A2<A3... がありA2%A1==0, A3%A2==0...。X円の商品を買う。自分も店員も金額に応じた最適な払い方をする。払うコインとおつりのコインに同種のものが含まれないような払い方の数は

• とっかかりもつかめなかった。以下解説を見て
• 払う金額-X=おつり 払う金額-おつり=X
• おつりをマイナス円の支払いと思うと簡単になる
• 大きい金額のコインから考えるDPだけどめっちゃ難しい