量子アルゴリズムの魅力(競プロer向け)

今回は量子アルゴリズムの記事を書いてみました。私は現在M1で、この量子アルゴリズムについての研究を行っています。今回の記事はタイトル通り主に競プロer向けです。具体的には

  • 計算量の概念、\mathcal O(N) の意味が分かる

人に向けた記事です。誰でも量子計算の魅力を理解できる記事も書きたいとは思っています。しかし、まだ記事を書くのに慣れていないこともあり、ターゲットを絞った方がいいと思ったので、今回は競プロer向けとさせていただきます。そして二つの強力な量子アルゴリズム、GroverのアルゴリズムとShorのアルゴリズムについて簡単に解説しようと思います。

量子アルゴリズムとは？

「そもそも量子アルゴリズムって何？」という人も多いと思います。簡単に言うと量子コンピューターを使ったアルゴリズムです。では量子コンピューターが何か、どうやって作るのか？と聞かれると、実は私も答えることができません。 抽象的に言うと、「量子力学特有の現象を使うことで計算を行う、現代のコンピューターと比べてとても高速なコンピューター」です。 私は「量子アルゴリズムを使って何ができるか？」を研究しているだけで、量子コンピューターを作る研究をしているわけではありません。 逆に言うと、どうやって作るかを知らなくても、何ができるかは研究することはできるのです！

なんで高速に計算できるの？

これを細かく説明しようとすると、また記事の更新がしばらく止まりそうなので、重要なことだけ言います。

一つのプロセッサで並列計算ができるからです。

つまり任意の自然数nと配列A_1,A_2,...,A_nとB_1,B_2,...,B_nについて、A_1+B_1,A_2+B_2,...,A_n+B_n を１ステップで同時に計算できます。すごく速いです。厳密に言うと計算ができるだけで、結果として我々が得られるのはA_1+B_1,A_2+B_2,...,A_n+B_nの中で一つだけなので、計算には少し工夫が必要なのですが。この得られる結果が一つなのが量子特有の難しい部分なので、この解説はまた今度にさせてください。

Groverのアルゴリズムとは

これが書きたいので競プロer向けの記事にしました。Groverのアルゴリズムがどんなアルゴリズムかと言うと

\mathcal O(N)時間かかる全探索を、\mathcal O(\sqrt N)時間で行うことができる

アルゴリズムです。競プロerの方ならGroverのアルゴリズムがとても強力なアルゴリズムであることが理解できるかと思います。もともと全探索にかかる時間が\mathcal O(N^{2}) なら\mathcal O(N) 時間でできます。競プロ的にはチートですね。 このアルゴリズムを応用した様々な問題を解く高速なアルゴリズムが、現在研究されています。

Shorのアルゴリズムとは

もう一つ、Shorのアルゴリズムという有名なアルゴリズムがあります。これは

素因数分解をビット数についての多項式時間で解くことができる

アルゴリズムです。このアルゴリズムの存在が示されているため、量子コンピューターが開発されると、RSA暗号が終わるなどと言われています。 今のところ、このアルゴリズムを使うために必要なビット数を持つ量子コンピューターは、まだ存在していません。いつか開発される日が来るとは言われていますが。 このアルゴリズムは量子フーリエ変換(FFTではなくQFT)を使ったアルゴリズムです。この量子フーリエ変換を応用した様々なアルゴリズムも、現在研究されています。

すごさは分かったけど難しいんでしょ？

この二つのアルゴリズムを理解するのに必要な知識は、線形代数の知識だけです。量子力学の知識は必要ないです。この二つのアルゴリズムが、具体的にどういう計算を行うアルゴリズムなのかは、線形代数だけで理解することができます。 量子計算と言うと物理の分野だと思ってしまう方が多くいると思います。しかし実際は、数学の知識さえあれば誰でも勉強できる分野です(アーキテクチャを除けば)。 少しでも多くの競プロerの方が、量子アルゴリズムに興味を持ってくれたらなぁと思って書いてみました。興味を持った方、一緒に量子アルゴリズムの勉強をしてみませんか？

現状報告とこれから

お久しぶりです。ブログの更新がまたかなり空いてしまって、継続することの難しさを感じています。大学院生がここまで忙しいとは思っていませんでした。 単位を回収しながら、自分の研究をしなくてはならず、更に研究室のメンバーでしている輪読の勉強もしなくてはいけません。 まとまった時間をとるのは、歳を重ねるほどに難しくなっていきますね。

