プログラミング講座 #6 競プロのテクニック(初級)
795 Views
April 26, 23
スライド概要
部活用に作成した資料です。
「#5 競プロをやってみよう」を理解してから見ることをお勧めします
https://www.docswell.com/s/ZOI_dayo/ZVV18Q-Programming-05
競プロで使うテクニックをいくつか紹介してます
あとはコード書くのに慣れてきたら茶色くらいになれるんじゃないかと思います〜
関連スライド
各ページのテキスト
プログラミング講座 #6 競プロのテクニック(初級) @ZOI_dayo
vector 前回vectorって使ったの覚えてますか? (C++での配列みたいなやつです) あれはほぼ毎回使うので覚えておいてほしいです! ですが、vector単体だけでは解けない(or 解きにくい)問題があるのも事実です... なので、少し発展的なデータ型だったり軽いテクニックだったりを紹介します !
例題1: ABC 298 A - Job Interview 例えばこの問題を見てください
まずは翻訳 とりあえず翻訳すると、 - 長さNの文字列Sが与えられる Sのなかにxという文字があれば”No”を出力 Sのなかに(xがなく)oという文字があれば”Yes”を出力 Sのなかにxもoもなければ”No”を出力 ですね
実装 とりあえず実装してみます うーんif()の中が書きにくいですね... どうやって書きましょう...
「文字が含まれる」の判定どうやるの 一応C++には「sのなかに”x”という文字がある」 の判定として s.find("b") != std::string::npos という書き方があるのですが、特に後半が わかりにくいを極めています 使いたくないですね
1. stringをvector<char>として見る ここで、文字列を含んでいるかに限られない、めちゃくちゃ有用なテクニックを紹介します 「string ≒ vector<char>」というものです charってなんだ...? という感じだと思いますが、charは「文字」のイメージです(character=文字) stringは文字列(0~∞文字)、charは1文字、という感じです ちなみに、“a”はstringのa、’a’はcharのaです(クォーテーションの数に注目)
1. stringをvector<char>として見る stringはvector<char>みたいに使える、となると何が便利なのでしょうか? 実は、string s = “abc”; に対して、c[0] == ‘a’であり、c[2] == ‘c’となります しかも、s[0]=’d’とすると、s == “dbc” とすることができます!
2. フラグ もう一つ紹介しておきます 「フラグを立てる」という言葉を日常で使うことがあるかもしれませんが、 その「フラグ」です 例えば、ループ内で何らかの処理をして、結局条件1や2を満たしたか気になるとき、 どうすれば良いでしょうか?
2. フラグ ここで、「フラグ」と呼ばれるbool型の変数を準備します bool flag1 = false, flag2 = false; for(/*略*/) { // 条件を満たしたらflag1やflag2にtrueを代入するようにする } if(flag1 && flag2) { // 条件を満たした場合のみの処理 } こういう感じでうまくいくのがわかりますか?
再実装 これらのテクニックを使えば、 さっきの問題を右のように解くことができます (前から一文字ずつ見ていって、oやxがでたら フラグを更新しています)
練習問題 stringに対してs[0]みたいな操作をしてchar型の値を取ってきたり、 フラグを使ったりしそうな問題を紹介します ABC277 B - Playing Cards Validation → 与えられた文字列が全てトランプカードとして成立し、被りはないか、という判定です ABC282 B - Let's Get a Perfect Score → 各個人の解ける/解けないが与えられるので、全問正解できるように2人組を作ります
例題2: ABC298 B - Coloring Matrix 例えばこの問題を見てください
翻訳 つまり、 - 同じサイズの2つの2次元平面が与えられる 0と1だけでできている くるくる回して、Aで1ならばBで1、が成り立つようにする(逆は不要) ということですね 1次元の数列ならvectorでできたけれど、2次元はどう表現すれば...?
3. 多次元配列 vector<int>のように、<>のなかにはvectorの要素の型を入れるのですが、覚えてますか? これを使って、vectorのなかにvectorを入れてみます vector<vector<int>> test(N); これで、test[0][1]のように値を取り出すことができます (test[0]がvectorなので、それに対して[1]しています) vector<int>(N, 0)で、「長さNで全要素0のvector<int>」を得られるので、 これを使えば2次元配列も簡単に初期化できます vector<vector<int>> test(N, vector<int>(M, 0));
3. 多次元配列 といってもしっくりこないと思うので、使う時はvalue[x][y]みたいな感じで、 x座標/y座標をそれぞれの[]に入れているイメージでもいいと思います とりあえず、これを使えば問題に取り組めそうですね、やってみましょう
実装 まずは入力がややこしいので確認です AとBはどう受け取ればいいでしょう? これは、それぞれN*N個あることを考え、 forループを2重にして使えば良いです やってみましょう
実装 入力部分はこんな感じですね forループは、1重目と2重目でiとjと 変数を変えなければバグってしまうので 気をつけてください あとは、これを回転させて条件確認ですね... (大変)
実装 とりあえず回転です 問題にヒントがあるので使います つまり、[i][j]→[N+1-j][i]にする、ということに見えますが、一つトラップがあります 1 <= i,j <= N とある通り、プログラミングのように0始まりではないのです つまりiを(i+1)、jを(j+1)に読み替え、[i+1][j+1]→[N+1-(j+1)][i+1]にする、 すなわち [i][j]→[N-1-j][i] であることが分かります
実装
Aを回転する時、操作中に「Aの一部だけ書き換えてしまった状態」があると
おかしなことになります
つまり、これはダメだということです
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
A[N-1-j][i] = A[i][j];
}
}
(∵ i=0, j=0のループで、[0][0]を[N-1][0]に書き込む時、[N-1][0]のデータは失われてしまう!)
実装
なので、横着せず「new_Aを作って書き込み、終わってからAを上書き」でやります
vector<vector<int>> new_A(N, vector<int>(N));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
new_A[N-1-j][i] = A[i][j];
}
}
A = new_A;
実装 現状、入力受け取りとAの回転はできそうです 次は、Aが条件を満たしてるかのチェックですね これは、Aのそれぞれを見て、1であればBも1であるかを見ればいいわけです bool is_valid = true; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) { if(A[i][j] == 1 && B[i][j] != 1) is_valid = false; } これで分かりますかね...? 二重ループ内にifをおいて、フラグを更新しています
実装 あとは組み合わせるだけですね! (まあ4回まわす処理は要りますが) こんな感じでどうでしょう? (長いので分割、行数よく見てね)
練習問題 2次元配列関係の問題を並べてみます ABC295 B - Bombs → 爆発します。物騒ですね。マンハッタン距離とは「縦横しか行けない世界での距離」です stringがvectorと似てる、ってやつも使います! ABC296 B - Chessboard → さっきのやつよりは簡単かな? チェス盤での位置の名前を出力します これもstringに対して[]のやつ使うと思います(というかほとんどの問題で使う気もする)
例題3: ABC 294 B - ASCII Art 次はこの問題です
翻訳 つまり、vector<vector<int>>みたいな2次元配列を渡すから、それを 0→「.」、1→A、2→B、...、26→Zと置き換え、1行ごとに出して、ということ そりゃ、if文を27個書いたらできるけど...嫌だしどこかで間違えそう
4. charは数字 実は、stringの時に出てきたcharって、中身が数字なんです! なんで1文字だけなの?と思ったかもしれませんが、 charは文字ですが、「0~127の数字を入れられる型」という面も持っています ちなみに、どの数字が入っていればどの文字を表すのか、というのは ASCIIとして決められてるので調べてもいいかも?
4. charは数字 つまり何が言いたいかというと、charは数字として計算に使える、ということです しかも、ASCIIコード表を見てもらえば分かりますが、a~z、A~Z、0~9といったものは 常識的な順序で並んでいます! つまり、’a’+3 == ‘d’となるわけです! (地味に面白い) ただし、’a’ + 3 は(‘a’==97なので)100と捉えられるかもしれません coutに入れた時「数字じゃなくて、100をcharとして見て! ‘d’だよ!」としなければなりません
4. charは数字 こんな時に使えるのが、キャストというものです こんなふうに使います cout << (char) 100 << endl; cout << (char) (‘a’ + 3) << endl; このように、値の前に「(型)」と書くことで、型を強制的に決めることができます (もちろん、無茶な変換をするとエラーになります、int→charくらいにしましょう)
実装 これでもう行けそうですね この例では1文字ずつ出力しています (改行時のみendlです) もちろんresultかなにか変数を作って入れて、 最後にまとめて出力でもOKです
練習問題 charを数字として使って遊ぶ問題を並べてます ABC282 A - Generalized ABC → AからK文字目までのアルファベット列挙です ABC291 A - camel Case → 大文字か小文字かを不等式で判断できます! 面白いですね〜
例題4: ABC 295 C - Socks 次はこの問題です
翻訳 つまり、 - 靴下を、色ごとに何個ずつあるか覚えておく それぞれに対して÷2(切り捨て)してその総和を求める 例えば赤が3足、青が6足あれば、1+3=4セット作れる、というわけです
実装 しかし、よく制約を見てみると、 色(つまりAi)は10^9種類あります これでは、v[c]に色がcの個数を入れるとしても、 長さ10^9の配列を作らないといけないので、時間に間に合いません (1秒で10^8回くらいしか計算できないので、100秒くらいかかってしまいます...)
5. STLコンテナ こんな時には、情報をvector以外で保存する、ということを考えてみてください いろいろありますが、今回の用途にはmap<K, V>というものが使えます (map=連想配列です、#2で紹介してるので見てみてください) 例えば、map<int, int> socks_count;、とすると、socks_count[0] += 1;と普通のvectorみたいに使えま す 必要に応じて生成されるvectorみたいなものです
5. STLコンテナ ただ、このままでは「mapの内容のうち中身があるもののキー」を取得できません このままではやっぱり10^9回いちいち試さないといけないので、時間に間に合いません ここで、拡張forというテクニックを利用します
6. 拡張for文
普通forはこう書きますが、
for(int i=0; i < N; i++) {
// 何かする
}
vectorやmapなどがあるとき、forはこんな使い方もできます
map<string, int> m; // 値は入れとく
for(auto e : m) {
// 何かする
}
6. 拡張for文
for(auto e : m) {
// 何かする
}
これをすると、mの値が一つ一つeという変数に入りながらループされます
ただし、mapをループする時にはちょっと注意があります
stringがvector<char>であるように、mapはvector<pair<K, V>>みたいな感じなんです
pairとは...?
6. 拡張for文 pair<K, V>とは、2つの値をまとめて管理できるかたまりです 長さが2で固定されてる配列、というイメージでもそこまで外れてはないはずです pair<int, string> p;があった時、p.firstでint型の値、p.secondでstring型の値が貰えます
6. 拡張for文
つまり、
map<string, int> m;
for(auto e : m) {
}
の時、{}の中ではpair<string, int>が使えるということです
これを踏まえて書いてみましょう
実装 では実装です、こんな感じですね
5. STLコンテナ このような、vector、string、map、pairといったものをSTLコンテナと言います (Standard Template Libraryの略ですが、まあ最初から入ってるやつら、ということです) 他にも有名なものがいくつもあり、必要になってから覚えてもらえばいいのですが、 とりあえずここではsetだけ紹介しておきます
5. STLコンテナ setはほぼほぼvectorだと思ってもらえれば良いです ただし、以下の違いがあります - 要素の追加/削除/含まれてるかの確認が爆速 「N番目」をみることができない 被った値は省略される つまり、「これまでに一度でも登場したか」をみるのに最適です ちなみに、set内は常に小→大にソートされた状態になっています(拡張forで確認できる) これが素早く追加/検索できる秘訣ですね
5. STLコンテナ 使い方はこんな感じです set<int> s; for(int i = 0; i < N; i++) { int a; cin >> a; s.insert(a); } bool is_exist = (s.count(5) == 1); if(is_exist) cout << “5は存在します” << endl; else cout << “5は存在しません” << endl;
5. STLコンテナ
s.count(x)は、sの中のxの個数、すなわち0か1を返します
ちょっと省略するとこんな感じですね(1 == true, 0 == false)
set<int> s;
for(int i = 0; i < N; i++) {
int a;
cin >> a;
s.insert(a);
}
if(a.count(5)) cout << “5は存在します” << endl;
else cout << “5は存在しません” << endl;
5. STLコンテナ あと、おまけとしてvectorのソート方法を紹介します vector<int> v(N);について、 sort(v.begin(), v.end()); でvがソート済みのものに書き換えられます そんなに早くないので、ループの中で実行したりはしないでください ... (今はあんまり使わないかもだけど、後で死ぬほど使うことになるはず )
練習問題 mapとかsetとかを使う問題のつもりです〜 ABC296 C - Gap Existence → setの検索が爆速なのを利用します ABC294 D - Bank → setをうまく使って時間短縮しましょう! 難しめです (使わなくてもできるらしい) ABC298 C - Cards Query Problem → これは難しいです! mapやsetを上手く使えば解けるかも? (使わなくてもできるらしいけど)
まとめ 今回めちゃくちゃ長くなってしまいました... いつもより教科書感がすごいですね、まあここで書いたことを知っておけば A~Bくらいは安定して解けるんじゃないかな? と思うので、ぜひ過去問を解いてみてください これを身につけたら、うーん、茶色は狙えるんじゃないかな? 多分... という感じです! 頑張ってください〜
終わり