AtCoder Regular Contest 078 C - Splitting Pile

　AtCoderのC埋め2つ目。
　ARC078 / ABC067 のC問題「Splitting Pile」です。a[1]からa[N]までの数字が書かれた山札(pile)を上側の数の合計と下側の数の合計の差がなるべく小さくなるようにして2つに分割(split)します。この差の絶対値を出力すればよいです。

#include <iostream>

typedef long long ll;

using namespace std;

int main(){
    int N;  cin >> N;
    int a[N+1];
    ll sum = 0LL;
    for(int i=1; i<=N; i++){
        cin >> a[i];
        sum += a[i];
    }

    ll sunuke = 0LL;  /* 0LLは「long long型の0」という意味。LLでlong long型にキャスト */
    ll araiguma;
    ll ans = (ll) 2e10;
    for(int i=1; i<N; i++){
        sunuke += a[i];
        araiguma = sum - sunuke;
        ans = min(ans, abs(araiguma - sunuke));
    }

    cout << ans << endl;

    return 0;
}

　とりあえずa[1]からa[N]までの合計をsumにとります。そんで、a[i]をi=(1→N-1)で動かして、上側の合計(sunuke=Σ(k=1→i))と下側の合計(araiguma=sum-sunuke)との差がansより小さいかなあとゆーのをやればできます。

　そんで、関数abs(x)は、xの絶対値を返す関数です。便利です。if文使って3行くらいで書けるので覚えなくてもいいです。
そんじゃばいばい。

ll abs(ll x){
  if(x<0) return -x;
  else return x;
}

AtCoder Regular Contest 080 C - 4-adjacent

　AtCoderのC問題を埋めようと思い立ったので、頑張る。

　今回は、ABC069、ARC080のC問題「4-adjacent」。adjacentはグーグル先生によると「隣接」という意味らしい。N個の整数a[i]がもらえるので、それを並べ替えて、「隣接」するすべてのaの積(任意のiについてa[i]*a[i+1])を「4」の倍数にできるか？　という問題。
　つまり、数列aを並べ替えて、奇数の隣に必ず4の倍数を持ってこれるかという問題。偶数の隣は、偶数であれば何でもよいからだ。つまり、見るべきはaの具体的な個々の数ではなく、aに含まれている4の倍数の数と奇数の個数である。ただし、奇数、4の倍数、奇数のように、両端が奇数のパターンもある(偶数が0個の場合のみ)ので、注意しようね、って感じ。

#include <iostream>
using namespace std;

int N, a;
int odd=0, even=0, multiple4=0;

int main(void){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> a;
        if(a%2) odd++;
        else if(a%4) even++;
        else multiple4++;
    }

    bool ans = true;

    if(!even){
        if(odd > multiple4+1) ans = false;
    }else{
        if(odd > multiple4) ans = false;
    }

    if(ans) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

　なにかコードについて言うとしたら、if(!even) のところかな。前にも書いたけど、C++やCでは、false値として0が設定されているので(0以外はtrue)、even の否定 !even とは、even==0 と同値です。even==0 のとき、even は偽(false)なので、!even は真(true)になります。even!=0 のときは、even は真(true)なので、!even は偽(false)になります。

　ではでは。

AtCoder Beginer Contest 070 C - Multiple Clocks

　みなさん、おはこんばんにちは。またしても #いいねされた数だけAtCoderでAC タグのための問題です。

　ABC070のC問題「Multiple Clocks(意訳：時計がいっぱい)」です。N個の自然数T[i] (1<=i<=N) がもらえるので、T[1]からT[N]までの最小公倍数を教えてあげる問題です。

#include <iostream>
typedef long long ll;
using namespace std;
 
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
 
ll lcm(ll a, ll b){
    ll g = gcd(a, b);
    return (a / g) * b;
}
 
int main(void){
    int N;  cin >> N;
    ll T, ans = 1LL;
    for(int i=0; i<N; i++){
        cin >> T;
        ans = lcm(ans, T);
    }
 
    cout << ans << endl;
 
    return 0;
}

