2018-12-22

1秒差で負けた [CADDi 2018 for beginners]

f:id:tako0608:20181222214430p:plain

久しぶりに全完できました
結構早く解けました(500の実装がクソ軽かった)
1秒差で3位=>4位になったので賞金が1万円=>5000円になりました
1ペナで20:56で5分間（頼む誰も全完するな...）と思っていましたが4:59経った時全完されました（悲しい）

C問題

かけてPになるN個の数 $a_1, a_2, \cdots , a_N$ がある時、それらすべてのgcdの最小値を求める問題です。
Pを素因数分解したとき、同じ素因数を $a_0$ から $a_N$ まで均等に分けるのが良いので、図のようにします（一般化して書く能力がないのでsample 4で）
素因数分解のスニペットを持っていたので10分で実装できました

f:id:tako0608:20181222221913p:plain

考察中は $N=3, P=2^{6}\cdot 3^{3}$ でやっていて、 $2^{2}$ と $2\cdot 2$ が同じなために上の $2^{4/6}$ のところを $2\cdot 4/6$ として1WAを出しました

int main(){
    lint n,p;cin>>n>>p;
 
    lint plf=p,pp;
    map<lint,lint>ma;
    for(lint i=2;i*i<=p;++i){
        if(!(plf%i)){
            pp=1;plf/=i;
            while(plf%i==0){
                ++pp;plf/=i;
            }
            //ここで、因数i^ppがわかる i is prime
            ma[i]=pp;//処理
 
        }
    }
    if(plf!=1){
        //ここで、因数plf^1がわかる plf is prime
        ma[plf]=1;
    }
    lint ans=1;
    for(auto i:ma){
        if(i.second>=n)ans*=pow(i.first,i.second/n);
    }cout<<ans;
}

D問題

一本のりんごの木があり、N色のりんごが実っています。これらのりんごの N種類の色には 1から Nまでの番号が振られており、i番の色のりんごは $a_i$ 個あります。あなたとダックスフンドのルンルンは、以下の行動を交互に行います (あなたから始めます)。木から1個以上のりんごを選んで食べる。ただし、一度に選ぶりんごは全て異なる色でなければならない。木から最後のりんごを食べた者を勝者とします。あなたとルンルンがともに最善を尽くすとき、どちらが勝つでしょうか？

という問題です。同じ色を列に並べて考えると、

サンプルを見て考えると「相手のターンにわたるときにすべての列にあるりんごの個数が偶数になっていれば勝ち」だとわかります。
なので始めのターンに「奇数の列からすべて取る」ができればfirstの勝ちです。
それができないのはすべての列が最初から偶数になっているときなので、すべての列が偶数個になっているかわかればいいです。
証明はしていないw

int main(){
    lint n;cin>>n;
    vector<lint> a(n);
    bool first=0;
    rep(i,n){
        cin>>a[i];
        if(a[i]&1)first=1;
    }cout<<(first?"first":"second");
}

2018-12-09

第18回日本情報オリンピック予選に参加しました

結果

100-100-100-100-100-6で合計506点を取りました。去年の予選通過のボーダーが340だったらしいので、多分本選行けると思います

感想

競プロを初めてもうすぐ半年というところで、これだけの点数を取ることができてうれしいです
全体的に、過去問よりかなり簡単に感じました。
体感難易度はJOI難易度で2-2-2-6-5-?というところ（解けない問題の難易度は分からないので）
不得意なグラフが出なかったおかげでここまで取れた気がします
解いた順番は、A(10分)->B(7分)->C(7分)->E部分点(70点)(17分)->D(1時間10分)->F部分点(6点)(14分)->E(20分) です
Dの発想が難しい
以下、可読性0のクソコードを貼ります

A問題

1日ごとにaコイン、7日ごとにbコインもらえるとき、何日目にcコイン以上になるかという問題です
最初は割り算をして出そうと思いましたが、頭が悪いので2WAしてキレてループまわしました（）

int main(){
    lint a,b,c;cin>>a>>b>>c;
    lint cur=0,ans=0;
    while(cur<c){
        ++ans;
        cur+=a;
        if(ans%7==0)cur+=b;
    }cout<<ans;
}

B問題

JOI 君はすごろくを持っている．このすごろくは 2019 個のマスが横一列に並んだ形をしている．これらのマスには，左端のスタートマスから右端のゴールマスへと順に 1 から 2019 までの番号がついている．

現在このすごろくの上には，N 個の駒が置かれている．これらの駒には，スタートに近い順に 1 から N までの番号がついている．駒 i (1≦i≦N) は，マス Xi に置かれている．すべての駒は異なるマスに置かれている．

JOI 君はこれから M 回の操作を行う．j 回目 (1≦j≦M) の操作では，駒 Aj を 1 マス先へ進める．ただし，移動元のマスがゴールマスであった場合，もしくは移動先のマスに別の駒が置かれている場合，駒 Aj は進まず，位置は変わらない．

