情報1st

旭丘数理科学部 第2回情報講義 おしながき • • • • C++の記法について 二次元配列 累積和 例題を解こう！ 旭丘数理科学部 情報講義担当 たきかわ @cinnamon_cute_

講義の概要 旭丘数理科学部 • C++の記法について • 前回の10進BASICでできる話をC++に互換させます • 今回からC++で全部話していきます • (身構える必要はないです) • 二次元配列 • 配列を多次元に拡張したものを考えます • 一次元配列の要素の中に一次元配列が入ってます • 平面だと思ってもらえればいいです • (この2つはあんまり面白くないです;;ごめんなさい)

講義の概要 旭丘数理科学部 • 累積和 • 前処理をするということを学びます • たくさんのクエリを処理することを目標に • imos法という汎用性の高い方法も学びます • 例題を解こう！ • 二次元配列や累積和、その混合問題を解いていきます • 知識に帰着させることの面白さを感じてください • (この2つはめっちゃおもろいです 期待して)

旭丘数理科学部 C++の記法について

C++の記法について 旭丘数理科学部 • 数値を入れる変数の書き換え • 10進ベーシック • 整数や小数などを気にする必要はない。 • 自由に書くことができる。 • C++ • “型”を変数に対して指定しなければならない • 小数のときは float 整数のときはint …と決められている • なぜ型を指定する必要があるの？ • 10進ベーシックにも、内部には”型”が存在し、推定して自動で当てはめ てくれている。 • しかし、そのような言語は実行時間がかかり、遅くなったり、プログラ マの意図していない型が当てはまったりする場合がある

C++の記法について 旭丘数理科学部 •型 • 変数の種類をきめる • Ex • • • • • • int 231 までの符号付き整数を扱える long long int 263 までの符号付き整数を扱える double 小数を扱える(大きさについては各自で調べてください) char 文字を1文字だけ扱える 例 ‘a’ string 文字列を扱える 例 “あいうえお” bool true か falseの2つの状態を保持する • 競技プログラミングで主に使うのはこのあたりです。

C++の記法について 旭丘数理科学部 • 10進ベーシックの、 • • • • • • LET DIM INPUT FOR IF PRINT • と同じような機能を持ったC++の書き方を次のスライドに 載せます

C++の記法について 旭丘数理科学部 10進ベーシック C++ LET a //変数aを立てる int a; INPUT b //bを立てる cin >> a; PRINT b //bを出力する //整数の変数aを立てる //aに入力を入れる //aは事前に立てなければいけない cout << a << endl; //aを出力する FOR i = 0 TO 9 STEP 1 “なにか” NEXT i for(int i = 0; i < n; i++){ //int i = 0; → カウンタ変数を立てる “何か” // i < n; → 条件を満たしている時ループ } //i++ → ループ時iを1増やす IF a = 10 THEN “なにか” ELSE “なにか” END IF if(a == 10){ “何か” } else{ “何か” } vector<int> a(10); a[0] = 1 DIM a(10) a(0) = 1 //等しい条件は、”==“で表す

旭丘数理科学部 実際にプログラムを書くときはおまじないが結構必要です。以下の文字 はおまじないとして、書くものだと覚えてください。 #include <bits/stdc++.h> using namespace std; int main(){ “この中にプログラムを書く” } 理由に関しては、今の時点では説明ができないので、また機会があり次 第話します。

C++のルール • 基本1行ごとに終わったら ; を書く • これが日本語で言う 。に相当します • forやifのあとは { } を書く • forやifの効果の範囲を{ } で示しています • 配列の要素は [ ] で指定 • ( ) を使う場面が多いので混同してしまう 旭丘数理科学部

旭丘数理科学部 二次元配列

二次元配列 旭丘数理科学部 • 二次元配列 • 配列を二次元に拡張したものです。 • 配列を”線”と考えると、二次元配列は、”面”です。 • 迷路や行列、グラフの問題の入力を受け取ることに使います • 動的計画法などの計算過程で用いる場合もあります • 宣言方法 • vector<vector<int>> a • vector の型をvector<int>で指定しているイメージです。 • 図形的な理解をしようとすると次のスライドのようになります。