　関数gcdは最大公約数(GCD:greatest common divisor)を返し、関数lcmは最小公倍数(LCM:least common multiple)を返します。gcdでやってるのは、ユークリッドの互除法で、lcmでは、2つの自然数a,bについて、LCM = (a*b)/GCD が成り立つことを使って、オーバーフローしないように計算しています。この中で、gcdを呼び出しています。
　あと、私みたいに次のようにlcmを求めてしまうと、 (a, b)=(1,1e18) とかのとき(2e9=2*10^9)、O(1e18)になってしまって、余裕でTLEになってしまいます。気を付けましょう。

#include <iostream>
typedef long long ll;
using namespace std;

ll a, b;
ll lcm(x, y){
  if(x==y) return x;
  else if(x<y) x += a;
  else if(y<x) y += b;
  return lcm(x,y);
}
//

　なので、ユークリッドの互除法を使います。ユークリッドの互除法なら、O( log(1e18) ) だそうです。つまり、全体でO(Nlog(1e18) < 1e6)なので、余裕です。
　ちなみに、O(1e9) 程度が競プロにおける標準的な(2秒)計算量の制限になります。

　あ、あと、typedef はだいたいdefineみたいな感じだけど、既にある型(int, bool, long long 等)に新しい名前(integer, boolen, ll 等)を与えたいときに使います。

　じゃ、ちゃお。

AtCoder Beginer Contest 061 C - Big Array

　twitterで #いいねされた数だけAtCoderでAC というハッシュタグを使ってしまったので、そのうちの一問です。

　ABC061のC問題です。問題名は「Big Array」、空っぽの配列Big Arrayにa[i]という数をb[i]個入れる操作をi=(1→N)について行ったとき、Big ArrayのなかでK番目に小さい数を出力しなさいという問題です。ちなみに、実際に問題通りのBigArrayを作ろうとすると、恐らくMLEになります。

#include <iostream>
#define a_MAX 100000
using namespace std;

long long ary[a_MAX+1];

int main(void){
    int N;  long long K;
    cin >> N >> K;

    int a, b;
    for(int i=0; i<N; i++){
        cin >> a >> b;
        ary[a] += b;
    }

    long long ans = 0;
    for(int i=1; ans<K && i<=a_MAX; i++){
        ans += ary[i];
        if(ans>=K){
            cout << i << '\n';
            break;
        }
    }

    return 0;
}

　ary[i]に、Big Arrayのなかにiという数が何個含まれているかを記憶します。そんで、aryの中身を小さい順にansに足してって、ansがちょうどK以上になるようなiの値を出力してやれば、K番目に小さな値を出力したことになります。

　んで、こっからは技術的な何か
　#defineっていうのは、マクロ処理ってやつで、#define a b とやると、ソースコード内のaという"文字列"をすべてbという"文字列"に置き換えてコンパイルしてくれます。便利な使い方として、

#include <iostream>
#define f(a,b) a+b
int main(){
  int sum = f(3,4);
  cout << sum << endl;
}

などとすると、 f(3,4)という文字列を3+4という文字列に変換してコンパイルしてくれるので、上のコードだと7が出力されます。
　便利ですが、2人以上の人数で開発を行うときは、絶対に使わないようにしてください。バグと宗教戦争のもとです。

　では、ばいばい。

ABC075 (AtCoder Beginer Contest 075)

　久しぶりの更新です。正直このブログの存在を忘れてましたm(_ _)m

　おとといABCがあったので、それの解答を載せたいと思います。C問題のコンパイル通らなくて辛かったです。終了数分前にやっとコンパイル通したらWAだったという。。。そんな感じのABCでした。そもそも手元でコンパイルぐらい通してから提出しろよという(←n回目の懺悔(n≥3))

A - One out of Three