今回はまず、前の記事で言っていた、毎日ACチャレンジですが...

途切れてしまいました...

30日以上継続できていたので、かなりへこみました。しかし継続が結果にもつながっていると思っています。 f:id:niwapon-15:20190425002416p:plain Tenka1 Programmer Beginner Contest 2019 で初めてのパフォーマンス1600を記録できたことはとてもうれしかったです。 一度途切れてしまいましたが、これからも毎日ACは継続していこうと思っています。

ブログの更新についてですが、記事の長さを短くして、定期的に更新しようと思っています。現状、ゼミの準備などに時間をとられるため、時間のかかる長い記事を書くのは困難です。 一回のハードルを低く設定し、更新の頻度を上げるのが目的です。日本語の練習がしたくて始めたのに、続かないのでは意味がないですからね。 量子アルゴリズムについての記事をできるだけ早く書きたいと思っています。自分の一番の専門分野を、他人に説明する能力というのは絶対に必要になると思っているので。

これからも頑張っていきます。よろしくお願いいたします。

毎日ACチャレンジ

　ブログの更新がしばらく止まってしまいました。自分で週に２回は投稿したい、と宣言していながらこの体たらくですね。原因は単純明快です。量子コンピューターについての記事を書くのに、思ったより時間がかかっているからです。記事を書こうと思い、まずは自分が書きたいことを全て書き出しました。その後、書き出した内容を整理し、文章にしようとしてみました。この文章にする作業に、思ったより時間がかかっています。できるだけ早く完成させたいですね。

　それとは別に、一つの目標を立ててみることにしました。それは「AtCoderの過去問を、毎日一つはACさせる」ことです。大学の友人が以前言っていた目標を思い出して、自分も同じことをしてみようと思いました。時間があるときには400点以上の問題を解き、無いときには100点とか200点の問題を解くことにします。こうすることで、目標の達成のハードルを下げられると思っています。400点以上の問題を解いたときは、解法を自分の言葉にする努力もしてみたいと思います。

　短い記事になってしまいましたが、これからも無理のない範囲で、頑張っていこうと思います。

C++ における vector の使い方

　一昨日は ABC121 がありました。宣言した通り、ABCの結果と、問題を解くのに使えそうな C++ のライブラリについての記事を書こうと思います。今回はC++におけるvector についてです。AtCoder のコンテストに提出されている C++ のコードを読むと、配列ではなく vector を使っているものがたくさんあります。何故 vector の方が好まれているのか、ずっと気になっていました。今回は、vector の使い方について、私なりにまとめていきたいと思います。

ABC121の結果

　まずは、ABC121 の結果についてです。
f:id:niwapon-15:20190309233615p:plain
今回、初の全完を達成しました。かなり嬉しかったです。しかし、D 問題については4回も WA を出してしまいました。原因は初歩的なコーディングミスでした。更にレートを上げるために、こういうミスには、すぐ気づけるようになりたいですね。以前よりも、コーディングのスピードは上がったと思います。これからも精進を続けたいと思います。コーディングの速さと、アルゴリズムの知識、両方がもとめられるのが面白いところですね。言語に関する記事をだけでなく、アルゴリズムに関する記事も、いつか書きたいと思っています。

　ABC121 の B 問題と C 問題は、配列か vector を使って解くのが一般的だと思います。コンテスト中は、使い慣れている配列を使って解きました。この問題を解く、vector を使ったコードを書くことを目標にして、vector について調べてみました。

vectorの基本

