ARC098 D - Xor Sum2

問題概要

長さNの整数列Aがある.
二点l, r ( l < r )を決めて,  A_l ~  A_r を全て足した値と全て xor した値が等しい lr の組みの個数を求めろ.

解法

制約が2*105なので0(n2)解は無理っぽそうなので,O(n)かO(nlog(n))ぐらいかなぁって気持ちになれるけど,コンテスト中は解法は降ってこなかった. 結論を言うと  A_l ~  A_r の整数のうち, 各bitの立っている整数の個数が1個以下だと 和 と xor が等しくなる. と言うこと.

例えば, 2 と 10 だと, 2進数にすると 0010 と 1010 となる. これの和は 1100 , xor は1000になる. ここで等しくならない原因は,同じ場所のbitが2つ以上立っていると, 和では繰り上がらなければいけないところが xor では繰り上がらず0になってしまうので和と xor は等しくならなくなってしまうことだ.

これをどうやって数えるかと言うとしゃくとり法を使えばいいみたい . しゃくとり法は0(n)なのでACできる.

ソースコード

int main(){
    long long n,ans=0;
    int a[2000005];

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long long xsum=0,sum=0;

    int r=0;
    for(int l=0;l<n;l++){
        while(r<n){
            if((xsum ^ a[r])!=(sum + a[r]))break;
            xsum=(a[r] ^ xsum);
            sum+=a[r];
            r++;
        }
        ans+=(r-l);
        xsum^=a[l];
        sum-=a[l];
    }
    cout<<ans<<endl;
    return 0;
}

tourist解

これは解説のO(n)解なのかな?

各bitが最後に立っていたのはいつかを記録する配列を用意しておき,更新するタイミングでその時間のmaxをとってあげればi-max+1でiまでの題意をみたす個数がもとまる.

正直これ書いてて自分で何言ってるのかわからなくなったので,ソースコードを見れば一瞬でわかると思います.感動しました.

一言

解説ブログを書きまくって解説するのうまくなってやるぞい!!

ARC097 D-Equals

問題概要

1 ~ Nの順列p1,p2,p3, ... ,pnが与えられる.次にm個の1 ~ Nの整数のペア(a, b)が与えられる.このペアは与えられた順列の整数aと整数b( a,b は添字のことではない )の場所をswapさせることができる. これらの操作を好きな数だけ繰り返してPi = iとなるiの数として考えうる最大値を答えよ.

解法

連結成分内なら好きなように移動することができる.つまり,移動可能な場所のグループを作ってpi と i は同じグループに属しているかを判定すれば良い.このようなグループ分けはUnion-Find木を使えば高速に処理ができるのでそれを使う.
Union-Find木はAtCoderが説明スライドを公開しているのでそちらを参照されたし.
Union-Findの説明スライド

ソースコード

class Union_Find{
private:
    vector<int> par, rank;

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
public:
    Union_Find(int Max_Node){
        par.resize(Max_Node);
        rank.resize(Max_Node);
    }