すべての操作が終了した時点で，各駒が置かれているマスを求めよ．

という問題です。

int main(){
    lint n;cin>>n;
    bool ma[10000]={};
    vector<lint> x(n);
    rep(i,n){
        cin>>x[i];--x[i];
        ma[x[i]]=1;
    }
    lint m;cin>>m;
    vector<lint> a(m);
    rep(i,m){
        cin>>a[i];--a[i];
        if(ma[x[a[i]]+1]||x[a[i]]==2018)continue;
        ma[x[a[i]]]=0;
        ++x[a[i]];
        ma[x[a[i]]]=1;
    }for(auto i:x)cout<<i+1<<endl;
}

C問題

JOI 君はマルスタンプ，バツスタンプ，マルバツスタンプの3種類のスタンプをそれぞれ 0 個以上持っている．これらはマルやバツのマークを紙に印字することができるスタンプである．

マルスタンプを使うとマルが 1 つ印字され，バツスタンプを使うとバツが 1 つ印字される．マルバツスタンプを使うとマルとバツが横一列に 1 つずつ印字され，スタンプの向きを変えることで，マルの右にバツが来るようにも，バツの右にマルが来るようにも印字できる．

JOI 君は，持っているスタンプをそれぞれちょうど 1 回ずつ適当な順番で使い，紙に横一列にマルとバツを印字した．印字されたマルとバツの列は文字列 S で表される．S は O と X から構成された長さ N の文字列であり，Si= O ならば JOI 君が印字したマークのうち左から i 番目のものがマルであることを表し，Si= X ならばそれがバツであることを表す (1≦i≦N)．

あなたは，JOI 君が持っているスタンプの個数は分からないが，JOI 君が印字したマルとバツの列は知っている．印字されたマルとバツの列から，JOI 君が持っているマルバツスタンプの個数としてあり得るもののうち最大値を求めよ．

という問題です。

次の文字と違うかどうかだけを見たので、'O'とか'X'とかと比較しなくてもかけました

int main(){
    lint n;cin>>n; string s;cin>>s;
    lint ans=0,i=0;
    while(i<n-1){
        if(s[i]!=s[i+1]){
            ++ans;
            i+=2;
        } else ++i;
    }cout<<ans;
}

D問題

日本列島は細長い列島である．日本列島は平行な境界線により N 個の区画に分けられている．区画には端から順に 1 から N の番号が付けられている．区画 i (1≦i≦N) の高さは Ai である．

日本列島は海に囲まれており，海面の高さは場所によらず一定である．高さが海面の高さより高い区画を陸地と呼ぶ．

陸地が連続している部分のことを島と呼ぶ．より正確に書くと以下の通りである．整数 l, r (1≦l≦r≦N) について，日本列島のうち区画 l，区画 l+1，…，区画 r からなる部分を領域 [l,r] という．以下の条件を満たす領域 [l,r] を島という：

区画 l，区画 l+1，…，区画 r はすべて陸地である．

l>1 ならば区画 l−1 は陸地ではない．

r<N ならば区画 r+1 は陸地ではない．

海面の上昇により，日本列島は少しずつ沈没している．現在の海面の高さは 0 であるが，これは時間が経つにつれて徐々に上がり，ついには日本全体が海になってしまう．

JOI 君は，海面の高さが上昇すると，日本の島の数が増減することに気付いた．現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を求めたい．

という問題です。

発想が難しかったです。
座標圧縮とかわかりません
海面を上げて行って、区画が沈むときだけ見て、もし沈む区画の右と左が両方沈んでいたなら--(島の数)、両方沈んでいないなら++(島の数)
をしました
10WAだしました

int dead[100010]={1};
int main(){
    setc;
 
    lint n;cin>>n;dead[n+1]=1;
    vector<P> a(n);
    bool least=0;
    rep(i,n){
        cin>>a[i].first;
        if(a[i].first)least=1;
        a[i].second=i+1;
    }
 
    sort(all(a));
    lint ans=least,cur=1;
 
    
    rep(i,n){
        dead[a[i].second]=1;
        if(!dead[a[i].second-1]&&!dead[a[i].second+1])++cur;
        else if(dead[a[i].second-1]&&dead[a[i].second+1])--cur;
        if(i==n-1||a[i].first-a[i+1].first)ans=max(ans,cur);
    }cout<<ans;
}

E問題

JOI 氏は，自宅の敷地に N 本の木を所有している．これらの木は一列に並んでおり，順に 1 から N までの整数で番号が付けられている．

この冬，JOI 氏はいくつかの木を選んで，イルミネーションを飾り付けることにした．イルミネーションには美しさと呼ばれる値が定まっている．木 i にイルミネーションを飾り付ける場合の美しさは Ai である．