　色々なサイトが参考になりそうでしたが、次のサイトが一番参考になりそうでした。
vivi.dyndns.org
vector は、要素の数を、後から増やすことができる配列のようなものです。まずは宣言の仕方と、基本的な使い方を見てみます。

  • C++の標準ライブラリであり、vector というヘッダーファイルを、インクルードすることで使うことができる(#include <vector> とコードの始めに書くことで使える)
  • vector の宣言は std::vector<"格納したい変数の型"> "名前";で行う (name space std; と書くことで std は省略できる)
  • std::vector<"格納したい変数の型"> "名前"(n); で要素数 n の vector を宣言できる
  • A という vector の i 番目の要素には A[i] でアクセスでき、代入もできる
  • size メソッドを使って要素数を取得できる
  • push_back メソッドを使って末尾に要素を追加できる

試しに使ってみます。

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

int main(){
	vector<int> A(3); // 要素数3の vector の宣言
	A[0] = 4; // A[0]に4を代入
	A[1] = 2; // A[1]に2を代入
	A[2] = 7; // A[2]に7を代入
	cout << "現在の要素は" << endl; // 現在の要素を出力
	for(int i=0;i < (int)A.size();i++){
		cout << A[i] << " ";
	}
	cout << endl;
	A.push_back(5); // 末尾に5を追加
	A.push_back(1); // 末尾に1を追加
	cout << "現在の要素は" << endl; // 現在の要素を出力
	for(int i=0;i < (int)A.size();i++){
		cout << A[i] << " ";
	}
	cout << endl;
}

実行結果は以下のようになります。

現在の要素は
4 2 7
現在の要素は
4 2 7 5 1

B 問題

まず ABC121 の B 問題で vector を使ってみます。
atcoder.jp
B 問題では次のことが便利です。

二次元の vector は int の vector を要素にもつ vector ということです。今回はこれを使って B 問題を解くことにしました。解答のコードは以下のものです。

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
	int N, M, C;
	cin >> N >> M >> C;
	vector<int> B(M);
	vector<vector<int>> A;

	for(int i=0;i<M;i++){
		cin >>B[i];
	}
	for(int i = 0;i<N;i++){
		vector<int> IN(M);
		for(int j=0;j<M;j++){
			cin >> IN[j];
		}
		A.push_back(IN);
	}
	int count = 0;
	for(int i=0;i<N;i++){
		int sum = 0;
		for(int j=0;j<M;j++){
			sum += A[i][j] * B[j];
		}
		sum += C;
		if(sum > 0) count++;
	} 
	cout << count << endl;
}

まず整数 N と M を、標準入力から受け取ります。その後、 B_1, B_2, ..., B_M を格納する vector を用意します。今回は要素数が M と分かっているので、サイズを指定して宣言しました。その後順番に、各B[0], B[2], ..., B[M-1] に、標準入力から受けとった値を格納していきます。問題は1 \leq i \leq Nを満たす全ての i について、 A_{i1}, A_{i2}, ..., A_{iM}を入力から受け取る部分です。今回は、次の操作を行うことで実装しました。

  1. int 型の二次元 vector A を宣言する
  2. int 型の変数 i = 0 を宣言する
  3. 要素数 N の vector IN を用意する
  4. IN[0], IN[1], ..., IN[M-1] に標準入力から受け取った値、すなわちA_{i1}, A_{i2}, ..., A_{iM}を格納する
  5. A.push_back(IN) でvector IN を A の末尾に追加する
  6. i++ を行い、i < N のときは 3 に戻る

これは、 A が vector<int> を要素に持つ vector であることを利用しています。作った vector を push_back で末尾に追加することで、正しい順序の二次元 vector を作ることができます。

C 問題

　次は C 問題についてです。
atcoder.jp

C 問題は pair を使った実装が簡単そうです。ここで vector でのソートの仕方と、要素が pair の時にソートした結果がどうなるのかをまとめてみます。

  • vector は begin と end の二つのメソッドを使って先頭と末尾のイテレータを取得できる
  • A という vector の要素を昇順ソートしたいときは、 sort(A.begin(), A.end()); で行える(algorithm というヘッダーファイルをインクルードしておく必要がある)
  • pair の要素をソートする際には、各要素は辞書に的比較される