二次元配列 旭丘数理科学部 • vector<vector<int>> a(n,vector<int>(m)); ０ • 緑の枠の場所は • a[2][4]と表せる 1 2 3 … n-1 • 0 1 2 3 4 5 6 … m-1 • 0 1 2 3 4 5 6 … m-1 • 0 1 2 3 4 5 6 … m-1 • 0 1 2 3 4 5 6 … m-1 • 0 1 2 3 4 5 6 … m-1 • 0 1 2 3 4 5 6 … m-1

二次元配列 vector<vector<int>> a(h,vector<int>); //入力 for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin >> a[i][j]; } } //出力も同じ用に 旭丘数理科学部

旭丘数理科学部 累積和

累積和 旭丘数理科学部 • 前提として、区間の表し方について学びます。 • 数直線上で、それぞれ、 • 𝑎 ≤ 𝑥 ≤ 𝑏 , 𝑎 < 𝑥 ≤ 𝑏, 𝑎 ≤ 𝑥 < 𝑏, 𝑎 < 𝑥 < 𝑏となるxの範囲を • 𝑎, 𝑏 , 𝑎, 𝑏 , 𝑎, 𝑏 , 𝑎, 𝑏 と表し、 • これらを”区間”と呼ぶ • [𝑎, 𝑏]を閉区間 • (𝑎, 𝑏)を開区間 • (使わないかも)

累積和 旭丘数理科学部 • こんな問題が与えられます！ • 𝑁日間経営してた店があります。𝑖日目の売上は𝑎𝑖 です。 • 𝑀個のクエリが与えられます • 「1日目から𝑟日目までの店の売上の合計を求めてください」 • 制約 • 1 < 𝑁 < 105 , 1 < 𝑀 < 105 • 0 ≤ 𝑎𝑖 ≤ 106 , 1 ≤ 𝑟 ≤ 105 • 入力 • 𝑁𝑀 •𝑟

累積和 • ナイーブ解法 • 𝑎𝑖 をサイズ𝑁の配列に入れる •{ • クエリを受け取り、 • [0,r)をfor文で加算する𝑂(𝑟) •} • {}内を𝑀回ループする • 計算量𝑂(𝑀𝑟) • 最大で1010 の計算回数 旭丘数理科学部

累積和 旭丘数理科学部 • 正解解法 • 𝑎𝑖 をサイズ𝑁の配列に入れる • サイズ𝑁の配列𝑆𝑢𝑚を作り、[0, 𝑖)の和を𝑆𝑢𝑚[𝑖]に入れる • 𝑆𝑢𝑚 0 = 𝑎1 𝑆𝑢𝑚 𝑖 = 𝑠𝑢𝑚 𝑖 − 1 + 𝑎 𝑖 • クエリを受け取り、𝑆𝑢𝑚[𝑟 − 1]を出力 • これを𝑀回ループ • 計算量𝑂 𝑀 • 余裕で間に合う

累積和 旭丘数理科学部 • ナイーブな解法は、 • 𝑎1 ~ 𝑎𝑟 までの和を毎回求めるため、毎回r回のループを回さなけ ればならず、無駄。 • 正解解法は、 • 𝑆𝑢𝑚としてまとめておけば、1回で済む。 • このように、予め操作を行い、あとの動作の計算量を下げること を、 “前処理” という。

累積和

旭丘数理科学部

int n,m; cin >> n >> m;
vector<int> a , sum(n);
for(int i= 0; i < n; i++){
cin >> a[i];
}
sum[0] = a[0]
for(int i = 1; i < n; i++){
sum[i] = sum[i-1] + a[i];
}

//Sum[i]に

[0,i)の和が入る

累積和 旭丘数理科学部 • ある店がT 分営業してます • 客が𝑁人来ます • ある客𝑖はある時刻ちょうど𝑐𝑖 に店に入り、𝑑𝑖 に店を出ます。 • 店主は、その日のうちに一番店の中に人がいた瞬間を知りたいで す • 同時刻の場合、退店→入店の順に行われます。 • 制約 • 1 ≤ 𝑇 ≤ 2 ∗ 105 • 1 ≤ 𝑁 ≤ 2 ∗ 105 • 1 ≤ 𝑐𝑖 ≤ 𝑑𝑖 ≤ 𝑇

