競プロ初心者日記【C++】

一緒に競プロ頑張って行きましょう!

【競プロ】得点、投票系の順位で使うアイデア

得点、投票系の順位で使うアイデア

殴り書きをゆるしてください。(ってか自明のこと)
これはJOI 2011 予選問題2の解法で使われました。

順位の付け方

点数が大きい順に番号を振る場合、その数より大きい数の個数が順位となる。

例えば、点数が

生徒1 > 5
生徒2 > 4
生徒3 > 3
生徒4 > 2
生徒5 > 1

であった場合、生徒1より点数が大きい人はいないので、生徒1の順位は0(1番目)になる。
同様に、生徒4より点数が大きい人は、生徒5を除いた3人であるため、順位は3(4番目)になる。

※これは順位が同率になる場合にも適用できる。
生徒1 > 5
生徒2 > 5
生徒3 > 5
生徒4 > 5
生徒5 > 1

であった場合、生徒5以外の順位は同率0位(1番目)となるが、生徒5は4位(5番目)となる。

実装例
#include <iostream>

using namespace std;

int main()
{
    int n;
    cout << "生徒の数 > ";
    cin >> n;
    
    int student[n];
    for (int i = 0; i < n; i++){
        cout << "student" << i << "の得点 >> ";
        cin >> student[i];
    }

    int s_rank[n] = {};

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (student[i] < student[j]) s_rank[i]++;
        }
    }

    for (int i = 0; i < n; i++){
        cout << "student[" << i << "]の順位は > " << s_rank[i]+1 << endl;
    }
}
input1
5 1 2 3 4 5
output1
student[0]の順位は > 5
student[1]の順位は > 4
student[2]の順位は > 3
student[3]の順位は > 2
student[4]の順位は > 1
input2
5 5 5 5 5 1
output2
student[0]の順位は > 1
student[1]の順位は > 1
student[2]の順位は > 1
student[3]の順位は > 1
student[4]の順位は > 5

【競プロer必見!】一番簡単な四捨五入の仕方!

こんにちは。まつげんです。 今日もバイトしてました。明日も8時間バイトです。

今回は「四捨五入」の仕方について殴り書きしていこうと思います。
いつもみんながどうやって四捨五入をしているか気になっていたんですよね。だれかもっと簡単な方法があったら教えてください。

早速本題ですが、自分は「int型へのキャスト」を利用しています。
キャストというのは、簡単に言うと「ある型を別の型へ変換したい!」ってときに使うやつです。
(変換したい型)変数名でキャストできます。

コード

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double a = M_PI; //円周率 3.14159...

    cout << a << endl;
}

表示結果

3.14159

しっかり円周率が出てきましたね。
ちなみに、M_PIを使うには#include <cmath>する必要があります。

ここで、今あるdouble型をint型へキャストすると...

コード

int main()
{
    double a = M_PI; //円周率 3.14159...

    cout << a << endl;

    cout << (int)a << endl;
}

表示結果

3.14159
3

(int)aで3が出てきましたね。これはdouble型であったaがint型にキャストされて、小数点以下が無視されたためです。
他でも試してみると、

コード

int main()
{
    double a = 1.1;
    double b = 1.5;
    double c = 1.7;
    double d = 1.999999;

    cout << (int)a << endl;
    cout << (int)b << endl;
    cout << (int)c << endl;
    cout << (int)d << endl;
}

表示結果

1
1
1
1

こうなりました。すべて1になっています。
このことから、int型へのキャストは切り捨てになることがわかりますね。
四捨五入ではこの切り捨てを上手く利用します。

コード

int main()
{
    double a = 1.49999;
    double b = 1.50000;

    if (a >= (int)a + 0.5) a++;
    if (b >= (int)b + 0.5) b++;

    cout << (int)a << endl;
    cout << (int)b << endl;
}

表示結果

1
2

これでわかりましたかね。自分の四捨五入のやり方はこれです。
四捨五入したい変数を一旦キャストし、小数点以下を切り捨てたところで0.5を足したものと比較しています。
わかればすごく簡単ですよね!?!?!?!?(威圧)

これでめでたしめでたs....

なぬうぅぅぅぅぅ!?!?!?