実際に pair を要素にした vector を使ってみました。(追記：pairを使うときは utility をインクルードする必要があります)

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main(){
	vector<pair<int,int> > A(5); // 要素数5の vector の宣言
	A[0].first = 2; // A[0]の一つ目の要素に2を代入
	A[0].second = 4; // A[0]の二つ目の要素に4を代入
	A[1].first = 3; // A[1]の一つ目の要素に3を代入
	A[1].second = 1; // A[1]の二つ目の要素に1を代入
	A[2].first = 1; // A[2]の一つ目の要素に1を代入
	A[2].second = 5; // A[2]の二つ目の要素に5を代入
	A[3].first = 1; // A[3]の一つ目の要素に1を代入
	A[3].second = 2; // A[3]の二つ目の要素に2を代入
	A[4].first = 4; // A[4]の一つ目の要素に4を代入
	A[4].second = 6; // A[4]の二つ目の要素に6を代入
	cout << "現在の要素は" << endl; // 現在の要素を出力
	for(int i=0;i < (int)A.size();i++){
		cout << "(" << A[i].first << "," << A[i].second << ")" << " ";
	}
	cout << endl;
	sort(A.begin(), A.end());// Aを昇順ソートする
	cout << "現在の要素は" << endl; // 現在の要素を出力
	for(int i=0;i < (int)A.size();i++){
		cout << "(" << A[i].first << "," << A[i].second << ")" << " ";
	}
	cout << endl;
}

実行結果は以下のようになります。

現在の要素は
(2,4) (3,1) (1,5) (1,2) (4,6)
現在の要素は
(1,2) (1,5) (2,4) (3,1) (4,6)

ちゃんと辞書順に比較されていることが分かります。ここで C 問題について考えてみます。C 問題は、エナジードリンクが安い店から順番に、できるだけ多くのエナジードリンクを買うのが最適解です。そのために、エナジードリンクが安い順に、お店をソートすることを考えます。しかし、価格についてだけをソートすると、その店で買える最大本数が分からなくなってしまいます。なので、各要素が価格と最大数を表している、pair の vectorを考えます。そして一つ目の要素にその店の価格を、二つ目の要素をその店で買える最大本数を格納します。これをソートすると、お店は価格が安い順にソートされます。価格が同じ店については、最大本数が少ない方が先になります。少ない方から買っても、多い方から買っても解に影響はありません。これらを踏まえた、C 問題の解答が次のコードです。

#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using namespace std;
 
int main(){
	long int N, M;
	cin >> N >> M;
	vector<int> A(N), B(N);
	for(int i=0;i<N;i++){
		cin >> A[i] >> B[i];
	}
	vector<pair<long int,long int>> buy(N);
	for(int i=0;i<N;i++){
		buy[i].first = A[i];
		buy[i].second = B[i];
	}
	sort(buy.begin(), buy.end());
	long int sum = 0;
	for(int i = 0;i<N;i++){
		if(M <= 0) break;
		long int m = min(buy[i].second,M);
		sum += buy[i].first * m;
		M -= m;
	}
	cout << sum << endl;
}

出力する値である合計価格が、32ビット整数に収まらないことがあります。このときにlong int を使っていないと、オーバーフローしてしまうので注意が必要です。

まとめ

今回はvectorについてでした。配列と同じ様に使える部分が多くあり、更に要素を追加できるという大きな違いがあります。他にも何が違うのかは、細かく調べきることはまだできていません。また、イテレータがどういう物なのかも、まだちゃんと理解できていないです。この辺りを勉強していく必要がありそうですね。

勉強とやる気

　私は、AtCoderのコンテストに取り組んでいる間に、C++のライブラリを検索することが多いです。私が競技プログラミングを始めたのは最近です。AtCoderに登録したのが去年の12月頃で、本格的に取り組み始めたのは今年からです。なんとなくC++で競技プログラミングを始めたので、C++の勉強も同時に始めました。なのでC++については、まだ勉強不足です。最初はC++の勉強をしてから、競技プログラミングの勉強をしようか、とも考えました。「C++の基礎知識がないのに、C++を使って何かに取り組むなんて間違いだ」そう思っていたのですが、今は間違いではないと思っています。何故なら、「C++の基礎知識を学ぶ」やる気を維持するのは、とても難しいからです。今回は勉強するときのやる気について、記事を書くことにしました。

　まず、今回の記事は「エンジニアの知的生産術――効率的に学び、整理し、アウトプットする」（西尾泰和, 技術評論社, 2018年8月）を参考にしています。まだ一度読んだだけで、すべてを読み込めた訳ではありません。それでもこの本をもっと早く読みたかったと思っています。私が意識せずに出来ていたこと、出来ずにいたこと、両方に気づかされました。この本はエンジニアに向けての本です。そのためプログラミング言語などが例にあげられています。ですがこの本の話は、エンジニアリング以外の分野でも役に立つことです。知的生産についてたくさんのことを学べます。もっと細かくやる気の維持について知りたい方には特におすすめします。是非読んでみてください。
gihyo.jp
www.amazon.co.jp

