AtCoder Regular Contest 001 B - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

ARC001のB問題。

解くまでに11分。もうちょっと早く解けても良さそう。

今日の一問は、ARC001より、リモコン！AtCoderはここから始まった。
今の基準だと簡単目の300点くらいかな？解くことは出来るだろうけど、「5分で解いて」ってなると水色レベル。早解きを意識してやってみよう！https://t.co/z4G3AIGT7z#chokudai今日の一問

— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 22, 2019

B - リモコン

エアコンの設定温度をA度からB度にしたい。

一度のボタン操作で以下の6つの操作のうち一つを実行できる。

• 1度上げる
• 1度下げる
• 5度上げる
• 5度下げる
• 10度上げる
• 10度下げる

操作の最小回数を求めよ。

解き方

6つの操作のうち、 最もB度に近くなる操作を繰り返していく。

という一番単純そうな解き方をした。

解説によると解き方は色々あるらしい。

サンプル2で試してみる。

19度から28度にしたい。

6つの操作を全て試す。

19 + 1 = 20
19 - 1 = 18
19 + 5 = 24
19 - 5 = 14
19 + 10 = 29
19 - 10 = 9

一番28度に近くなったのは19+10=29。

また同じように6つの操作を試す。

29 + 1 = 30
29 - 1 = 28
29 + 5 = 34
29 - 5 = 24
29 + 10 = 39
29 - 10 = 19

一番28度に近くなったのは29-1=28。

ということで操作の最小回数は2回。

コード

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
        int A, B;
        cin >> A >> B;
        vector<int> v{10, -10, 5, -5, 1, -1};
        int cnt = 0;
        while(A != B)
        {
                int diff = 0;
                int minv = 1<<29;
                for(int i = 0; i < v.size(); i++)
                {
                        if(abs(B - (A+v[i])) < minv)
                        {
                                minv = abs(B - (A+v[i]));
                                diff = v[i];
                        }
                }
                A += diff;
                cnt++;
        }
        cout << cnt << endl;
        return 0;
}

おわりに

速解きを意識したい

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com