JOI 氏は，あまりに近い 2 つの木の両方にイルミネーションを飾り付けてしまうと，眩しすぎる場合があることに気がついた．具体的には，j=1,2,…,M に対して，木 Lj, Lj+1, …, Rj のうち 2 つ以上にイルミネーションを飾り付けるべきではないということが判明した．

この条件に従ってイルミネーションを飾り付けるときの，美しさの合計の最大値を求めよ．

という問題です。

Dよりは簡単だと思います...
全てのiについて、木iを選ぶとき、その木より左にあり選べる木のうち、一番右にあるものがどこにあるか　という情報が必要です
その前処理をO(NM)で求め、単純なDPをする(70点)までは簡単にわかります。Dに時間を使う前に70点を取っておいたのはいい判断でした
前処理をO(N)に高速化するところが少し難しいです。
自分はpairでl,rを受け取り、lについてソートして、左から決めていったらO(N)になりました

lint dp[200020]={};
int main(){
    lint n,m;cin>>n>>m;
    vector<lint> a(n);rep(i,n)cin>>a[i];
    vector<P> sec(m);
    vector<lint> leftest(n);rep(i,n)leftest[i]=i;
    rep(i,m){
        cin>>sec[i].first>>sec[i].second;--sec[i].first;
    }vsort(sec);lint last=0,pos=0;
    rep(i,m){//前処理
        last=max(last,sec[i].second);
        for(pos=max(pos,sec[i].first);pos<last;++pos)leftest[pos]=sec[i].first;
    }
    rep(i,n){//dp
        dp[i+1]=max(dp[i],dp[leftest[i]]+a[i]);
    }cout<<dp[n];
}

始めに出した70点解法:

lint dp[200020]={};
int main(){
    lint n,m;cin>>n>>m;
    vector<lint> a(n);rep(i,n)cin>>a[i];
    vector<P> sec(m);
    vector<lint> leftest(n);rep(i,n)leftest[i]=i;
    rep(i,m){
        cin>>sec[i].first>>sec[i].second;--sec[i].first;
        repi(j,sec[i].first,sec[i].second){//前処理(70点)
            leftest[j]=min(leftest[j],sec[i].first);
        }
    }sort(all(sec));lint last=0,pos=0;
    rep(i,n){//dp
        dp[i+1]=max(dp[i],dp[leftest[i]]+a[i]);
    }cout<<dp[n];
}

F問題

2XXX 年，世界の国は直線状に並んでいた．N 個の国があり，1,2,…,N の番号が付けられている．i=1,2,…,N−1 に対し，国 i と国 i+1 が互いに隣国である．

この年の国際情報オリンピックでは，国 i からは Ai 人の選手が参加する．国際情報オリンピックの技術委員のあなたは，競技での座席表を作成する担当である．競技会場が細長いため，一列に並んだ A1+A2+…+AN 個の座席に選手たちを割り当てることになった．不正防止のため，同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない．

選手たちを座席に割り当てる方法は何通りあるだろうか．この数は非常に大きくなる可能性があるので，それを 10007 で割った余りを求めたい．

という問題です。

全探索O(N!)で6点を取りました
2つ以上離れている人同士を辺でつなげば巡回セールスマン問題になって20点解法ができそう...?と思いましたが、20点解法の制約だと（頂点が30個あるので）bitdpできなさそう（？）でしたし、まずbitdpができないので無理でした

6点解法:

int main(){
    lint n;cin>>n;
    if(n>5)return 0;
    vector<lint> a(n),p;
    rep(i,n){
        cin>>a[i];
        rep(j,a[i])p.push_back((i<<1)+j);
    }lint ans=0;
    bool ok;lint l=siz(p);
    do{
        ok=1;
        rep(i,l-1){
            if(abs((p[i]>>1)-(p[i+1]>>1))<2){ ok=0; break;}
        }
        ans+=ok;
    } while(next_permutation(all(p)));
    cout<<ans;
}

最後に

これから勉強などで時間が無くなると思いますが、せっかく本戦に行ける（かもしれない）ので競プロのための時間も作りたいと思います

2018-09-09

ABC109 A B C D問題

ABC AtCoder 競プロ

A問題
- 解法
B問題
- 解法
C問題
- 解法
D問題
- 解法

11回目のratedコンテストで3回目の全完をしました。
次回はAGCなので不安です。

A問題

A - ABC333
$A, B$ が与えられるので、 $A\cdot B\cdot C$ が奇数となるような $C$ が存在するか判定する問題です。

解法

$A\cdot B$ が偶数の場合、 $C$ が何であっても $A\cdot B\cdot C$ は偶数となり、
$A\cdot B$ が奇数の場合、 $C$ が奇数の時 $A\cdot B\cdot C$ は奇数となるので、 $A\cdot B$ の偶奇を判定すればよいです。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int a,b;cin>>a>>b;
    cout<<(a*b%2?"Yes":"No");
}

