初回 -> はじめに
M-SOLUTIONS プロコンオープン 2020に参加しました。
4完です！
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 2min | - | 4ms |
| B | 3min | 貪欲法 | 6ms |
| C | 4min | しゃくとり法 | 40ms |
| D | 13min | 貪欲法 | 6ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
青Performanceを初めてとりました。嬉しい。
その時点での最善手を繰り返すことを貪欲法といいます。
（名前は知っていて使ってもいたのですが、正しい定義を知りませんでした)
C問題
評点についてはひとつ前の学期からの比較ができればいいです。
つまり、実際の値を求める必要はありません。
A - Kyu in AtCoder
int x;
cin >> x;
cout << 10 - x / 200;
級位は200刻みで変わるので、xを200で割った切り捨ての値を使うと解けそうですね。
今回はうれしいことに、同じ級位のレーティング内では200で割った切り捨ての値は変わりません。
そのため、そのままx / 200という値を使えます。
（例えば[400, 599]という範囲ではなくて[501, 700]という範囲だった場合、(x - 101) / 200のような調整が必要です。）
8級の時に合わせて10から引く調整をして答えになります。
B - Magic 2
int a, b, c, k;
cin >> a >> b >> c >> k;
int cnt = 0;
while(a >= b)
{
b *= 2;
cnt++;
}
while(b >= c)
{
c *= 2;
cnt++;
}
cout << (cnt <= k ? "Yes" : "No");
その時点での最善手を繰り返すことを貪欲法といいます。
A < B < C の状態になるように実際に操作して、その時の操作回数をKと比較しました。
「真に」大きいとあるので、不等号の書き方に注意です。
C - Marks
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i = 0; i < n; ++i)
{
cin >> a[i];
}
for(int i = 0; i < n - k; ++i)
{
cout << (a[i] < a[i + k] ? "Yes" : "No") << endl;
}
K+1 <= i <= N となるすべてのiを試すとO(NK)となり、制約より時間内に解けません。
また、A_i = [1, 10^9]なので評点を直接求めようとするととても大きな数字になってしまいます。
最大で10^(9 * 200000)程度になってしまいます。
あまり詳しくないのですが、桁に上限がないpythonでもこれは表せないのではないでしょうか。。。
この問題で使うのはしゃくとり法です。(評点を直接は求めないので厳密には違うかもしれません)
評点についてはひとつ前の学期からの比較ができればいいです。つまり、実際の値を求める必要はありません。
学期がひとつ進むと、評点の要素はi番目が消えてi + K + 1番目が新しく追加されます。
つまり、これまでの評点から「i番目の要素」を割って「i + K + 1番目の要素」をかけた数が新しい要素になります。
これを比較するには、「i番目の要素」と「i + K + 1番目の要素」の大小を比較すればいいですね。
こうすることでn - k回の比較で済み、実際の評点を求めなくても答えがわかります。
D - Road to Millionaire
ll n;
cin >> n;
vector<ll> a(n);
for(int i = 0; i < n; ++i)
{
cin >> a[i];
}
ll val = 1000;
ll min_val = a[0];
ll max_val = a[0];
a.erase(unique(a.begin(), a.end()), a.end());
for(int i = 1; i < a.size(); ++i)
{
if (a[i - 1] > a[i])
{
val += (val / min_val) * (max_val - min_val);
max_val = min_val = a[i];
}
max_val = max(max_val, a[i]);
min_val = min(min_val, a[i]);
}
val += (val / min_val) * (max_val - min_val);
cout << val;
株価が安いときに買って高いときに売れば利益が出ます。
株価が単調減少を続けている間は待って、株価が上がる直前に買えば株を安くたくさん買えます。
そして、単調増加を続けている間は待って、株価が下がる直前に売れば売却額は大きくなります。
つまり、株価が下がるまで待って、下がったときに「これまでの最安値」で買って「下がる前の価格」で売ると利益を最大化できます。
その時の買値と売値の差額が利益になります。
表現がおかしいですが、「株価が下がったとき」に買って売るようにします。
買わないほうが良い場合もあるためです。
この方針で貪欲に実装すれば答えが出ます。
以上です。ありがとうございました。