f:id:matsugen1234:20181006212146p:plain

コード

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    double a = 1.4999999;
    double b = 1.500000;

    cout << round(a) << endl;
    cout << round(b) << endl;
}

表示結果

1
2

もうすでに四捨五入する関数roundが用意されてるだと!?!?!?


めでたしめでたし.....

ABC001【C 風力観測】の解き方!

AtCoder Beginner Contest 001【C 風力観測】の解き方を解説します!

問題文

(略)

問題文の要約

16方位に分けた方角(風向)を角度で与えるので、それに対応した1~3文字の方角(風向)に直して出力すること。
風速を[m/min]の単位で与えるので、それに対応した0 ~ 12の風力を出力すること。
例外として、「風力が0」の場合は「方角(風向)は 'C' 」とすること。

入力

Deg Dis

Degは方角(風向)のこと。本来の角度を10倍した値が与えられる。
Disは風速(風程)のこと。単位は(m/min)(メートル)で与えられる。

入力の制約

0 <= Deg < 3,600
0 <= Dis < 12,000

出力

方角(アルファベット3文字) 風速

Sample Code(C++)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    float deg, dis;

    string str[17] =
    {"N", "NNE", "NE", "ENE", "E", "ESE", "SE", "SSE", "S", 
    "SSW", "SW", "WSW", "W", "WNW", "NW", "NNW", "N"};

    float dis_table[14] =
    {0.2, 1.5, 3.3, 5.4, 7.9, 10.7, 13.8, 
    17.1, 20.7, 24.4, 28.4, 32.6, 200.0};

    int dis_ans;

    cin >> deg >> dis;
    
    deg /= 10;
    dis /= 60;
    dis = round(dis * 10) / 10;

    for (int i = 0; i < 13; i++){
        if (dis <= dis_table[i]){
            dis_ans = i;
            break;
        }
    }
    
    double current = 11.25;
    int index;

    if (dis_ans == 0){
        cout << "C" << " " << 0 << endl;
        return 0;
    }
    else {
        for (int i = 0; i < 17; i++){
            if (deg < current){
                index = i;
                break;
            }
        current += 22.5;
        }
    }

    cout << str[index] << " " << dis_ans << endl;
}

コードの説明

全てをincludeする悪魔のヘッダファイル

#include <bits/stdc++.h>

について知りたい方はこちら!

matsugen.hatenablog.jp

1. 準備

//8:
string str[17] =
{"N", "NNE", "NE", "ENE", "E", "ESE", "SE", "SSE", "S", 
"SSW", "SW", "WSW", "W", "WNW", "NW", "NNW", "N"};

float dis_table[13] =
{0.2, 1.5, 3.3, 5.4, 7.9, 10.7, 13.8, 
17.1, 20.7, 24.4, 28.4, 32.6, 200.0};

下準備として、方角の文字が順番に入ったstring型 strと、各風速の上限を入れたfloat型 dis_table を宣言しました。 どうやって使うかは、後ほど解説します。

2. 入力

//18:
cin >> deg >> dis;

方角(以下deg) 風程(以下dis) の順に読み込みます。

2.主な処理

//20:
deg /= 10;
dis /= 60;
dis = round(dis * 10) / 10;

degは本来の値から10倍された値で入力されるので、本来の値に戻すために10で割ります。
disは、1分間のものが与えられるので、秒単位に直すために60で割ります。
そのあと、roundを使って、小数点第2位を四捨五入します。
⇩roundがわからない、知りたい方は神のサイトへ!⇩
cpprefjp.github.io

//24:
for (int i = 0; i < 13; i++){
    if (dis <= dis_table[i]){
        dis_ans = i;
        break;
    }
}

for文でdisの上限に当てはまるものを探します。
見つかったら、その添字をdis_ansに代入し、for文を抜けます。

double current = 11.25;
int index;

if (dis_ans == 0){
    cout << "C" << " " << 0 << endl;
    return 0;
}
else {
    for (int i = 0; i < 17; i++){
        if (deg < current){
            index = i;
            break;
        }
    current += 22.5;
    }
}

double型 currentを11.25で初期化して宣言しました。
int型 indexも同時に宣言します。

