2021/1/9、10に開催されたコンテストの感想

AtCoder Regular Contest 111

A

10^N/Mの切り捨て mod M

• 10^N/M=Mt+x
• 10^N=MMt+Mx+α
• x=10^N mod MM / M
• M進数の下から2桁目という表現をすることができるらしい、天才かよ

B

2つの数から1つ選ぶことをN回やる、選んだ数の種類数の最大はいくらにできるか

• どっかで見たことあるぞ
• 何かでソートすればいいというような単純な問題ではない
• ユニークなものは絶対に採用
• 突然ですが、2数をその番号の頂点を結ぶ辺とするグラフに置き換える
• 次数が少ない頂点から採用し、そこから生えている適当な辺をひとつ切ることを繰り返す
• chokudai speedrunかぁ

C

N人いて、それぞれ誰かの荷物を持っている。荷物と持ち主が一致するように交換していきたい。最適な交換順を示せ。ただし各人で渡せる重さに制限がある

• コンテスト後AC
• 自分のじゃないのを持っていて、重さオーバーなら無理
• それ以外多分いけそう
• もう自分のを持っている人は退場
• いちばん重いのを持っている人が、持っている荷物の持ち主と交換
• 実装頭壊れた setをつかう

AtCoder Beginner Contest 188

A

3ポイントシュートで逆転できますか？

• 負けてるほう+3>勝ってるほう

B

Σaibi=0ですか？

• やればいい、最初オーバーフローすると思っちゃった

C

2^N人でトーナメント戦。準優勝は誰？

• やればいい
• 2^Nの入力ってどうやるっけ
• rep(i,1<<N)だわ
• 優勝と反対ブロックの勝者という解のほうがスマートだけどシミュレーションした、そしたらバグってつらい（不等号ミス）

D

料金の異なるいろんなサービスを受ける。それぞれの開始日、終了日を決めた。毎日の料金はその日受けるサービスの料金の総和だが、自由に使える定額プランもある。最安いくらか

• 日数多い
• ええい座圧じゃmapに叩き込め
• imos
• min(定額、通常の料金)*日数、の総和

E

DAGな町がある。金を買って、別の町で売る。利益は最大いくらか

• DPをする
• 各町において、利益＝売値-それ以前に訪れる町の中で最安の買値

F

±1と2倍の操作ができる。XをYにするには何手かかるか

• なんか見たことある
• X=Yは自明に0
• Xのほうがでかいなら引くしかない、以下それ以外
• YをXにする方向で考える
• 2で割るのは偶数の時にしかできない
• 加減は奇数の時しかしなくていい
• という感じで再帰関数
• 数が小さいところは注意
• バグった。コンテスト後に解説見た
• AGCででた問題じゃん