この本を読んだ上で、やる気を維持するために取り組もうと思ったことが、いくつかあります。今回はその中でも大切だと思った、三つのことを紹介します。

1. 必要なことだけを、必要になったときに勉強する

　必要なこと、というのは「将来必要になりそうなこと」ではありません。「今すぐ必要なこと」です。例として、記事の初めに書いた、競技プログラミングを考えましょう。私は競技プログラミングを始めました。まだ、競技プログラミングに取り組むうえで、必要になりそうなC++の知識が足りていません。それでも私は、ある問題を解いてみようと考えました。しかし、その問題を解くには、自分の知らないライブラリを使わないと解けないことが分かりました。このときに初めて、そのライブラリについて勉強しました。先に知識を身に着けてから、問題を解き始めたのではありません。必要なことだけを、必要になったときに勉強する、というのはこういうことです。
　競技プログラミングについては、必要なことだけを、必要になったときに勉強することが出来ていました。しかし、他の物事ではできていないことに気づきました。

  • オンラインゲームで勝つために、ゲームをやる前に情報を集める
  • 英語を読めるようになるために、まず英単語だけを覚える
  • 初めて使う機械を操作するために、説明書を全部読む

例に挙げたのは、私が実際にしたことです。同じようなことをした経験がある方、いるのではないでしょうか。私が挙げた例と同じでなくても、「将来必要になりそうなこと」だから勉強した経験は、誰にでもあると思います。もちろん、必要になってからでは間に合わないこともあります。しかし、必要になってからでも間に合うことは、そのときに初めて取り組めばいいのです。
　必要なことから勉強することは、やる気の維持に繋がります。「今必要なこと」を勉強するときには、どこまで勉強すればいいのかが明らかです。人間のやる気は、ゴールが明らかなものに取り組む方が維持しやすいです。「将来必要になりそうなこと」は、どこまで勉強すれば終わるのか、まったく分かりません。そしてだんだんとやる気が失われていきます。そしてやる気の失われた勉強では、頭に情報が入ってきません。これを避けて、時間を無駄にしないためにも、今必要なことから勉強するべきなのです。
　私が以前、プログラミングを勉強しようと思ったときのことを、思い出してみました。そのときは漠然と「Ｃ言語を勉強しよう」としか考えていませんでした。だんだんとやる気が失われ、勉強するのをやめてしまいました。自分が必要になったときでないと、人間のやる気の維持は難しいのです。「必要なことだけを、必要になったときに」勉強するのが大切なのです。

2. やることを減らす

　先にも述べましたが、勉強する上で「やる気」は重要です。やる気が無いと、集中力が維持できずに効率が落ちます。そして何より、勉強を始められません。私にとっての問題は特に後者でした。卒論を書き終えて、発表を終えた後のことです。毎日何もやる気が起きず、ベッドで寝ている日が続いてしまいました。外出するのも億劫になり、生活習慣もひどいものでした。このときの私の頭の中にあったやるべきことを挙げてみます。

  • 昨年のゼミで読んだ本の復習
  • 卒論研究で行った研究の続き
  • 就活の情報を集める
  • 競技プログラミングの力をつける
  • 修論のテーマに繋がる題材を探す
  • 論文を書くのに必要な、文章を書く力を身に着ける

今こうして挙げてみても、多すぎたなと思います。先生に研究の内容は褒めていただき、これからも頑張って、学会を目指そうと言っていただけました。しかし、頑張ろうと思っても、何も手がつかずにいました。卒論発表の後、私の中で研究は、苦痛を感じるものになってしまっていました。私は先生に頼みこみ、しばらく研究から距離を置かせてもらうことにしました。研究から離れ、一度心を休ませることにしたのです。そして休んでいる内に、競技プログラミングに取り組もうと思えるようになりました。今思うと、やることが多すぎたのかなぁと思っています。
　私の例はかなり特殊だと思っています。しかし、やることが多すぎるせいで、やる気が起きないことは誰にでもあると思います。勉強しないといけないことが増えすぎたら、どうにかしてそれを減らすことは大切です。この「増えすぎた」と感じる量は、人によって差があると思います。自分にとって、やる気が維持できる量はどれくらいなのか。これを知っておくことも、また大切なことだと思います。