B問題

B - Shiritori
与えられた文字列の列がしりとりになっているか判定する問題です。

解法

やるだけです。せっかくなので少し前に([ABC105] 解法、unordered_mapの使いどころ - tqkoh's diary)使ったunordered_mapを使った実装にしてみました。
下のサンプルコードでは、使われた文字列をkeyとして、何回つかわれたかをvalueとしています。足した後に2になる、または、しりとりになっていない場合"No"を出力し、最後まで行ったら"Yes"を出力しています。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int n;cin>>n;
    unordered_map<string, int> ma;
    vector<string> s(110);cin>>s[0];++ma[s[0]];
    for (int i=1;i<n;++i){
        cin>>s[i]; ++ma[s[i]];
        if(ma[s[i]]==2 || s[i][0]!=s[i-1][s[i-1].size()-1]){cout<<"No";return 0;}
    }
    cout<<"Yes";
}

C問題

C - Skip

数直線上に $N$ 個の都市があり、 $i$ 番目の都市は座標 $x_i$ にあります。
あなたの目的は、これら全ての都市を $1$ 度以上訪れることです。
あなたは、はじめに正整数 $D$ を設定します。
その後、あなたは座標 $X$ から出発し、以下の移動 $1$ 、移動 $2$ を好きなだけ行います。
- 移動 $1:$ 座標 $y$ から座標 $y+D$ に移動する
- 移動 $2:$ 座標 $y$ から座標 $y-D$ に移動する
全ての都市を $1$ 度以上訪れることのできる $D$ の最大値を求めてください。という問題です。

解法

まず $X$ から始めるという変な設定なのですべての $i$ について $x_i$ から $X$ を引きます。
すると、何個か例を見るとすべての都市の座標に行くにはその公約数の時に行けることがわかります。(6, 8, 10)など？
なので最大公約数を求めます。

#include "bits/stdc++.h"
using namespace std;
int gcd(int a, int b) {
    if (!b)return a;
    return gcd(b, a%b);
}
int main(){
    int n,X,x,ans;cin>>n>>X;
    cin>>x;ans=abs(x-X);
    for (int i=1;i<n;++i){
        cin>>x;ans=gcd(abs(x-X),ans);
    }cout<<ans;
}

D問題

縦H行横W列に区切られたマス目があり、上から i番目、左から j列目のマスをマス(i, j)と呼びます。マス(i, j)には $a_{ij}$ 枚のコインが置かれています。あなたは以下の操作を何度でも行うことができます。操作: まだ選んだことのないマスのうち1枚以上のコインが置かれているマスを1 つ選び、そのマスに置かれているコインのうち1枚を上下左右に隣接するいずれかのマスに移動する
偶数枚のコインが置かれたマスの数を最大化してください。

出力: 偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力せよ。

$N$
$y_1$ $x_1$ $y_1\prime$ $x_1\prime$
$y_2$ $x_2$ $y_2\prime$ $x_2\prime$
$\cdots$
$y_N$ $x_N$ $y_N\prime$ $x_N\prime$

という問題です。最小の手数とは言ってない

解法

これはやり方さえわかれば後は実装するだけです。
まず、操作のすべてのパターンを見てみると、

操作するマス	操作後のマス	考察
A.奇数マスから奇数マス	偶数マス、偶数マス	奇数マス2個が消えた！
B.奇数マスから偶数マス	偶数マス、奇数マス	奇数マスを（1貰うほうのマス）に移動できた。
C.偶数マスから奇数マス	奇数マス、偶数マス	奇数マスを(1あげるほうのマス)に移動した。
D.偶数マスから偶数マス	奇数マス、奇数マス	ゴミ

奇数か偶数か、だけで後の状態が決まるので、重要なのは奇数か偶数かだけだとわかります。

また、いま奇数をなるべく消して偶数だけにしたいので、何らかの移動をして奇数マスから奇数マスに1を運んでいけばいいとわかります。
なので、この問題は「奇数と奇数をつなぐ道を出力する」という問題と言い換えられます。
ここから先の図では、マスの値をmod 2で表します。つまり奇数が1という事です。
つなげ方はいくつかあります。自分は本番中には「じゃばら状に見て行って、奇数が来たら、矢印を置くかおかないかのフラグを反転させ、フラグがたっているときのみ矢印を出力する」（以下図）

をしましたが、twitterで「右下に寄せる」という天才的発想を見たので、そちらを紹介します。

どういうことかというと、

f:id:tako0608:20180909113518p:plain

