はじめに
お久しぶりです。テスト期間のため投稿を休んでいました。テストが無事終わったので今日からまた始めようと思います。今日は、テスト期間中に受けたAtcoderで、回答ができなかったC問題とD問題の解説と、ロベールについて書こうと思います。
Atcoder ( 2019/05/25 開催 ) ABC 127
C問題
N 枚の ID カードと M個のゲートがあります。\\i番目のゲートは、L_{i},L_{i}+1,...,R_{i}番目のIDカードを持っていれば通過できます。\\一枚だけですべてのゲートを通過できるのは何枚あるでしょう？
私の回答
#include <iostream>
int main(){
int N =0, M = 0;
std::cin >> N >> M;
int L[M+2] = {0}, R[M+2] = {0};
int count[100001] ={0};
int ans = 0;
for(int i =1; i <= M; i++)
{
std::cin >> L[i] >> R[i];
}
// for(int m = 1; m <= M; m++)
// {
// for(int i = L[m]; i <= R[m]; i++)
// {
//
// }
// }
for(int m = 1; m <= M; m++)
{
// printf("%d_____________________\n",m );
for(int i = L[1]; i <= R[1]; i++)
{
// printf("L[1]の値は%d\n",L[1]);
// printf("R[1]の値は%d\n",R[1]);
//
// printf("iの番号は%d\n",i );
for(int j = L[m+1]; j <= R[m+1]; j++)
{
// printf("L[m+1]の値は%d\n",L[m+1]);
//
// printf("jの番号は%d\n",j );
if( i == j )
{
count[i]++;
// printf("チャリン\n", count[i]);
}
}
}
}
for(int i = L[1]; i <= R[1]; i++)
{
if( count[i] == M-1)
ans++;
}
std::cout << ans << std::endl;
}
結果は不正解の WA 。
Atcoderでは、計算量を考える必要がある。３重for文を使って正確な値を導き出すことができても、LTA (Long time answer) になってしまう。
この問題では、 通過できるIDカードが連続しているという点に注目します。
サンプル問題で例えるとこのようになります。
この図をみたら、 L の値は、最大値を取り、 R の値は最小値を取ればいいことがわかる。
この方法を使うと for文一つだけで実行することができる。
上記の方法でプログラムを書いてみる。
#include <iostream>
#include <algorithm>
int main(){
//NとMの値を初期化
int N =0, M = 0;
std::cin >> N >> M;
int L = 0;
int R = 0;
int L_max = 0;
int R_min = 100005;
for(int i =0; i < M; i++)
{
std::cin >> L >> R;
L_max = std::max(L_max,L);
R_min = std::min(R_min,R);
}
if( R_min >= L_max )
std::cout << R_min - L_max + 1 << std::endl;
else
std::cout << 0 << std::endl;
return 0;
}
D問題
N枚のカードがあり、i番目のカードには整数 A_{i}が書かれています。\\
あなたは、j=1,2,...,Mについて順に以下の操作を1回ずつ行います。\\
操作: カードを B_{j}枚まで選ぶ(0枚でもよい)。\\
選んだカードに書かれている整数をそれぞれ C_{j}に書き換える。\\
M回の操作終了後に N枚のカードに書かれた整数の合計の最大値を求めてください。
この問題では、 std::pair と priority_queue というものを組み合わせて使うことで解くこともできる。
サンプル問題をみてみる。
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
int main()
{
int N = 0;//カードの枚数
int M = 0;//操作の回数
int A = 0;
int B = 0;
int C = 0;
long long int ans = 0;
std::cin >> N >> M;//値を入力
std::priority_queue< std::pair<int, int> > q;//値の高いもの順
for(int i = 0; i < N; i++)
{
std::cin >> A;
q.push( std::make_pair(A, 1) );
}
for(int i = 0; i < M; i++)
{
std::cin >> B >> C;
q.push( std::make_pair(C, B) );
}
for(int i = 0; i < N; i++)
{
auto p = q.top();
std::cout << "p.first = " << p.first<< std::endl;
q.pop();
ans += p.first;
if(p.second > 1)
{
p.second--;
q.push(p);
}
}
std::cout << ans << std::endl;
return 0;
}
priority_queue では、pairの first の値で大きい順にソートしてくれる。
std::pair と std::vector の組み合わせはなかなか使い勝手が良さそうなので使えるように覚えたほうがいいと思う。
ロベールのC++
静的メンバ変数
静的メンバ変数とは、メンバ変数に static をつけることで生成できる。そして、静的メンバ変数はどれだけクラスを作っても共有することができる。
とりあえず普通の変数とコードを書いてみる。
#ifndef A_H_
#define A_H_
class A {
public:
A(int num = 0);
void Show();
private:
int m_value;
};
#endif // #ifndef A_H_
#include "A.h"
#include <iostream>
A::A( int num )
{
m_value = num;
}
void A::Show()
{
std::cout << m_value << std::endl;
}
#include "A.h"
int main()
{
A a(100);
A b(300);
a.Show();
b.Show();
}
実行結果
100
300
ここで m_value に static をつけて、静的メンバ変数にしようと思う。しかし、コンパイルしてみると、リンクエラーというものが出た。調べてみるとリンクエラーは結構厄介なエラーで場所の特定が難しいらしい。
今回は、 static が原因であった。
static をつけると必ず実体を作る必要がある。しかし、今回は実体定義のほうにstaticをつけ、実体化せずにいたのでエラーが起きた。
#ifndef A_H_
#define A_H_
class A {
public:
A(int num = 0);
void Show();
private:
static int m_value;
};
#endif // #ifndef A_H_
#include "A.h"
#include <iostream>
int A::m_value;
A::A( int num )
{
m_value = num;
}
void A::Show()
{
std::cout << m_value << std::endl;
}
#include "A.h"
int main()
{
A a(100);
A b(300);
a.Show();
b.Show();
}
実行結果
300
300
これで問題なく動作するようになった！
メンバ変数ではなく、グローバル変数に static をつけても、静的メンバ変数みたいな動作をする。しかし、メンバ変数でなければ、クラスに所属しているという意味合いが薄れてしまい、危険である。静的メンバ変数のほうが、安全で扱いやすい！
終わりに
最近暑い！
おやすみなさい。