　まずはA問題ですね。問題名は「One out of Three (3人の中の一人)」。３つの整数 A、B、C がもらえるので、仲間はずれ君を探し出してやればACをもらえます。入力例1が 5 7 5 なのはご愛嬌ですね。

#include <iostream>
using namespace std; 
int main(void){ 
  int A, B, C; 
  cin >> A >> B >> C; 
  if(A==B) cout << C; 
  else if(B==C) cout << A; 
  else cout << B; 
  return 0; 
}

　気づきましたでしょうか。そうです。シンタックスハイライターが使えるようになりました(嘘。はてな記法です。できてなかったらごめんなさい。

　肝心のコードですが、今回はスタートダッシュしたかったので入れ子{}というものをできるだけ使わない書き方にしました。提出コードはchar型の変数宣言をコメントアウトしてたりしててもっと汚いです。。。

　if文やfor文の{}は、操作が1行で済むなら使わなくても大丈夫です。インデント的にどうなの？　と思うことはありますが。。。下のコードのように書いても問題なく動きますが、さすがに見づらい(可読性が低い)ので自重しましょう。可読性は大事です。

if(A==B) 
cout << C; 
else if(B==C) 
  cout << A; 
else cout << B;

B - Minesweeper

　つぎはB問題です。問題名は「Minesweeper」明らかにms社のパソコンに積んであるあのゲームですね。はじめに H * W の文字列がもらえて、' # ' が爆弾(地雷)マス、' . ' が空きマスです。空きマスを周囲8マスにある爆弾の数に置き換え、爆弾マスはそのまま ' # ' で出力できればACもらえます。

#include <iostream>
using namespace std;

int main(void){
    int H, W;
    cin >> H >> W;

    char m[H+2][W+2];
    for(int i = 0; i < H+2; i++){
        for(int j = 0; j < W+2; j++){
            if(!i || !j) m[i][j] = '.'; //!i は i==0 と同義
            else if(i==H+1 || j==W+1) m[i][j] = '.';
            else cin >> m[i][j];
        }
    }
            
    for(int i = 1; i < H+2; i++){
        for(int j = 0; j < W+2; j++){
            if(m[i][j] == '.'){
                int bom = 0;
                if(m[i-1][j-1] == '#') bom++;
                if(m[i-1][ j ] == '#') bom++;
                if(m[i-1][j+1] == '#') bom++;
                if(m[ i ][j-1] == '#') bom++;
                if(m[ i ][j+1] == '#') bom++;
                if(m[i+1][j-1] == '#') bom++;
                if(m[i+1][ j ] == '#') bom++;
                if(m[i+1][j+1] == '#') bom++;
                cout << bom;
            }else{
                cout << "#";
            }
            if(j == W-1) cout << endl;
        }
    }
    return 0;
}

　今いるマスの左上、左、左下、上、下、右上、右、右下のマスを、そのマスあるかな～(端っこじゃないよね？)といちいち確認しながら爆弾あるかな～と数えていってます。最近セグメントエラー(coreを出力しました)という文字列をよく見るので、変なとこ(配列のサイズの外側)の値を参照したりしないように、配列mの大きさを上下左右に1つづつ広くとってます。以上。

C - Bridge

　つづいてはC問題です。問題名は「Bridge」、グラフから辺を取り除いたときに、グラフ全体が非連結になるような辺を「橋」というそうです。最初に、いつもの自然数N、Mがもらえるので、N個の頂点を結ぶM本の辺がもらえるので、上手いことやって橋の本数を求めてください、という問題ですね。

#include <iostream>
using namespace std;

bool g[51][51];
bool gg[51][51];

bool cone(int n){
  bool rtn=true;
  bool ck[n+1] = {false, true};
  for(int k=0; k<n; k++)
    for(int i=1; i<=n; i++)
      for(int j=i+1; j<=n; j++)
        if(gg[i][j] && (ck[i] || ck[j]))
          ck[i]=true, ck[j]=true;

  for(int i=1; i<=n; i++)
    if(ck[i]==false) rtn = false;

  return rtn;
}

bool coneRemoveAB(int n, int a, int b){
  for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
      gg[i][j] = g[i][j];

  gg[a][b]=false;
  gg[b][a]=false;

  return cone(n);
}


int main(void){
  int n, m;
  cin >> n>> m;

  int a[m], b[m];
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i];
    g[a[i]][b[i]] = true;
    g[b[i]][a[i]] = true;
  }

  int bridge = 0;
  for(int i=0; i<m; i++)
    if(!coneRemoveAB(n, a[i], b[i])) bridge++;

  cout << bridge << endl;
  return 0;
}

