AOJ1136 Polygonal Line Search ~ 座標を90度回転させたくなったので ~

問題

Polygonal Line Search

方針

・比較対象を90度ずつ回転させて始点を元の図に合わせてひたすら判定を繰り返す.
・後ろから比較しないと一致しない場合があるのでそれを考慮する.
計算量的に泥臭く書いてもTLEしないと思うので実装を頑張る.

座標の90度回転

自分はcmathのsinとかcon関数を使ってよしなにする方法を真っ先に思いついたけど,よくよく考えてみると90度時計回りの回転なので

x = y
y = -x

で実現できる.証明とかはググれば出てくると思う.

回答コード

bool check(vector<pi> comp, vector<pi> target){
    if(comp.size()!=target.size())return false;
    for(int z=0;z<2;z++){
        for(int i=0;i<4;i++){
            bool ok=true;
            int x=target[0].first-comp[0].first;
            int y=target[0].second-comp[0].second;
            for(int j=0;j<(int)comp.size();j++){
                if(comp[j].first+x!=target[j].first||comp[j].second+y!=target[j].second){
                    ok=false;
                }
                int tmp=-target[j].first;
                target[j].first=target[j].second;
                target[j].second=tmp;
            }
            if(ok)return true;
        }
        reverse(all(target));
    }
    return false;
}

void solve(int n){
    int m;
    cin>>m;

    vector<pi> comp(m);
    for(int i=0;i<m;i++){
        cin>>comp[i].first>>comp[i].second;
    }

    for(int i=0;i<n;i++){
        cin>>m;
        vector<pi> diff(m);
        for(int j=0;j<m;j++){
            cin>>diff[j].first>>diff[j].second;
        }
        if(check(comp,diff))cout<<i+1<<endl;
    }
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        solve(n);
        cout<<"+++++"<<endl;
    }
    return 0;
}

終わりに

色々解説見たけど,この解法が一番シンプルでバグを埋め込みにくい気がする.
それから,実はこの問題は半年前に挑戦してWA出しまくって解けなかった問題だったりする.
以前は90度回転解法ではなくて,「どの向きにどれだけ移動しているか」みたいな方針で解いていたので,割と複雑なコードになってバグを埋め込みまくった挙句リタイアしていたなぁ...

ARC098 D - Xor Sum2

問題概要

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

解法

制約が2*10⁵なので0(n²)解は無理っぽそうなので,O(n)かO(nlog(n))ぐらいかなぁって気持ちになれるけど,コンテスト中は解法は降ってこなかった. 結論を言うと ~ の整数のうち, 各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でよく見かける人々と喋ったりした。 去年のようにキャベツが大量に残っていたわけじゃなく平和だった。

みかんは完食されていました
嬉しいみかんー >< pic.twitter.com/JMkAb93PH7

— 🍊みかん🍊 (@mkan_0141) 2018年3月26日

2日目-会津大学セット

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

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

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

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

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

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

I問題作問者にI問題のタイトルを叫びながらりんご潰して欲しい

— 🍊みかん🍊 (@mkan_0141) 2018年3月27日

2日目-懇親会

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

お前らレモン残すんじゃねえぞ
みかんとの約束だからな！
#rupc2018 pic.twitter.com/rwfnUpRgvI

— 🍊みかん🍊 (@mkan_0141) 2018年3月27日

レモン完食🍋🍋🍋🍋
#rupc2018 pic.twitter.com/xLQaMGIfnm

— 🍊みかん🍊 (@mkan_0141) 2018年3月27日

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

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

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

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

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

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

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

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

C問題ゆるせん

— 🍊みかん🍊 (@mkan_0141) 2018年3月28日

その後

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

RUPC参加者とラ pic.twitter.com/GfQGIY5MPR

— 🍊みかん🍊 (@mkan_0141) 2018年3月28日

最後に

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

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

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なモジュールをインストールしたり、エラーが出ているモジュールを別のバージョンでインストールしたり試行錯誤してもダメだった。 ググってみたりしたけど、ググり力が低いため見つけるのに時間がかかった。

対処法

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

原因

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

詳しくはこのサイトに書いてます。
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アプリを作り始める。

まとめ

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