AtCoder Beginner Contest 356に参加しました。
結果
A,B,Cの3問正解でした。
D問題何回見直してもアルゴリズム的におかしいところが見当たらなくて、どこかでオーバーフローしてるんだろうなと思ったら案の定オーバーフローしていて完全に見逃してた。
コンテスト終了後に解説見てたら気がついて修正したらACできたし、
何なら初回に提出したコードを修正したらACになった。
ソースに直書きした数値はintとして扱われるっていうのは知らなかったので、ビットシフトでオーバーフローしていたのを完全に見逃してた。結構もったいないミスだなあ。
１からNまで順に並んでいる数列のLからRまでを逆順にしたときの数列を出力する問題。
１からL-1まで出力してRからLまで出力して、R+1からNまで出力すれば解ける問題。
任意の内容でループ処理を書けるなら特に困らず解ける問題だと思う。
N個のアイテムとM個のパラメータがあって、それぞれのアイテムは各パラメータを増加させていく。
N個のアイテムすべてを消費したときに各パラメータはしきい値
を越えているかどうかを判定し結果を出力する問題。
アイテムの数とパラメータの数はそれほど多くないのでそこまで難しくないと思う。
M個のパラメータそれぞれの合計値を管理する配列を用意して、全アイテムの各パラメータの値を順番に足していく。
最後に各パラメータがしきい値を越えているかどうかを順番に確認して結果を出力する。
二重ループと配列を使ったデータの処理ができれば解ける問題だと思う。
N本の鍵があって何本かは正しい鍵で、何本かはダミーの鍵になっている。この時K本以上の正しい鍵を使えば鍵が開く。
こういった状況で何本かの鍵を同時に使って鍵が開くかどうかのテストをM回行った。
N本の鍵のどれが本物でどれがダミーかのパターンの内テスト結果に矛盾しないパターンは何通りあるかを答える問題。
鍵の本数は最大でも15なので全通りのパターンを確認してもなんとか時間以内に処理が終わらせられそう。
全通りの処理としてビット全探索を採用して全パターンの処理をすることにした。
1パターンごとにMケースあるテスト結果に矛盾しないかどうかを確認して、矛盾しないパターンの数を数えていき、
最後に出力した。
全通りの探索を正しく実装できるかどうかがポイントな問題だと思う。
ビット全探索を知っているかどうかがかなり影響しそう。
最後までオーバーフローに気付けなくて時間内には解けなかった問題。ソースに直書きした数値はintになるっていうのを知らなかったのと、任意のビットが1かどうかの判定にC問題で出てきたビット全探索で使っている処理を流用したのがまずかった。
ビット全探索だとintの範囲で収まることが多かったから用意してたコードメモがintにしか対応してなかったのが失敗だったなあ。
NとMが与えられるので
を計算して出力する問題。
NとMはともに
未満とかなり大きな数になる可能性がある。
愚直に0からNまで順番に論理積を計算して1となっているビットの数を数えて足してとやっていたらTLEになる。
別の解き方を考えていった考察としては以下の通り
- 論理積なのでkとMの両方で1となっているビットだけが加算の対象となる。
Mの時点で0となっているビットはそもそも処理する必要がない。
- 各ビットを個別に注目すると1ビット目は010101・・・2ビット目は00110011・・・といった具合に周期性がある。
なので０からNまでを順番に処理するのではなく、
N以下の内１ビット目が１になる数字はいくつあって、
２ビット目が１になる数字はいくつあって、・・・を計算して最後に順番に足していけば解けると考えた。
これなら６０ビット分の数値計算をするだけて済むので処理時間はかなり短くなる。
N以下の数値の内iビット目が1になる数値の数は、
周期何周分とあまりいくつかを計算して、1周期の中ではビットが1になるのはいくつあって、あまりのうちビットが1になるのがいくつあるのかを計算すれば求められる。
- 周期数は
あって、1周期のうちの半分は1なのでまずは
- あまりは
あって、そのうち前半の
はビットが0になる。なのでビットが1になる数値の数は
になる。
この2つの値を足すと、kとMの論理積の内ビットiが1となる数値の数になる。
60ビット分この処理を行って、最後に60ビット分の算出結果を合計すれば求めたい値を算出できる。
