2020年3月11日　日記

3月11日

前書き

今日はピザを食べました。親の金で食べるピザは美味しいデスね。

久しぶりにあさかつに参加しました。途中で値落ちしました。生活習慣は一度失ったら取り戻すことはできません。

セグメントツリー完全に理解しました。
私は知ってしまいました。
私はもう、知ってしまいました。
私は忘れることができません。
あの日見た木の名前を僕達はもう忘れることができません。
あなたはそれを知ってしまったのです。
それは、あなたがそれを知ったことを知っています。

2020年も猫が可愛い

今日解いた問題

ABC028c - 数を3つ選ぶマン

[全探索]

店長さんの早解き記事で紹介されていた問題です。この問題、受け取った5つの値を大きい順に並べて,大きい順に a1, a2, a3, a4, a5としたときに、 a1 + a2 + a5 か a1 + a3 + a4 が答えになるんですけど、全探索でも解けるんですよね。
そっちのほうが考察がいらなくて楽なんだけど、そもそも思いついてすらいませんでした。

天才ですね。

で、この問題を解いて、全探索で解くのすげえな！ってつぶやいたら、店長ともう一人魚介類ちゃんっていう方がいるんですけど、その方たちから使える知識を教えてもらいました。

あ〜、その前に、問題文と僕が最初に書いた全探索のコード貼っておきますね。

異なる整数が 5 個与えられます。この中から 3 つ選んでその和で表すことの出来る整数のうち、 3 番目に大きいものを出力してください。

#include <bits/stdc++.h>
 
using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
int main()
{
    vector<int> a(5);
    rep(i,5) cin >> a[i];
    vector<int> sum(0);
    rep(i,5){
        For(j,i+1,5){ //for(int j = i + 1; j < 5; j++)と同じ
            For(k,j+1,5){
                sum.push_back(a[i]+a[j]+a[k]);
            }
        }
    }
    sort(sum.begin(),sum.end());
    reverse(sum.begin(),sum.end()); //ここの二行が改善されて行きます。
    cout << sum[2] << endl;
}

まずこれが僕が書いたコードデス。どの3つを足すかの5C3 = 10通りを全部試し,sumという配列に突っ込んでいく。その後降順にソートして、3番目のものを出力するというコードです。

さて、このコードを見せびらかしたら店長からメッセージが

これはおまけですが、 sort(sum.begin(),sum.end(),greater<型>()) で降順ソートできます

まじか。ということで、ここからは

sort(sum.begin(),sum.end());
reverse(sum.begin(),sum.end()); //ここの二行が改善されて行きます。

この部分がどう変わっていくかだけ見せますね。他の部分は同じです。

まずはこう

sort(sum.begin(),sum.end(),greater<int>());

greater()というものだけが加わりました。これで降順にソートできるようです。

このコードを書いたら次は魚介類ちゃんさんからメッセージが。

sort して reverse するのめんどくない？ sort(a.rbegin(), a.rend()) したい

ほう？ rbegin?rend?そんなの使えるの？絶対ウソじゃん。

sort(sum.rbegin(),sum.rend()) ;

ACです。まじか。

こんな感じで新しく使える知識が身につきました。

振り返りにもう一度問題分と完成コードを見ていきましょう。

異なる整数が 5 個与えられます。この中から 3 つ選んでその和で表すことの出来る整数のうち、 3 番目に大きいものを出力してください。

#include <bits/stdc++.h>

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)

int main()
{
    vector<int> a(5);
    rep(i,5) cin >> a[i];
    vector<int> sum(0);
    rep(i,5) For(j,i+1,5) For(k,j+1,5) sum.push_back(a[i]+a[j]+a[k]);
    sort(sum.rbegin(),sum.rend());
    cout << sum[2] << endl;
}