はじめ見たときは「こっちのほうが実装難しそう（どこまで1を運んでいるかを覚えておくなどがどうやればいいかわからない）」と思いましたが、なんとこのやり方、「1マスずつ見て行って、奇数が来たら右に移動する（端っこでは下）」だけでできるんです。
なぜかはこの図か上の表を少し見ればわかると思いますが、奇数を奇数に移動(A.の操作)したら消えるので、1をどこまで運んで置いたかなど覚えておく必要がないんです。
この解法を見て気づきましたが、自分のじゃばら状の解法（？）も、奇数が来たら次のマスに移動するだけでよかったようです。
どっちにしろじゃばら状に移動させるのは少し難しかったので、右下に寄せる解法のサンプルコードを載せておきます。

#include "bits/stdc++.h"
using namespace std;
char ans[250010][256]={""};
int main(){
    int h,w,in;cin>>h>>w;
    bool mp[550][550];int ansc=-1;
    //奇数を1として入力します。
    for (int j=0;j<h;++j)for (int i=0;i<w;++i)cin>>in,mp[j][i]=in%2;
    for (int j=0;j<h;++j){
        for (int i=0; i<w-1; ++i)
            if (mp[j][i]){
                //そのマスが奇数の時のみ、右向きに移動A.またはB.をします。
                mp[j][i]=0; mp[j][i+1]=!mp[j][i+1];
                //答えを保存しておき、数を数えます。
                sprintf(ans[++ansc],"%d %d %d %d\n",j+1,i+1,j+1,i+2);
            }
        if(j!=h-1&&mp[j][w-1]){
            //一番右かつ右下以外の時は、下向きに移動A.またはB.をします。
            mp[j][w-1]=0; mp[j+1][w-1]=!mp[j+1][w-1];
            sprintf(ans[++ansc],"%d %d %d %d\n",j+1,w,j+2,w);
        }
    }
    cout<<ansc+1<<endl;
    for (int i=0;i<=ansc;++i)cout<<ans[i];
}

2018-08-26

ABC107 A B C問題 - tqkoh's diary

ABC AtCoder 競プロ

A問題
- 解法
B問題
- 解法
C問題
- 解法
学んだことメモ

これはアウトプットして自分の記憶を定着させ実力を高めるための記事です。公式の解説はここにあります。

https://img.atcoder.jp/arc101/editorial.pdf

A問題

A - Train

$N$ 両編成の列車の前から $i$ 両目は後ろから何両目か、という問題です。

解法

前から $N$ 両目の列車は後ろから $1$ 番目ですので、答えは $N-i+1$ です。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int n,i;cin>>n>>i;
    cout<<n-i+1;
}

B問題

B - Grid Compression

各マスが'.'か'#'の $H*W$ のグリッドが与えられるので、一行全ての文字が'.'の行と一列全ての文字が'.'の列を削除したグリッドを求める問題です。例えば、

##.#
....
##.#
.#.#

を

###
###
.##

に変換します。

解法

解法はやるだけなのですが実装が難しいです。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int h, w; cin>>h>>w;
    vector<string> m(110);
    bool erasex[110]={}, erasey[110]={};
    for (int i=0; i<h; ++i){
        cin>>m[i];
        if (m[i].find('#')==string::npos)erasey[i]=1;
        //行iに'#'が一つもなければ、消す行にします。
    }
    bool tmp;
    for (int j=0; j<w; ++j){
        tmp=1;
        for (int i = 0; i<h; ++i)if (m[i][j]=='#')goto L_erase;
        erasex[j]=1;//列jに'#'が一つもなければ、消す列にします。
    L_erase:;
    }

    for (int i=0; i<h; ++i)if (!erasey[i]){
        for (int j=0; j<w; ++j){
            if (!erasex[j])cout<<m[i][j];
        }
        cout<<endl;
    }
}

自分は、こういう多重ループを抜けるgotoはわかりやすいので使っていいと思っています。

C問題

https://beta.atcoder.jp/contests/abc107/tasks/abc107_c

数直線上の0にいるとき、それ上にあるろうそく $n$ 本のうち $k$ 本に火をつけるのに歩く最短距離を求める問題です。
解法
ある2本に火をつけるとすると、その間にあるろうそくはすべてつけられるので、つけるろうそくは連続している $k$ このろうそくであるべきです。その中で最短のものを求めればいいわけです。
一つの区間の中のろうそくをすべてつけるのの最短距離は、右から行くか、左から行くかのどちらかです。
$(右から行くのと左から行くのの短いほう)$
$=(右端から左端の距離) + (右端と左端のうち0に近いほうから0までの距離)$ とすると単純に解けます。
よって、答えは
$0 \le i$ < $n-k+1$ の範囲で $a_{i+k-1}-a_i+min(|a_i|,|a_{i+k-1}|)$ の最小値です。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int n, k; cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;++i)cin>>a[i];

    int ans=INT_MAX,t;
    for(int i=0;i<n-k+1;++i){
        t=min(a[i+k-1]-a[i]+abs(a[i+k-1]), a[i+k-1]-a[i]+abs(a[i]));
        if(ans>t)ans=t;
    }
    cout<<ans;
}

学んだことメモ

文字列の中の文字列の検索方法。