　bool型の配列g[i][j]は、iからjへの辺があるかどうかを記録します。関数coneRemoveABで、グラフgから辺abを取り除いた配列ggを作って、関数coneで、グラフ全体が連結かどうかを判定します。これをm回(辺の数)だけ繰り返してあげると、取り除いたときにグラフ全体が非連結になる辺(橋)の数が分かるというわけです。
　冒頭にも書いた通りコンテスト中にC問題は通せなかったのですが、その原因は関数coneの3重ループです。2重ではいけません。gg[1][2]==false, gg[1][3]==true, gg[2][3]==true のときなど、嘘関数になってしまい、、、
　つまり、2重ループではいけないのです(コンテスト終了直前に気付いた)。それで3重ループにするわけですが、じゃ何回繰り返すの？　ってことなんですが、1番多いときで、gg[2][3], gg[3][4], gg[4][5], ... ... , gg[n-1][n], gg[n][1] だけがtrueみたいな感じのときで、n回なんですね。というわけで1番外側のループはn回繰り返せばいいわけです(←だいたいワーシャルフロイド法)。みなさんは全探索ぐらい余裕で書けるようになりましょう()

　D問題も一応コンテスト中に実装しようとしたんですが、vectorの使い方が分からないままvector使おうとして死んだので、、、

　というわけでまた次回にゃ～～～～～～～～～～～～～～～～～～～(てーげー)

パワーワード //競プロは関係ありません

　ただただパワーワードだと思ったものを発言者の許可なく順に上げていくだけの何の生産性もないページ。無駄に更新される(予定)。旅行で競プロを離れている間に何も書かないのもあれかなって。

・カロリーの高いひととき　←New!

・ところでヤードポンド法は滅ぼさなければならない

・赤になれないうちは典型問題すら解けてないということ

・こっちは遊びでブスやってるんじゃないんだ

・治安の悪い髪の毛

・数珠映え(ダイアモンドとかダサすぎ)

・所用の腹痛があるので早退します

以上

AtCoder Beginner Contest 073

　日曜にアクセス解析とかいう機能を使ってみたんだけど、アクセス数が毎日１(なお自分の模様)でちょっと心折れそうだった。yukicoderの解説に上げたらアクセス数が４になったので、ちょっと頑張ろうと思った今日であります。

　というわけで、土曜日(9月9日)にあったABC073の挑戦記録ですね。D問題(最短経路問題)が解けなかったのでまだまだですね。要復習です。。。

　じゃあA問題いきますね。問題名は「September 9」、thが欲しいところですね。AtCoderはいつも通り２桁の自然数Nを与えてくれるので、一の位か十の位に「９」が含まれているかどうかを判定すればOK。書き方はいろいろ。

　まずはansの型宣言を忘れ、char型の"9"とint型の9を間違えてしまって私がCE＆WAを食らってしまったchar型配列を使うコーディング。このように書けば通るはずです。

