トップ > AtCoder ABC221

AtCoder ABC221

ABC221参加しました。

atcoder.jp

一部の問題は省略します。  

C - Select Mul

解説 - AtCoder Beginner Contest 221

提出 #26341648 - AtCoder Beginner Contest 221

とっつきにくい問題でしたが、例を上げて考えていくとわかってきました。

まず積a,bが最大になるには、a,bに含まれている数が降順に並んでいる必要があります。
例えば
a = {1,2,3}
b = {4,5}
の場合、a*bの最大は321 * 54になります。

こう考えれば、あとは、a,bに入る数の組み合わせを考えればよく、これはbit全探索でいけます。
Nは最大でも10桁程度で210程度の組み合わせだけ考えればいいからです。

D - Online games

解説 - AtCoder Beginner Contest 221

提出 #26342343 - AtCoder Beginner Contest 221

imos法っぽいですが、ちょっと工夫が必要な感じに見えました。

公式解説を紐解いていきます。

この問題は、イベントタイミングだけを処理してログインユーザー数を増減させていくことが大事です。サービス開始から今までの日にちを全部forで処理していくと、到底時間が足りません。

ここで言うイベントとは(発生時間(int), アクション(ログイン/ログアウトのint) )の組です。
後の利便性のため、ログイン = 1, ログアウト=-1とします。

このときイベントが起きない時間帯は、ずっとログインユーザー数一定で時間だけが経過していきます。また、最後のイベントが起きたあとはずっとログインユーザー数は遷移しません。

なので、まずイベントが起きた時間が早いもの順でソートします。

その後、それぞれのイベントについて処理していきます

public class EventLog
{
    public long time = 0;
    public int login = 0;//1 : login, -1 : logout
}

...(中略)...
var loginDays = new long[N];
for(int i = 0; i < N; ++i) { loginDays[i] = 0; }//初期化

long loginUsers = 0;
for(int i = 0; i < eventTime.Count - 1; ++i)
{
    //1. あるイベントを処理して総ログインユーザー数を増減
    loginUsers += eventTime[i].login;//login
    if (loginUsers > 0)
    {
        //2.そのイベントにより、総ログインユーザー数(=loginUsers人)が何日続くか?
        long day = eventTime[i + 1].time - eventTime[i].time;
        loginDays[loginUsers - 1] += day;
    }
}

1.のイベント処理後に、総ログインユーザー数が変化します。 2は少しややこしいですが、この総ログインユーザー数のまま何日続くかを計算します。

仮にi+1番目のイベントが同じタイミングであれば(=i+1番目のtime = i番目のtime)、2のday=0で変化はありません。これで、同じ日にイベントが沢山重なっていても結果には影響しません。

仮にi+1番目のイベントがものすごく未来にあれば、i番目のイベントを処理した結果のログインユーザー数がずっと続きます。つまり、イベントが非常に間をおいて起きても、間の期間のログイン日数を管理できます。

なお2で loginUsers - 1しているのは、ログインユーザー数0人は答えに影響しないからです。loginDays[0]=ログインユーザー数1人の期間ですね。

感想

C問題は、このブログを書いているときになってようやく考えが整理できてきた。

D問題は、結果から考えると数行だけれど、それをコードに起こすまでに、配列の扱いをうまく工夫しないと時間がかかる問題だったように思います。