Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

M-SOLUTIONS プロコンオープン 2020　A ~ D解説(Python3)

ABC参加記

M-SOLUTIONS プロコンオープン 2020の解説です！

当日は都合により参加が出来なかったのですが、バーチャル参加しました！！

結果は4完40分程度でした。本番だと水パフォだったので参加したかった...

(この記事は解法を詳細に説明しているため約15分程度で読めます)

 

 

A問題-「Kyu in AtCoder」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_a

問題概要:

最高レーティングXが与えられるので、問題文のルールに従って保有する級を示す数字を出力せよ。

解法1:

愚直に、全ての条件を列挙し実装する方法です。プログラミング初心者の方は条件分岐を書く練習となり良い問題となったでしょう。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15498772

解法2:

実は、今回　求める級をxとおくと、

(10-X/200)=xという式が成り立ちます。

(ここで/は小数切り捨ての割り算であることに注意して下さい)

よって、この式を出力してもAC(正解)することが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15498809

 

B問題-「Magic 2」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b

問題概要:

整数A,B,Cが与えられます。

以下の操作を考えます。

  • 3個の整数うちいずれか1個の整数を選び2倍する。
  • これをK回行う。

K回以内の操作(0回でも大丈夫です)で、

A＜B＜Cが成り立つようにできるかを判定しなさい。

 

解法:
  • 整数Aに対する操作回数をx
  • 整数Bに対する操作回数をy
  • 整数Cに対する操作回数をz

とすると、

  • (x+y+z) \leqq K

が成り立ついずれかの(x,y,z)で操作を行うことによりA＜B＜Cが成り立てばよい。

つまり、

  • A*2^{x} ＜ B*2^{y} ＜ C*2^{z}

が成り立つ組み合わせが1つでもあればよいということになります。

これは、制約が小さいことから全探索により解くことが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15459754

 

C問題-「Marks」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c

問題概要(短縮):

評点が以下のようにつけられる。

  • 直近K回の期末テストの点数を掛け合わせたもの
    (ただしK-1学期までの評点はつけられないものとする)

K+1≦i≦Nを満たすそれぞれのiについてi学期の評点がi-1学期の評点より真に高いかを判定し、その判定結果を出力せよ。

 解法:

愚直にK回分の評定それぞれ求めようとすると、各計算にK回、その計算がN-K+1回繰り返されるので、計算量はO(NK)となり、これは制約を考えると4×10^{10}回程度の計算量となるためTLE(実行時間制限超過)となります。

それどころか、A_iの制約に注目すると1 \leq A_i \leq 10^9と言う表記がなされています。

仮に、N = 2000 , K = 1000で、全ての評定A_iが10^9であった場合を考えます。

すると、10^9を10^3回掛けることになります。一般的にコンピューターは多倍長整数の計算が苦手なのでNが小さくてもこのような計算をすると時間がかかってしまいます。

ここでPoint。

Point【多倍長整数の計算】

コンピューターにとって多倍長整数(とても長い整数)のかけ算は苦手なので、時間が多くかかってしまう。

これは、オーバーフロー(int型の範囲を超える)とは違う意味なので履き違えないようにしましょう。(そもそも、Pythonはint型のオーバーフローが発生しないのでオーバーフローを考えなくても良いのですが...)

では、どのようにして計算量を減らすのでしょう。

分かりやすくするために、x学期の評点をM_xとおきましょう。

例えば、入力例1の場合

M_3 = A_1×A_2×A_3

M_4 = A_2×A_3×A_4

M_5 = A_3×A_4×A_5

 

となります。ここで、もう気づいた人もいると思いますが、それぞれのM_iについては共通項があります。

これを考えると、隣合う2つのM_iについて(以降L,Rとおきます)

Rの最後の項がLの最初の項よりも真に大きい時、RはLより真に大きいということがいえるので

問題文における

i学期の評点がi-1学期の評点より真に高い　

という条件を満たすことになります。(公式解説を見た方が分かりやすいかも...)

そのため、これはN-K+1組ある

A_iとA_{K+i}の関係を調べれば良く、

計算量もO(N)となります。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15459769

 

D問題-「Road to Millionaire」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_d

問題概要:

問題文にあるとおりに株をうまく取引したとき、最終的な所持金は最大でいくらになるかを出力せよ。

解法(取引日で行動を変える):

取引日によって行動を変える貪欲法によって解くことが可能です。

(とにかく株を買えばお得になるように行動するということです)
行動パターンは以下の通りです。

  • 1日目
    株を買う、もしくは買わないの2択です。
    ここで、(1日目の株価) ＜ (2日目の株価)が成り立っていれば株を買う
    成り立っていなければ株を買わない　という行動が最適です
  • i日目(2≦i≦N-1)
    株を持っているか持っていないか・i+1日目の株価との比較で最適な行動がそれぞれ変化します。
    株を持っている場合
    i+1日目の株価がi日目の株価より高い、または同じならば売らない
    i+1日目の株価がi日目の株価より低いならば売る
    という行動が最適です。
    株を持っていない場合
    i+1日目の株価がi日目の株価より高い、または同じならば買う
    i+1日目の株価がi日目の株価より低いならば買わない
    という行動が最適です。
  • N日目
    株を売るか、株を所有していなければそのまま株を買わない
    という行動が最適です。

幸いにもNの制約は小さいので、このような複雑な貪欲法のシミュレーションを行うことにより解くことが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15467841

 

以上、M-SOLUTIONS プロコンオープン 2020の解説でした！

公式解説にはこの他にも別の解法もあるので、実装できる人はやってみましょう！！

質問・指摘点などがあればコメントなどでお願いします...!!