    void init(int n) {
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
        }
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return ;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y])rank[x]++;
        }
    }

    bool same(int x, int y){
        return (find(x) == find(y));
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> in(n);
    for(int i = 0; i < n; i++)cin >> in[i];
    Union_Find uf(n + 10);
    uf.init(n + 1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
        uf.unite(b, a);
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(uf.same(in[i], i+1)){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

感想

考察実装込みでだいたい10分くらいで解けたので大満足. Union-Findを使う問題をあまり見たことがないのでいい練習になった.

あと,こういう記事書くの難しいよね

RUPC2018 参加記

RUPC参加前

twitterで今年もあるよとのことだったので参戦。 atnd.org

1日目-立命館大学セット

怒髪さん、masumiさん、ksawさんの4人でdmkmというチームで参加しました。
自分はC問題を担当していましたが、解法が舞い降りてこなかったのですぐ助けてした。弱いね。
結局解法を教えてもらったが実装できそうになかったので怒髪さんに投げた。
E問題はksawさんが6通り辺をはってダイクストラやるだけ、と解法を教えてくれたので実装するもWA。
初期化の値が小さかったみたい。見事な戦犯をかます。
自分の仕事は以上で、チームとしては全完を成し遂げた。
チームメンバープロすぎる。

1日目-懇親会

twitterでよく見かける人々と喋ったりした。 去年のようにキャベツが大量に残っていたわけじゃなく平和だった。

2日目-会津大学セット

2日目はtuki_remonさんとkeiさんでkankitukeiというチームで参加した。
由来はレモンとみかんで柑橘、keiさんなので系、で柑橘系( 個人的にめっちゃ好きなチーム名 )

自分はB問題を解いて、あとはFとG問題の考察をした。

Fは移動パターンが数通りしかないから筋肉で殴れそう。
実装バグらせそうだったのでtuki_remonさんに実装を任せる。

Gは1つのペアで条件が成り立つなら優先的に消していき、それ以外のもので一般マッチングすればいいのでは?みたいな気持ちになった。
一般マッチングをどう実装すればいいのかわからなかったのでkeiさんに実装を任せる。
二人ともAC。はいプロ。

考察を他人に教えるということに慣れてなかったので、つたない日本語で考察を二人に言って申し訳なかった...。

この日は6完で、個人的にRUPC史上最も活躍した日だと思ってます。(ほんまか)

2日目-懇親会

初めて酎ハイをジョッキ2杯飲んだけど全く酔った感じがしなかった

どっからどう見ても酔ってますね。はい。

3日目-北海道大学セット

3日目はjimmyさんとわたあめさんとでjwmというチームで参加。

A問題は、はいという感じだったので実装AC B問題はいつのまにかACされていた。

C問題はわたあめさんから解法を聞くも実装方法がピンと思いつかず、ひどいソースコードになってしまった。その上ガバガバ実装だったので助けてもらいながらコードを修正する。これでいけるだろうということで提出するもWA。コンテスト中にはACできず。

D問題はラスト1分を切っている状態でjimmyさんが通してた。プロ。

結局この日は3完。知識不足というか実装力のなさを痛感した。

終わってから番兵さんとTreeoneさんにC問題のコーナーケースを聞いて辛い気持ちになった。

その後

RUPC参加者とにぼ二郎食べに行くぞー!!と思ったら定休日だったらしく別のラーメン屋に行った。

最後に

チームを組んで競プロするのはやっぱり楽しかったし、自分よりはるかにできる人の考察を聞いたりするのはすごくタメになる。 それに競プロのモチベーションも高まったので参加してよかったと思う。

次に参加するときには青くなっていたいなぁ

webpackで「Module not found: Error: Can't resolve 'fs'」と出てきた時の対処法

エラーいっぱいでつらい

reactを使っていた時に踏んだエラーで、npm webpackしたら大量のエラーが出てきて、その大半がModule not found: Error: Can't resolve 'fs' ( ここの'fs' が 'net' とか 'tls' と表示されていたのもあった)。 とりあえず、 yarn add fs でnot foundなモジュールをインストールしたり、エラーが出ているモジュールを別のバージョンでインストールしたり試行錯誤してもダメだった。 ググってみたりしたけど、ググり力が低いため見つけるのに時間がかかった。

原因

2018/5/27追加 node.jsが使われている時は「target: 'node'」を記入しないといけなくて、自分はAPIを叩くライブラリを使っていたのでこのエラーが起きていたみたいですね。 自分はjavascriptしか書いてないと思っててもライブラリでnode.jsが使われていると言う落とし穴があるんですね。

対処法

webpack.config.jsonに「target: 'node'」を追加すればいい。 たったこれだけでした。

詳しくはこのサイトに書いてます。
https://jlongster.com/Backend-Apps-with-Webpack--Part-I

ABC088 の話

タイポとか色々やらかして辛いコンテストでした

A - Infinite Coins

https://beta.atcoder.jp/contests/abc088/tasks/abc088_a

(N % 500 <= A)が成り立てばYesを出力すればよいよい

int main(){
    int n, a;
    cin >> n >> a;
    n %= 500;
    if(n <= a)cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}

B - Card Game for Two

https://beta.atcoder.jp/contests/abc088/tasks/abc088_b

両者とも最大になるようにカードを取っていくのだから当然数字が大きいカードから取っていくのでそれをシュミレーションする。

int main(){
    int n;
    int a[105];
    cin >> n;
    int aa = 0, b = 0;
    rep(i, n)cin >> a[i];
    sort(a, a + n, greater<int>());
    rep(i, n){
        if(i % 2 == 0)aa += a[i];
        else b += a[i];
    }
    cout << abs(aa - b) << endl;
    return 0;
}

C - Takahashi's Information

https://beta.atcoder.jp/contests/abc088/tasks/abc088_c

a1, a2, a3の値が決まったとすると、b1, b2, b3がどんな値を取っても a1 と a2 を使ったマスの差はどの行を見ても同じで、同じく a2 と a3 を使ったマスの差もどの行を見ても同じである規則性(?)がある。

int main(){
    int c[4][4];
    rep(i, 3){
        rep(j, 3){
            cin >> c[i][j];
        }
    }
    
    if(c[0][0] - c[0][1] == c[1][0] - c[1][1] && c[1][0] - c[1][1] == c[2][0] - c[2][1] &&
       c[0][1] - c[0][2] == c[1][1] - c[1][2] && c[1][1] - c[1][2] == c[2][1] - c[2][2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

if文が長くなってすっごい見づらいな...

D - Grid Repainting

https://beta.atcoder.jp/contests/abc088/tasks/abc088_d

自分の大好きなアルゴリズムはBFSなのででてきたときは興奮した:dohentai:
や、BFSって真面目にコツコツとする感じが可愛いでしょ?可愛いですね。

BFSでスタートからゴールまでの最短距離を計算して、(' . 'の数 - 最短距離 - 1)が最大スコアになる。 最後の -1 はゴールの部分は' . 'にしておく必要があるからです。

int h, w;
int d[55][55];
char s[55][55];
 
void BFS(){
    rep(i, 55)rep(j, 55)d[i][j] = INF;
    d[0][0] = 0;
    queue<int> q;
    q.push(0);q.push(0);
    while(q.size()){
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();
        for(int i = 0;i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(0 <= xx && xx <= w && 0 <= yy && yy <= h && s[yy][xx] == '.'){
                s[yy][xx] = '#';
                d[yy][xx] = min(d[yy][xx], d[y][x] + 1);
                q.push(xx);q.push(yy);
            }
        }
    }
}
 
int main(){
    int cnt = 0;
    cin >> h >> w;
    rep(i, h)rep(j, w){
        cin >> s[i][j];
        if(s[i][j] == '.')cnt++;
    }
    h--; w--;
    BFS();
    if(d[h][w] == INF)cout << -1 << endl;
    else cout << max(0, cnt - d[h][w] - 1)<< endl; 
    return 0;
}

今年一年のふりかえり

1月

  • すこし競プロにハマりだした
  • 初めてABCで全完してはしゃぎまくってた記憶あり

2月

  • 期末試験にTLEして追試した
  • RUPCに参加することが決まってABC-A問題B問題埋めが始まる
  • それしか覚えてない

3月

  • RUPCに参加。完全に競プロにハマった
  • この時初めて競プロで美味しいご飯が食べれた

4月

  • 2回生になったけどhogeって感じだった
  • 競プロ1回生が多くて生き残りが多くなりそうな気持ちになる

5月

  • 某社にインターンのプログラミング面接をする。落ちたけど、すごいいい経験になった
  • AOJ-ICPC埋めしてた
  • いいねされた数だけAtCoderでACするがスタート

6月

  • AOJ-ICPC埋めの難易度が上がってきて辛くなってくる

7月

  • ICPCに参加。
  • 期末めんどくさかった

8月

  • twitter apiを使ったwebアプリを作った。

9月

  • AtCoder で水色になった
  • ナナチかわいい

10月

  • 何も覚えてない...

11月

  • TOEICでそこそこの点が取れた
  • 講習会でBFS回を担当した。講習会難しい...

12月

  • もう一本webアプリを作り始める。

まとめ

激動の一年でした (小並感 ( みかんだけに(は?) ) )

さて、競技プログラミングの季節になりました

OIT Advent Calendar 2017

この記事は、 OIT Advent Calendar 2017の7日目の記事です。

簡単に自己紹介

大阪工業大学2回でIS科の者です。 emacsとneovimが好きでVisual Studioも好きだし、sublimeTextも案外嫌いじゃない、ただの浮気者です。 競技プログラミングチームとHxSに所属していて、🔥精進🔥したいなーと思いながらオフツゥンから出られない毎日を送ってます。 最近はwebアプリ作ったり、courseraで機械学習勉強したりしてのんびり過ごしてます。 ナナチかわいい

競技プログラミング #とは

与えられた問題をプログラミングでどれだけ多く、早く、正確に解けるかを競う競技です。 これだけ見たら、「なんかハードル高そうだなぁ...」と思う人がいるかもしれませんが、実際そんなことはなくて弊学で言えばC演習Ⅰが理解できれば大丈夫です。競技プログラミングをするにあたって必要な知識はfor文、while文、if文が使えれば競技プログラミングはできます!やったね!!!

どんな人にオススメ?

パズルとか数学とか好きな人は多分面白くできると思う。 あとは、プログラミング言語勉強したけど使える場所がないとか、単純にプログラミングするのが好きな人も楽しくできると思う。 あと、就活意識してる人もオススメできそう。最近は企業コンテストもあってドワンゴとかコロプラ主催のやつもある。ちなみにこれは上位に入ったら1次面接免除みたいな制度もあるみたい。 自分はパズルとか数学とかは苦手です。単純にプログラミングするのが好きなのでやってます。 いや、競技プログラミングは本当にプログラミング欲を満たしてくれるんですよ...素晴らしい... (だからみんなもやろうな??)

どんな力が身につくの?

自分がやった感想としては、自分の考えてる処理をソースコードにする能力とアルゴリズム力( ほんまか )がついてる気がします。 ( タイピングスピードも心なしか上がった気がする...) 競技プログラミングは色々な問題を解くので、「あ!これ競技プログラミングでやった処理だ!」みたいなことが時々あります。

競技プログラミングのサイトまとめ

AtCoder

f:id:mkan_0141:20171206203851p:plain 日本のプログラミングコンテストサイト。ほぼ週1(土日のどちらかで時間は夜9時から)でコンテストが開かれてるので参加しやすい。 使い方は

Atcoder - プロコン(競プロ) Wiki*

を参照してください。初参加の人はAtCoder Beginner Contestに出るといいです。 ちなみにさっき言ってた企業コンテストはこのサイトで行われます。

AizuOnlineJudge

f:id:mkan_0141:20171206204604p:plain プログラミングの問題が大量にある。上手く使えばプログラミング演習のテスト勉強にもなるし、実力もつくので良い。

まとめ

競技プログラミングを始めよう!!!!!