string s = "abc107";
s.find('a');//0
s.find("c1");//2
if (s.find('#')==string::npos);//sに#が含まれないならば

他にもこんな記事を書いています tqk.hatenablog.jp

tqk.hatenablog.jp

qiita.com

2018-08-19

ABC106 D問題 [part2] - tqkoh's diary

ABC AtCoder 競プロ

tqk.hatenablog.jp

の続きです

D問題
- 解法
  - 解法1
  - 解法2

D問題

D - AtCoder Express 2

横1列に並ぶN個の町を結ぶM(<=100,000)本の路線のうち、「LからRに完全に含まれる路線の数を求める」というクエリにQ問答えるという問題です。

解法

解法が2つありますが、どちらも、「路線の区間(l, r), 質問の範囲(L,R)を二次元座標で考える」という発想が必要です。
どういうことかというと、このような問題があったら(atcoderのサンプル2です)(路線の区間を(l, r)、質問の範囲を(L, R)とおく)

$N=10, M=3, Q=2$
$l_1=1, r_1=5$
$l_2=2, r_2=8$
$l_3=7, r_3=10$
$L_1=1, R_1=7$
$L_2=3, R_2=10$

f:id:tako0608:20180819154912p:plain

これから、

f:id:tako0608:20180819152627p:plain

こうするという事です。2番目のクエリについてみてみると、

f:id:tako0608:20180819153227p:plain

このようになり、問題は「この表でたてよこそれぞれL-1からRまでに含まれる路線の数を数える問題にQ個答える」と言い換えられます。
(上の例だと答えは 1 1)

数える方法を2つ紹介します。
実際に数えるのを実装するよりも、ここまで説明した問題の言いかえの部分の方が114514倍難しい気がします...

解法1

累積和(そこまでに何個あるか)を使い、数える部分を分割して足します。簡単です。
横の行ごとに累積和をとった図で言えば、(オレンジ $-$ 黄色)が答えになります。累積和を求めるのに $O(N^2)$ 、各クエリについて $O(N)$ で解けるので、この解法は $O(N^2+QN)$ です。

#include "bits/stdc++.h"
using namespace std;
int s[510][510];
int main(){
    int n,m,q;cin>>n>>m>>q;
    int l,r;
    for (int i=0; i<m; ++i){
        cin>>l>>r;
        for (int j=r; j<=500; ++j)++s[l][j];//累積和は後にふつうに求めたほうがいいかもしれないです。今回はどちらでも余裕
    }
    int ans;
    for (int i=0; i<q; ++i){
        cin>>l>>r;
        ans=0;
        for (int j=l; j<=r; ++j)
            ans+=s[j][r]-s[j][l-1];
        cout<<ans<<endl;
    }
}

解法2

二次元累積和を使います。二次元累積和の説明を先にします。
普通の累積和
$a_i$ に対して累積和 $S_i$ は、0からiまでにあるaの和を表します。
これをすると何がいいかというと、pからqまでにあるaの和を、 $S_q-S_{p-1}$ で $O(1)$ で求めることができることです。
$S_i$ の求め方は、 $i=1$ から見て行って、s[i]=s[i-1]+a[i-1]と計算していけば求まります。
これを使ったのが解法1です。
二次元累積和
同様に、 $a_{i,j}$ に対して累積和 $S_{i,j}$ は、0からi, jまでにあるaの和を表します。i, jまでとは、 $i=5,j=9$ のときこういうことです。
この表をよく見ればわかりますが、しっかり(i, j)までの値の和になっています。
普通の累積和と同じように、求め方と、使い方を知りたいのですが、その前にこれを見てください。 ...①
これを変形すると ...②
$S_{i,j}$ を求めるには、②を使います。赤い部分が $a_{i,j}$ の1マスだと考えます。
求め方： ②より、 $S_{i,j}=a_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}$ ですから、 i, jを1から見て行って、 s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1] を計算して行けば出来上がりです。
これをすると何がいいかというと、範囲内の $a_{i,j}$ の和を $O(1)$ で求められます。
範囲内の $a_{i,j}$ の和を求めるには、①を使います。赤い部分が求めたい範囲だと考えます。
求め方： ①より、求めたい範囲を(pl,ql)から(pr,qr)とすると、 $(範囲内のaの要素の和)=S_{pr,qr}-S_{pl-1,qr}-S_{pr,ql-1}+S_{pl-1,ql-1}$ ですから、s[pr][qr]-s[pr][ql-1]-s[pl-1][qr]+s[pl-1][ql-1]が答えです。
▽下の表で、みどりで囲った範囲の中にある $a$ の要素の和は, $3 - 1 - 1 + 1 = 2$ で、合っています。

D問題に二次元累積和を使ってみる