#include <iostream>
using namespace std;
bool ans;
int main(){
    char N[2];
    cin >> N[0] >> N[1];
    if(N[0]=="9" || N[1]=="9")ans++;
 
    if(ans)cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

　この前も書いたけど、グローバル変数として宣言すると、勝手に0とかそれっぽいもの(falseとか"\0"とか)に初期化されるので、悪い子(競プロ以外ではあまり使わない方がいいかな)だけど使ってあげてね。タイプ時間とソースコード長の短縮に役立つよ。あと、C++においてbool型は、falseが0、trueが1に対応してるということも、覚えておくと便利ですね。

　まあ、コンテスト中は思考停止してて、なんでWA食らったのか探すのがめんどくさかったので、最初っから書き直したんだ。これでACです。想定解はこっちらしいよ。

#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    
    int N1 = N%10;
    int N10 = N/10;
 
    if(N1==9 || N10==9){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

　えっと、C系統において整数型(int, long, long long, etc)では、小数点以下は切り捨てられるから、それを生かしたコードですね。以上。

　次はB問題ですね。問題名は「」、1e9(==10^9, 指数表記は便利なので使っていきたい)文字の文字列には、毎度お馴染みN個の欠損があります。i番目の欠損はl[i]文字目からr[i]文字目までで、この文字列全体で何文字欠損があるか教えてあげればいいんですが、Beginnerへの優しさ(易しさ？)ということで、欠損範囲が重なる((l[i],r[i])=(1,3) && (l[j],r[j])=(2,4) && i≠j)ようなことはありません。つまり、各欠損の文字数を適当な変数(このコードではans)に足していけばACがもらえそうですね。

#include <iostream>
using namespace std;

int main(){
    int N;
    cin >> N;

    int l, r, ans=0;
    for(int i=0; i<N; i++){
        cin >> l >> r;
        ans += r-l+1;
    }

    cout << ans << endl;
    
    return 0;
}

　このとき気を付けるのは、lとrを配列に入れないということですね。int型の変数は１つにつき32bit(==4Byte)くらいなので、要素数がNの最大値1e9個であるようなint型配列を作るときは、配列１つにつきメモリが(4×1e9)Byte ≒ 4Gb 必要になります。つまり、lとrを配列に入れていくと、私のようにMLE(Memory Limit Exceeded)を食らってしまうというわけです←　気を付けましょう。

　いま奄美大島ー成田のバニラエアの便の中でこれ書いてるんだけど、対地速度950km/hとか機長さんが言ってるので、人力で出せる速度でちゃんと飛行してる鳥人間コンテストの機体製作ってすげえんだなって思った

　では、C問題にゆきましょう。またしてもNが登場するよ。問題名は「」、N個の自然数A[N]がもらえるんで、A[1]から順番に、紙に書いてゆくよ。でも、すでにA[i]が紙に書いてあったら、それは跡形もなく消すよ。例えば、N=3, A={1,2,1,1}だと、紙の上では、1 → 1, 2 → 2 → 1, 2 てな感じで書かれてある数が変わるよ。これもMLEに注意しようね。

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

int main(){
    int N;
    cin >> N;

    set<long long> onPaper;

    long long A;
    for(int i=0; i<N; i++){
        cin >> A;
        bool c = onPaper.erase(A);
        if(c==0){
            onPaper.insert(A);
        }
    }
    
    cout << onPaper.size() << endl;
    return 0;
}

　このコードではsetっていうやつを使っていますね。まあqueとかstackっぽい感じで、要素を追加するときには 変数名.insert(要素) 、逆に要素を消すときには 変数名.erace(要素) って書けばOK。要素数が知りたいときには 変数名.size() 。んで、setやstackと違って、setには同じ数は入らない(要素は重複しない)という大変便利な特徴がありましてですね、今回はそれを使いました。

　onPaper.erace(A) ってやるとonPaperの要素Aを消せるんだけど、当然onPaperの中にAっていう要素がないとAは消せないんだよね。つまり、.erace()って書いてもeraceされないことがあるわけで、それがわかんないのは困る。というわけでうまくいったら1(true)、うまくいかなかったら0(false)を返してくれる機能があるんだよね。便利だね。

　何日もまたいでやる気なくなっちゃったからここで終わるね(←おい)。