ここで問題文の例外に対応します。
disが0のとき、degは 'C' を出力するので、方角 'C'、風速 0 を出力してプログラムを終了します。

disが0でないとき、degをfor文で回します。
もし、degの範囲が見つかったら、その添字をindexに代入し、ループを抜けます。 degの範囲でない時、方角の間隔が22.5度なのを利用して、currentに22.5を足す。 その後にまた範囲の照会を行います。

3. 出力

cout << str[index] << " " << dis_ans << endl;

先程確保したindexを添字として扱い、一番最初で準備したstring型 str[index]、dis_ansを出力します。

AC状態

f:id:matsugen1234:20180720101629p:plain
AC状態
https://abc001.contest.atcoder.jp/submissions/2870167

終了!

おつかれさまでした!

次回はABC002【C 正直者】を解説します!

ではまた!

僕が競プロで使っているC++のテンプレート

こんにちは!

今日は競プロで使っている自分のテンプレートをメモりたいと思います!

Templete(C++)

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{

}

これです!短いですね。
一つ一つ解説していきます。

1. 全てをincludeする悪魔のヘッダファイル

#include <bits/stdc++.h>

これはインパクトが半端ないですよね。
すべてのヘッダファイルがインクルードされます。
自分も最初にこれに出会ったときは、もう焼きそばが食べたくなりました。
これはGCCをお使いの方が利用いただけます。

2. ループを簡略化して書くためのマクロ

//2:
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)

1行目は普通のループ。
2行目は逆ループ。
3行目は最初の数値を指定してからのループです。

使用例
//1からnまでの合計を求める
int sum = 0;
REP(i, n) sum += i + 1;
// for (i = 0; i < n; i++) sum += i + 1;

3. 最大値として扱うためのINF

//5:
#define INF 2e9

最小値を求めるときなどの、変数を大きな値で初期化するときなどに使います。
一般的には、

#define INF 1e9

が多いのですが、自分はなんとなく2にしました。気まぐれです。

4. vectorなどの全範囲指定を簡略化

//6:
#define ALL(v) v.begin(), v.end()

v.begin(), v.end()って書くのめんどくさい()

使用例
//初期 {4, 3, 2, 1} を {1, 2, 3, 4} へ昇順ソートする

vector<int> a{4, 3, 2, 1};
REP(i, 4) cout << a[i] << " ";
cout << endl;

sort(ALL(a));
//sort(a.begin(), a.end());
REP(i, 4) cout << a[i] << " ";
cout << endl;
出力
4 3 2 1
1 2 3 4

5. std::って打つのめんどいじゃん?

//7:
using namespace std;

これ書いとくと std::cout や std::cin などが std:: と書かなくとも動くようになります。

6. やっぱ5000兆、扱いたいでしょ。

//8:
typedef long long ll;

日常的にも5000兆って結構使うと思うんですよね。

でも5000兆が入る型を用意するために毎度 long long って打つの嫌じゃないですか。

これを使えば ll と打つだけで5000兆があなたのものになります。

7. おわり!

どうでしたでしょうか。お探しのものは見つかりましたか?
まあ、基本みんな5000兆目当てなのでもう最後だけで十分でしたね。

気になることがあればコメント欄へお願いします!

ではまた!

ABC001【B 視程の通報】の解き方!

AtCoder Beginner Contest 001【B 視程の通報】の解き方を解説します!

問題文

気象情報は、世界中に様々な形で流れています。そのひとつの地上実況気象通報式 (SYNOP) では、視程 (肉眼で物体がはっきりと確認できる最大の距離)を、次の規則に従って、VVという値 (通報式) に変換して報じます。

  1. 0.1km 未満: VVの値は 00 とする。
  2. 0.1km 以上 5km 以下:距離 (km) を 10 倍した値とする。1 桁の場合は上位に 0 を付す。 例えば、2,000m =2.0km ならば、VVは 20 である。同じく、200mの場合VVは 02 である。
  3. 6km 以上 30km 以下:距離 (km) に 50 を足した値とする。 例えば、15,000m =15km ならば、VVは 65 である。
  4. 35km 以上 70km 以下:距離 (km) から 30 を引いて 5 で割った後、80 を足した値とする。 例えば、40,000m =40km ならば、VVは 82 である。
  5. 70km より大きい:VVの値は 89 とする。