これを知っていれば、数える部分はやるだけになるのかもしれません。
数えるのが $O(1)$ ですので、全体で $O(N^2+Q)$ です
この問題では二次元累積和である必要がありませんでしたが、応用ができそうな技術ですので覚えておきたいです。
実装例:

#include "bits/stdc++.h"
using namespace std;
int s[510][510];
int main(){
    int n,m,q;cin>>n>>m>>q;
    int l,r;
    for (int i=0; i<m; ++i){
        cin>>l>>r;
        ++s[l][r];
    }
    for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    for (int i=0; i<q; ++i){
        cin>>l>>r;
        cout<<s[r][r]-s[r][l-1]-s[l-1][r]+s[l-1][l-1]<<endl;
    }
}

他にもこんな記事を書いています tqk.hatenablog.jp

tqk.hatenablog.jp

2018-08-19

ABC106 A B C問題 [part1] - tqkoh's diary

ABC AtCoder 競プロ

A問題
- 解法
B問題
- 解法
C問題
- 解法
D問題（次パート）

これはアウトプットして自分の記憶を定着させ実力を高めるための記事です。公式の解説はここにあります。(公式には次パートで説明する二次元累積和については乗っていません)

https://img.atcoder.jp/abc106/editorial.pdf

part2:

tqk.hatenablog.jp

A問題

A - Garden

A*Bの土地に幅1の道を十字にひいたとき、残った土地を求める問題。

解法

道の交差点が隅に来るように道を移動させ等積変形すると、このようになります。よって答えは $(A-1)(B-1)$

#include "bits/stdc++.h"
using namespace std;
int main(){
    int a,b;cin>>a>>b;
    cout<<(a-1)*(b-1);
}

B問題

B - 105

1からNまでの奇数で、約数が8この物の個数を求める問題。

解法

全探索をします。1からNまでの奇数で約数が8この物を数えます。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int n;cin>>n;
    int ans=0,ctr;
    for (int i=1; i<=n; i+=2){
        ctr=0;
        for (int j=1; j<=i; ++j)if(i%j==0)++ctr;
        if(ctr==8)++ans;
    }
    cout<<ans;
}

C問題

C - To Infinity

数字のみからなる文字列Sの、各桁が一日ごとにその桁の数倍になるとき、5000兆日後はK文字目を求める問題です。
どういうことかというと、"1234"が一日で"1223334444"になり、その次に"122223333333334444444444444444"になるということです。
解法
"23"という文字列で考えると、2の桁数は $2^{5000000000000000}$ に増えますから、 $K \le 10^{18}$ より、Kがいくつであっても答えは"2"となります。ここから、1以外の数が出た瞬間、その数が答えになることがわかります。
例えば、"1123"という文字列を考えてみると、5000兆日後には"11222222..."となります。よって、答えは、K<3(1以外が最初に出てくるところ)のとき 1、それ以外 2 となります。
実装ですが、k番目まで見て行って1以外が出た瞬間にそれを出力、k番目まで1以外が出なければ1を出力、とするのが簡単だと思います。(--kをするのを忘れてWAしたなんて言えません)

#include "bits/stdc++.h"
using namespace std;
int main(){
    string s;cin>>s;
    int k;cin>>k;--k;//下のforの条件をi<kにすると--kは必要なくなる
    for (int i=0; i<=k; ++i)if (s[i]!='1'){
        cout<<s[i];
        return 0;
    }
    cout<<1;
}

D問題（次パート）

part2: D問題と今回のABCで学んだこと、二次元累積和についてを書きます

tqk.hatenablog.jp

他にもこんな記事を書いています tqk.hatenablog.jp

tqk.hatenablog.jp

qiita.com

2018-08-12

ABC105 - tqkoh's diary

競プロ AtCoder ABC

超絶初心者緑コーダーのメモ#2です

A問題
- 解法
B問題
- 解法
C問題
- 解法
D問題
- 解法
学んだことメモ
リンク

A問題

A - AtCoder Crackers
n個の物をk人に均等に分けたとき、一番多く持っている人と一番少ししかもっていない人の差を求める問題です。

解法

答えは0もしくは1になります。2以上差があると、多く持っている人から少ししかもっていない人に渡せばもっと均等になるからです。また、差が0となるのはnがkでちょうど割り切れるときだけなので、それを判定するだけでいいです。

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
int main() {
    int n, k; cin >> n >> k;
    cout << (n%k ? "1\n" : "0\n");
}

B問題

B - Cakes and Donuts
4ドルの物と7ドルのものをいくつか買って合計金額がnドルになるものを求める問題です。

解法

全探索すればいいです。(4ドルのものの個数) <= n/4, (7ドルのものの個数) <= n/7 ですが、制約が n <= 100なので普通に25*25とかもう100*100とか全探索しちゃってもいいです。

