あさかつ4/10 考察 by Rute - Ruteのプログラミング日記

あさかつ4/10が終了しました。

皆さん、お疲れ様でした！今回は、AtCoder Problemsが落ちたりするなど、いろいろとトラブルがあり、制限時間が従来より15分短かったです。

私は3完で、茶difficultyまで解くことができました。(以降A～Cまでの考察です)

A問題

https://atcoder.jp/contests/abc139/tasks/abc139_b

この問題ですが、 $B = 1$ の場合、タップを接続しなくてよいので $0$ を出力します。

それ以外( $B ＞1$ )の場合、タップを接続する必要があります。

初期値 kuti = 1と定義し、それに $A-1$ を足していき、kuti ≧ B となった段階でのタップの個数を出力すればよいです。

コード

B問題

https://atcoder.jp/contests/abc079/tasks/abc079_c

"+","-"を3つ入れる組み合わせは $2^{3}$ 通りなので、それを全通り試せば良いです。

ただし、また答えが複数存在する場合はどれを出力してもよいものとします。

とあるので、複数行出力しないように実装しましょう。

コード:

C問題

https://atcoder.jp/contests/abc079/submissions/11706044

締め切りが早い順にリストをソートする貪欲法で解くことが出来ます。

手順としては

1. 締め切りが早い順にリストをソートする

2. 以下のループをN回( i = 0 to N-1)行う

　simekiri = ls[i][0] とし、now に ls[i][1]を加算する

　now > simekiriの場合は締め切りに間に合わないので("No")を出力し、ループを終了

　また、flagの値を+1する

3. flagの値が0ならば、締め切りに間に合わなかった仕事はないので("Yes")を出力

という手順です。

コード:

以上、あさかつ4/10の考察でした。D以降は考えてみます