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

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

A問題

$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

tqk's diary

競プロとか

ABC107 A B C問題 - tqkoh's diary

A問題

解法

B問題

解法

C問題

解法

学んだことメモ