3. 細かく具体的な目標を決める

　以前、「量子力学について勉強しよう」と思って、専門書を買ってみました。しかし、どうにもやる気が維持できずに、勉強をやめてしまいました。これは「今必要ではなかったからやる気が出なかった」とも考えられます。しかしそれ以上に、「量子力学について勉強しよう」という目標が抽象的過ぎたことに気づきました。人間は、先が見えないとだんだんとやる気を失います。細かな目標を定めることで、先を見やすくすることができます。更に、それを達成したという満足感を得られることも、やる気の維持に繋がります。以前の私は、「今日はこの本のこのページまでは読もう」という細かな目標を、その都度定めるべきでした。
　この目標は、量でも時間でもいいです。例えば、「問題集で４ページ分の問題を解く」「30分は集中してこの論文を和訳する」といった目標がいいです。これらの目標は、細かく具体的に定められています。では「C++を完璧に理解する」という目標はどうでしょうか。これは抽象的過ぎて、なにをもって目標が達成できたとするのかが分かりません。また「本を一冊読み終える」という目標は具体的ですが、目標としては大きすぎます。この目標が大きすぎると感じるかどうかも、人によって変わるものだと思います。自分にとって、どれくらいの目標がやる気の維持につながるのか、これも知っておきたいことです。

まとめ

　勉強のやる気を維持するために、大事なことを三つ紹介しました。

  1. 必要なことだけを、必要になったとき勉強する
  2. やることを減らす
  3. 細かく具体的な目標を決める

この三つを意識することは、やる気の維持に繋がります。勉強するときには気をつけるようにしたいですね。

C++ における string の iterator と erase

　友人に「最初の投稿で既に日本語が怪しい」と言われたにわぽんです。これから頑張っていきます。今回はC++における string 型についてです。ABC120に出場している間に調べたことを、自分なりにまとめてみました。
atcoder.jp

毎回コンテストの後は、記事を投稿することにしました。出場した結果としましては、、、
f:id:niwapon-15:20190304011810p:plain
 A～Cの３問を解いて1515位でした。無事レートを上げることができました。また、前回のABC119では、A と B の２問しか解けませんでした。今回はC問題を解きたいと思っていたので、それも達成できました。コンテストの結果としては、とても満足しています。

　全問題の解法は、自分よりもっと優秀な人が書く内容だと思っています。今回は私がC問題で使った、C++における string の仕様についてまとめていきます。
atcoder.jp
解説では、0の個数と1の個数を数えて解いています。この解法が一番よさそうです。私はこの解法に気づかず、次のアルゴリズムでこの問題を解けると考えて、実装しました。

  1. 整数の変数 i を用意し、i = 0 としておく
  2. ( i + 1 ) が S の文字数を超えているなら、ステップ5 へ
  3. i 番目の文字と ( i + 1 ) 番目の文字が異なる場合、その 2 文字をSから削除し、i = 0 でないなら、i = i - 1として、ステップ 2 に戻る
  4. i 番目の文字と ( i + 1 ) 番目の文字が同じ場合、i = i + 1 としてステップ 2 へ
  5. ステップ 3 の計算で削除した文字の数を出力

文字列の先頭から見ていき、違う 2 文字の組があれば、その 2 文字を削除します。一応このアルゴリズムでも O(N) 時間で計算できている、と思っていますが自信はないです。

　このアルゴリズムを実装するのに string に実装されている erase というメソッドを使いました。この erase の使い方と、iterator についてをまとめたいと思います。
vivi.dyndns.org

こちらのサイトを参考にさせていただきました。

　まず、string に実装されている、文字列の一部を削除するメソッドを探しました。そして、 erase というメソッドがそれにあたることが分かりました。erase は iterator という型を引数にとっています。iterator とはなんなのでしょうか？

　自分なりに iterator が何なのかをまとめてみました。S を string 型の変数とします。このとき S の iterator である変数 itr は、「S の itr 番目の文字が保存してある場所」を表す変数です。C言語におけるポインタに近いものみたいですね。今回重要なのは次のことでした。

  • S.begin() で「S の 0 番目の文字が保存してある場所」にあたる iterator を取得できる
  • itr + k は 「S の (itr + k) 番目の文字が保存してある場所」にあたる iterator になる
  • *itr で「S の itr 番目の文字」を取得できる
  • S.erase(itr1, itr2)は「S の itr1 番目の文字から、( itr2 - 1 ) 番目の文字を削除する」という計算を行う