#include "bits/stdc++.h"
using namespace std;
int main() {
    int n; cin >> n;
    bool f = 0;
    for (int i = 0; i <= n / 4; ++i)for (int j = 0; j <= n / 7; ++j) {
        if (4 * i + 7 * j == n) { f = 1; break; }
    }
    cout << (f ? "Yes\n" : "No\n");
}

C問題

C - Base -2 Number
nの(-2)進数表記を求める問題です。

解法

このように、手計算と同じことをするプログラムを書けばよいです。
-2) -9
-2) 5 　... 1
-2) -2 　... 1
　　1　... 0

#include "bits/stdc++.h"
using namespace std;
int main() {
    long long n; cin >> n;
    string s;
    while (n) {
        if (n % 2)s = '1' + s;
        else s = '0' + s;
        n = ceil((double)n / (double)-2);
    }
    if (s == "")s = "0";
    cout << s << endl;
}

今回は-2進数だったので、割り切れなければ'1'にする、で大丈夫でしたが、-3進数になったりすると、c++の「余りの定義が正負で異なる」という仕様が邪魔をしてくるようになります。どういうことかというと、-5%3が、1とならなければいけないところ-2となります。(pythonなどの言語だとちゃんと1となります。) ただ+3すればいいだけなので問題ないですが。

D問題

D - Candy Distribution
$A_1, A_2, ..., A_n$ の連続した区間の和のうち、mの倍数であるものを数えるという問題です。 $O(N^2)$ から速くできなくて終わりました...

解法

累積和をそれぞれ%m しても変わらないので、問題文の通りに、累積和を求めて、
$A_{i+1}+A_{i+2}+...+A_j = (mの倍数)$ 、すなわち
$S_j\% m - S_i\% m=0 (0\leq i\leq N, i\leq j\leq N)$
を探索すると $O(N^2)$ で、 $N\leq 10^5$ なのでTLEです。 f:id:tako0608:20180812131801p:plain
しかし、実は上の式 $S_j\% m - S_i\% m=0$ を変形すると $S_j\% m = S_i\% m$ となり、
表の $i, j$ 番目の一番下の値が同じ数の区間は、その間の和が $m$ の倍数になることがわかります。(数学をやっている人からしたらこの式が気持ち悪くて最後にmodつけろ、と言いたくなるかもしれませんがプログラムのためなので許して)
その中から例えば上の例だと、0が3個ありますからその中から $i, j$ の2つを選ぶので選び方は ${}_3C_2=3$
通りあることがわかります。同様に1が1個ありますからその中から2つを選ぶ選び方は0通りです。これを足して3が答えです。
実装ですが、表の一番下の値が(0なのは3個), (1: 0個), ...,(k: $B_k$ ) ,..., (m-1: $B_{m-1}$ )という風に値ごとに保存しておいて、最後に
$\displaystyle \sum_{k=0}^{m-1} {}_{B_k}C _2= \sum_{k=0}^{m-1} \cfrac{B_k(B_k-1)}{2}$ を計算すれば答えが出ます。
まずこの考えが思いつかなかったのですが（弱い）、この考えを聞いても「制約が $m\leq 10^9$ なんだから配列が(最大m要素もあって)大きすぎて値ごとに保存するなんて無理じゃないか！」と思いどう実装すればいいかわかりませんでした。これは、「 $N\leq10^5$ なので埋まらない無駄な要素がある」ことを利用して、unordered_mapというデータ構造を使うとできます。これを知らなかったので方法を思いついても解けませんでした。。。

#include "bits/stdc++.h"
using namespace std;
int main() {
    long long n, m, in, s = 0, ans = 0; cin >> n >> m;
    unordered_map<long long, long long> h;
    ++h[0];
    for (int i = 0; i < n; ++i) {
        cin >> in;
        s = (s + in) % m;
        ++h[s];
    }
    for (auto i : h) {
        ans += i.second*(i.second - 1) / 2;
    }
    cout << ans << endl;
}

学んだことメモ

std::unordered_map: a[キー]に値を保存できる配列みたいなやつ。配列だと使うところが少なくて無駄ができるときに有効。要素はpair<const _KTy, _Ty>型になっているので、(要素).firstでキーに、(要素).secondで値にアクセスできる。
ex.

unordered_map<long long, long long> ma;
for (auto i : ma) {//iはmaの要素を遷移する
        ans += i.second*(i.second - 1) / 2;
}

リンク

他にもこんな記事を書いています

qiita.com

tqk.hatenablog.jp

C問題

D問題

結果

感想

A問題

B問題

C問題

D問題

E問題

F問題

最後に

A問題

解法

B問題

解法

C問題

解法

D問題

解法

A問題

解法

B問題

解法

C問題

解法

学んだことメモ

D問題

解法

解法1

解法2

普通の累積和

二次元累積和

D問題に二次元累積和を使ってみる

A問題

解法

B問題

解法

C問題

解法

D問題（次パート）

A問題

解法

B問題

解法

C問題

解法

D問題

解法

学んだことメモ

リンク