いま、あなたに視程の距離をメートルで与えるので、上記のルールに従って計算されるVVを出力するプログラムを作成してください。 なお、VVは必ず(上位の 0 を含めて)2桁の整数であり、上記のルールに従って計算した時に整数にならないような入力や、上記の範囲に入らない入力(例:5km より大きく 6km 未満) などはありません。

入力

m

入力の制約

0 <= m <= 100,000

単位はメートル

出力

各条件に合わせて出力

Sample Code(C++)

#include <iostream>
#include <cstdio>    //C言語でかけるようにするため
using namespace std;
 
int main()
{
    int m;
 
    cin >> m;
 
    if (m < 100){
        cout << "00" << endl;
    }
    else if (m <= 5000){
        printf("%02d\n", m / 100);
    }
    else if (m <= 30000){
        cout << 50 + m / 1000 << endl;
    }
    else if (m <= 70000){
        cout << ((m / 1000) - 30) / 5 + 80 << endl;
    }
    else {
        cout << 89 << endl;
    }
}

コードの説明

1. 入力

//10:
cin >> m;

mに入力をします。

2.主な処理&出力

//12:
if (m < 100){
    cout << "00" << endl;
}

if文を使って出力する値を決める!
まずはif文が、値の小さい順に比較するように注意する!
理由:宇宙の法則でそう決まっています。
(最初から if (m <= 70000) にしてしまうと、100未満もここで処理が終わってしまうため。)
m が 100 より小さいときは "00" を出力

//15:
else if (m <= 5000){
    printf("%02d\n", m / 100);
}

m が 5000 '以下' の場合、0埋め2桁で (km) を 10 倍した値(メートルから1 / 100 倍にした値)を出力する!
ここではC言語の printf を使っています!(cout だといろいろめんどくさいため)
参照:C++ の iostream フォーマット指定早見表

C++上でCを記述するためには
//2:
#include <cstdio>

を書く!

//18:
else if (m <= 30000){
    cout << 50 + m / 1000 << endl;
}

mが30000 '以下' の場合、(km)に50を足した値を出力!ばきゅーん!

//20:
else if (m <= 70000){
    cout << ((m / 1000) - 30) / 5 + 80 << endl;
}

mが70000 '以下' の場合、
1. kmになおす
2. 30引く
3. 5で割る
4. 80足す
以上!朝ごはん食べるより作るほうが難しいまである。

//23:
else {
    cout << 89 << endl;
}

mが70000より大きい場合、"89"を出力する!

AC状態

f:id:matsugen1234:20180717105316p:plain
AC状態
実行時間も十分ですね。

終了!

おつかれさまでした!

次回はABC001【C 風力測定】を解説します!

ではまた!

ABC001【A 積雪深差】の解き方!

AtCoder Beginner Contest 001【A 積雪深差】の解き方を解説します!

問題文

ある時刻の積雪深 H1と その 1 時間前の積雪深 H2 が与えられます。この時、この 1 時間の積雪深差 H1 − H2 の値を計算して出力してください。

入力

H1
H2

入力の制約

0 <= H1 <= 2000
0 <= H2 <= 2000

出力

H1 - H2

簡単ですね! ボタン付けの半分の時間でできます!

2つの数字が入力されるので、その差を出力するだけです。

Sample Code(C++)

#include <iostream>
using namespace std;

int main()
{
    int a, b;

    cin >> a >> b;

    cout << a - b << endl;
}

コードの説明

// 8:
cin >> a >> b;

cinのあとに2つ並べることで順番に入力します。

//10:
cout << a - b << endl;

a - b(H1 - H2)を出力します。

以上です!

ボタン付けの半分より早かったですね!

まばたきしている間に完成しました!

AC状態

f:id:matsugen1234:20180713195751p:plain
AC状態

終了!

おつかれさまでした!

次回はABC001【B 視程の通報】の解説をします!

ではまた!

競プロはじめてみた!

こんにちは。matsugenです。

最近、C++で競プロをはじめました!

自分用としてメモをこのブログに載せていきたいです!

#include <iostream>
using namespace std;

int main()
{
    cout << "Hello, Hatenablog!" << endl;
}