累積和 旭丘数理科学部 • ナイーブな解法 • ある配列𝑆𝑢𝑚(𝑁)をたてる • 全部0で初期化する • [𝑐𝑖 , 𝑑𝑖 )に1加算する…① • 要素の最大値を求める • ①のクエリの最悪計算量は𝑂(𝑇)になるので、 • すべての計算量は𝑂 𝑁𝑇 => 4 ∗ 1010 OMG

累積和 • 良い解法 • ある配列𝑆𝑢𝑚(𝑁)を立てる • 0で初期化する • 𝑆𝑢𝑚[𝑐𝑖 ]に+1, 𝑆𝑢𝑚[𝑑𝑖 ]に-1を加算します。 • 全部やります • 最後に𝐴𝑛𝑠(𝑁)を立てて、 • 𝐴𝑛𝑠 0 = 𝑠𝑢𝑚 0 • 𝐴𝑛𝑠 𝑗 + 1 = 𝐴𝑛𝑠 𝑗 + 𝑆𝑢𝑚[𝑗 + 1]をループします • 計算量𝑂(𝑁 + 𝑇)達成！ 旭丘数理科学部

旭丘数理科学部 • 区間にすべて一定の値を足したい場合 • imos法を用いる • Ex 配列𝐴の[l,r)の要素に3を加算したい場合 • A[l]に+3 , A[r]に-3する • 前から フィボナッチ数列みたいに加算していく • 1,8 + 2 , 2,6 + 3を実現したい場合の例 0 2 3 0 0 0 -3 0 -2 0 2 5 5 5 5 2 2 0

旭丘数理科学部 例題を解こう！

例題を解こう！ • 本日のメインコンテンツです。 • 今日習ったことを用いて考えてみましょう～！ • 問題は2問です。 旭丘数理科学部

おはなやさん 旭丘数理科学部 • 縦Hマス、横Wマスの植木鉢があります。 • 各マスには花の種が植わっていて、水を1Lあげるごとに1m成長します。 • たきかわくんはこれから𝑁回水やりをしようと思います。 • 𝑖回目水やりは、花壇の左上のマスを(1,1), 右下のマスを(H,W)として、 • 左上が 𝑎𝑖 , 𝑏𝑖 , 右下が(𝑐𝑖 , 𝑑𝑖 )となる長方形上に、 各マスに1Lずつ水がかかるようにして行われ ます。 • 一番高いお花は何メートルでしょう！ • 制約 • 2 ≤ 𝐻, 𝑊 ≤ 3000 • 1 ≤ 𝑎𝑖 ≤ 𝑐𝑖 ≤ 𝐻 • 1 ≤ 𝑏𝑖 ≤ 𝑑𝑖 ≤ 𝑊

AtCoder ABC-129 D 旭丘数理科学部 縦 H 行横 W 列のグリッドが与えられます。 このグリッドのうち、いくつかのマスには障害物が存在します。 すぬけ君は、障害物のないマスのうち一つを選び、 そのマスに明かりを設置しようとしています。 設置されたマスから、上下左右の四方向にまっすぐに光線が伸びます。 それぞれの方向について、最初に障害物が存在するマスにぶつかる、 もしくはグリッドの端にぶつかる手前のマスまで照らされます。 明かりを設置したマスも照らされますが、障害物が存在するマスは照らされません。 すぬけ君は明かりによって照らされるマスの個数を最大化したいです。 H 個の長さ W の文字列 Si (1 ≤ i ≤ H) が与えられます。 Si の j 文字目 (1 ≤ j ≤ W) が ’#’のとき、グリッドの上から i 行目で左から j 列目のマスには障害物があり、 ’.’ のときは障害物がありません。 照らされるマスの個数の最大値を求めてください。 制約 •1 ≤ H ≤2,000 •1 ≤ W ≤2,000 •Si は # と . のみからなる長さ W の文字列 •Si (1 ≤ i ≤ H) のうちいずれかに . は最低 1つ存在する •https://atcoder.jp/contests/abc129/tasks/abc129_d より引用

• https://atcoder.jp/contests/abc129/tasks/abc129_d