東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）に参加しました。
結果
A,B,C,D問題の4問ACでした。
普段に比べてD問題が簡単な気がした。その代わりE問題が難しかった。
A - 2^N
を出力するだけの問題。
言語に用意されている指数計算する関数を使うか、N回ループして計算すれば良さそう。
解説を見るとビットシフトで2乗の計算していて賢いなあと思った。 2の乗算ならたしかにシフト演算で計算できる。
B - Batters
野球の点数計算をする問題。
全員が同じ数だけ塁を進めるって言う設定で、進める塁の数が与えられるから
最終的に何点取れたかを計算する問題。
制約はそれほど厳しいものではないので素直にシミュレートして答えれば十分間に合う速度で解ける。
C - Filling 3x3 array
のマス目に自然数を書き込んだ時に、各行・各列の和が指定された値にする場合のパターン数を答える問題。
ある行にだけ注目すると3重ループでその行のパターンを全通り確認できる。
ただこうするとO()になるので3行分処理すると最終的にはO(
)になる。
指定される和の上限は30なので各マスに1~30のどれかを書き込むとすると最大で
だけ処理が発生する。
これ全部を処理すると時間がかかりすぎてTLEになるので、愚直に全通りを確認するのは筋が悪い。
ある行の和をにしたいので2つ値が決まれば、残りの1つは1通り決まる。
なので3重ループのところを2重ループに節約すれば最終的にはO()になる。これだと処理量の最大は
なのでなんとか間に合いそう。
解説だとこの解き方だった。
私は3重ループを2重ループに節約するテクニックを使いつつ、
各行毎に条件を満たす値の組み合わせを探して解いた。
組み合わせを探した後は、3重ループでさっき探した組み合わせを全通り試す。この処理は3重ループになるけど、合計の処理量はよりは十分小さいはず。（3つの値の和がある値になる組み合わせは
通りのうちの一部だけなので）
3重ループで全通り試しつつ、行・列ともに条件を満たす組み合わせの数を数えて出力させた。
D - Union of Interval
半開区間の和集合を計算して答える問題。
各値は何個の区間に含まれているのかを計算して、1個以上の区間に含まれている範囲の最初と最後を順番に出力させた。具体的にはimos法を使って1~の最大までの範囲で各値が何個の区間に含まれているのかを計算し、その後に尺取法を使って、半開区間に含まれている数が１以上となっている範囲を探して、見つかった区間の最初と最後を出力させた。
