2020/12/5に開催されたコンテストの感想

鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）

A

2~N（Nは30以下）のどれで割っても1余るN以上10¹³以下の整数を出力

• 2からNまで全部かけた数はどれで割ってもあまり0
• だから、これに+1
• をするとN=30のときデカすぎ
• 最低限だけかける
• どうする…？
• 素数を必要なだけかける
• log2(30) < log2(32) = 5 だから4つかけておけば2～30のどれがきても吸収できる
• あとは22223335...
• long longにするのを忘れない
• lcmに考えが至らなかった

B

"110"×10¹⁰の文字列にTは部分文字列としていくつあるか

• Tが短いときは手で解いたほうがいいんじゃない？
• T="1" ：10¹⁰ × 2
• T="0" ：10¹⁰
• T="00" ：0
• T="11" ：10¹⁰
• T="10" ：10¹⁰
• T="01" ：10¹⁰ -1
• Tが"110"の繰り返しでない場合は0（自明）
• T：(切れ端) + "110"×t + (切れ端)
• 10¹⁰ - {(左切れ端ある?) + t + (右切れ端ある?) - 1}

C

順列pに対してswap(p1,p2), swap(p2,p3), ...を一回ずつやってsortする方法（ないならない）

• 最大要素を右まで持っていかないといけない時が必ずくる
• とりあえず先にそれをやらないと詰みそう
• 大きい数の順に愚直にやっていって、まずいかどうか判断 setなりなんなり

D

長さNで、総和がM以下の数列Bすべてに対し、Bi Choose Aiの相乗を計算し、その総和 mod 10億7

• 解けず。
• dpっぽいけどこの制約じゃ無理でしょを永遠にしてた
• 解法みてひっくり返った 天才
• 形式的べき級数とかいう強い言葉も聞こえてきたので勉強しないと…

Cまでがひたすら遅かった。特にBの実装がめちゃくちゃ悩んだしペナ食らった。Aもうーんという感じで、かなりつらい結果。