これらを踏まえて書いたコードが以下のものです。

#include <iostream>
using namespace std;
int main(){
	string S;
	cin >> S;
	string::iterator itr = S.begin();
	int cnt = 0;
	int i = 0;
	while(i + 1< S.length()){
		if(*(itr + i) != *(itr + 1 + i)){
			S.erase(itr + i, itr + 2 + i);
			cnt = cnt + 2;
			itr = S.begin();
			if(i > 0){
				i--;
			}
		}
		else{
			i++;
		}
	}
	cout << cnt << endl;
}

このコードは、コンテスト中に提出したものを少し整理したものです。提出してみるとACでした(見やすいコードを書く練習もしたいですね)。
　コンテスト中にこういった言語の仕様を調べています。これにかかる時間を減らすためにも、一度調べたことは記事にまとめることにしました。iterator については、まだよく分かっていないので、これからも勉強していきたいです。

ブログを始めてみた。

　はじめまして。にわぽんと申します。このブログは、自称「にわか情報系大学生」の私が、自分のした勉強のまとめと、数学や量子情報などに関する解説を主としたものにしたいと思っています。このブログで何をしたいのかを、この記事ではまとめました。

 

1. 文章を書く練習をしたい

　私はこの3月に学部を卒業し、大学院に入学する予定です。一か月ほど前までは学部の卒論を書いていたのですが、その際に気づきました。

自分は日本語を書くのが下手すぎる。

文章の構成がおかしかったり、一つの文が長すぎて読みにくくなっていたり、誤字が多かったりと、色々な部分で自分の能力の無さに気づかされました。改めて考えると、正しい日本語を使って、論文のような長い文章を書くという経験は、自分にはほとんど無いものでした。それこそ、高校生のときの作文レベルのものです。練習を全くしないまま、卒論という人生の中でも大きな試練に挑んだことを今では後悔しています。

自分で文章を書く練習をしないと、日本語を書く力は身につかない。

このことに気づき、ブログを使って日本語を書く練習してみることにしました。ブログは、自分以外の人の目に留まることもあり、ある程度の緊張感をもって練習することができると思ったからです。なので記事を書く上では日本語の正しさや読みやすさに注意しながら書いていこうと思っています。

 

2. 継続することで自信をつけたい

　私は、自信が全く持てない人間です。他人に自分の長所を褒められても、お世辞やからかいなのではないかと思ってしまい、逆に人の悪口はそのまま受け入れてしまいます。卒論を終えてから、この性格のせいなのか、憂鬱感が酷く、何ひとつ手につかない状態が続きました。

　自分に自信がつかないのは、努力が足りていないからだという人もいます。そこで、このブログを継続的(具体的には週に2~3回を予定しています)に更新するという目標を掲げて、努力をしてみようと思います。そしてこの目標を達成し続けることが、自信を高めることに繋がるといいと考えています。

　また、このブログでは競技プログラミング、主にAtCoderのコンテストについても扱っていきたいと思っています。AtCoderのレートを上げるための努力を継続し、勉強したことをまとめるためにも、このブログを使っていきたいと思います。

 

3. 量子情報やプログラミングの入門者の助けになりたい

　私は学部2年で情報系の学科に進みました。そして現在は、量子情報という、最近注目を集めつつある分野の勉強をしています。量子情報に関する日本語の解説の数はまだ少ないです。特に、プログラミングは少し勉強したけど、数学の知識はほとんどないという人には難しい分野になっています。そのような人たちにも、量子情報に興味を持ってもらえるような、量子情報に関する記事を書きたいと考えています。

　また、プログラミングに関する記事も書きたいと思っています。本当にプログラミングを始めたばかりの入門者や、プログラミングをこれから始めたいという人には、現在において情報が多すぎてしまい、何をしたらいいのか分からないという人がいると思います。そんな人の助けになれたらいいなと思っています。

 

 

他にも細かいものでやりたいことはあるのですが、主なものは上の三つです。精一杯頑張っていこうと思っていますので、宜しくお願い致します。