2020-03-28

Codeforces #265 Div1 B. Restore Cube

Codeforces 幾何

問題

8点の座標が与えられるので(x,y,z)を自由に並びかえたとき立方体の頂点できるか判定せよ。

問題リンク：http://codeforces.com/problemset/problem/465/D

解法

各点の座標の並べ方は $3! = 6$ 通り。1点固定して他を全探索しても高々 $6^{7}$ 通りなので全探索できる。

あとは8点の座標が与えられたときにそれらが立方体の頂点になっているかを判定すればよい。

自分は、

8点の座標の平均となる点をOとして、Oから各点までの距離がすべて等しい
各点から異なる点への距離を求め、そのうち小さい3つの距離がすべて等しい

を満たすとき立方体としたらACできた。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr double EPS = 1e-9;

int n = 8;
vector<vector<int> > pos(n, vector<int>(3)), tmp(n, vector<int>(3));

double dist(vector<int> &p){
    return sqrt(pow(p[0],2)+pow(p[1],2)+pow(p[2],2));
}

double dist(vector<int> &p, vector<int> &q){
    return sqrt(pow(p[0]-q[0],2)+pow(p[1]-q[1],2)+pow(p[2]-q[2],2));
}

bool isCube(){
    int OX = 0, OY = 0, OZ = 0;
    for(int i=0;i<n;i++){
        OX += pos[i][0];
        OY += pos[i][1];
        OZ += pos[i][2];
    }
    OX /= 8;
    OY /= 8;
    OZ /= 8;
    for(int i=0;i<n;i++){
        tmp[i][0] = pos[i][0]-OX;
        tmp[i][1] = pos[i][1]-OY;
        tmp[i][2] = pos[i][2]-OZ;
    }
    vector<double> d(n);
    for(int i=0;i<n;i++){
        d[i] = dist(tmp[i]);
    }
    sort(d.begin(), d.end());
    if(abs(d.back() - d.front()) > EPS) return false;
    for(int i=0;i<n;i++){
        d.clear();
        for(int j=0;j<n;j++){
            if(i==j) continue;
            d.emplace_back(dist(tmp[i], tmp[j]));
        }
        sort(d.begin(),d.end());
        if(abs(d[2]-d[0])>EPS) return false;
    }
    return true;
}

bool rec(int i){
    if(i == n){
        if(isCube()){
            cout << "YES\n";
            for(int j=0;j<n;j++){
                for(int k=0;k<3;k++){
                    cout << pos[j][k]/8 << " \n"[k==2];
                }
            }
            return true;
        }else{
            return false;
        }
    }
    sort(pos[i].begin(),pos[i].end());
    while(1){
        bool ok = true;
        for(int j=0;j<i;j++){
            if(pos[j]==pos[i]) ok = false;
        }
        if(ok && rec(i+1)) return true;
        if(!next_permutation(pos[i].begin(),pos[i].end())){
            break;
        }
    }
    return false;
}

int solve(){
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin >> pos[i][j];
            pos[i][j] *= 8;
        }
    }
    if(!rec(1)){
        cout << "NO\n";
    }
    return 0;
}

int main(){
    solve();
    return 0;
}

http://codeforces.com/problemset/submission/465/74613974

この条件で十分条件と言えるのかは証明していません...
あと距離の計算を二乗距離のままで止めておくと誤差を気にしないでよくなるので次回からそうしたい。

2020-02-14

AOJ 0552 Exposition

AOJ 二分探索

問題

JOI 2010 本戦の問題

問題リンク：AOJ 0552

解法

かなり難しかった。

そのままの座標だとマンハッタン距離が扱いずらいので45度回転をする。すると、例えば $s=x+y,t=x-y$ と変換すれば距離は $\max(|s_i-s_j|, |t_i-t_j|)$ で求められるようになる。点群の最遠点対の距離は $\max(s_{\rm max}-s_{\rm min}, t_{\rm max}-t_{\rm min})$ で求まり、s,tで分離して考えられるので扱いやすくなる。

最大値の最小化なので二分探索が適用できないか考える。距離x以下で2つのグループに分けられるかを判定できればよい。このときボトルネックとなるのは全体の $s_{\rm max},s_{\rm min}, t_{\rm max},t_{\rm min}$ なのでこれらを基準にすると、例えば $s_i-s_{\rm min} > x$ となる点iは絶対に $s_{\rm min}$ の点と同じグループにできないことがわかる。これをそれぞれについて判定すると点を9つの領域に分類できる。

真ん中の列、行にある点は後で都合がいいように割り振れるので無視する。問題になるのは四隅の領域で、いずれかの対角の領域(図の0,3のペアと1,2のペア)にある点の個数が0でないと2つのグループに分けられない。

f:id:NOSS:20200215104917p:plain — 右下の黒い点は赤青どちらにも属せない

逆にある対角の点の個数が0ならば分けられるのでこれで判定を行える。

一回の判定にかかる計算量は $O(N)$ なので全体の計算量は $O(N \log (|X|+|Y|))$ となる。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1<<30;

void chmin(int &a, int b){a=min(a,b);}
void chmax(int &a, int b){a=max(a,b);}

int n, smax = -INF, smin = INF, tmax = -INF, tmin = INF;
vector<int> s, t;

// 距離x以下で分割できるか
bool check(int x){
    vector<int> gs(n,2), gt(n,2);
    // 45度回転した平面で9つの領域に分類
    for(int i=0;i<n;i++){
        if(min(abs(s[i]-smin),abs(s[i]-smax)) > x) return false;
        else if(abs(s[i]-smax) > x) gs[i] = 0;
        else if(abs(s[i]-smin) > x) gs[i] = 1;
    }
    for(int i=0;i<n;i++){
        if(min(abs(t[i]-tmin),abs(t[i]-tmax)) > x) return false;
        else if(abs(t[i]-tmax) > x) gt[i] = 0;
        else if(abs(t[i]-tmin) > x) gt[i] = 1;
    }
    int cnt[4]{};
    for(int i=0;i<n;i++){
        if(gs[i]==0 && gt[i]==0) cnt[0]++;
        if(gs[i]==0 && gt[i]==1) cnt[1]++;
        if(gs[i]==1 && gt[i]==0) cnt[2]++;
        if(gs[i]==1 && gt[i]==1) cnt[3]++;
    }
    return (cnt[0]+cnt[3]==0 || cnt[1]+cnt[2]==0);
}

int main(){
    cin >> n;
    s.resize(n);
    t.resize(n);
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        s[i] = x+y;
        t[i] = x-y;
        chmax(smax, s[i]); chmin(smin, s[i]);
        chmax(tmax, t[i]); chmin(tmin, t[i]);
    }
    int ok = 1e6, ng = 0;
    while(abs(ok-ng)>1){
        int mid = (ok+ng)/2;
        if(check(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok << endl;
    return 0;
}

2019-11-22

ICPC 2019 Asia Yokohama Regional 参加記

ICPC 参加記

チームEldoradoとしてICPC 2019 Asia Yokohama Regionalに参加しました。

チームメンバーの参加記

一日目

開場です pic.twitter.com/334eKJssY4
— NOSS (@noss46) 2019年11月16日

開場とともに入場。
あらゆる案内や受付が英語で「本当に英語しか使えない」ことを悟って内心動揺していました。大会中はほとんど「オーケー」と「サンキュー」くらいしか発言していませんでしたが...

チーム紹介文やコンテストのマニュアルを読んでいるうちに開会式が始まってリハーサルになりました。

リハーサル

nicklawさんが環境構築、Aをmhrb君、Bを私が読みます。

Aは自明らしいのでWAやREを出したりしてmhrb君がジャッジの確認をしていました。

Bは~~問題文が不明瞭で~~僕の英語力が足りず読解した内容とサンプルが合わねえ、となっていました。
チームメンバーに相談すると単語の定義をclarで質問することになり、その間暇なので多分この解釈だろうと信じて実装していました。無事解釈が合っていたので提出するとWRONG ANSWER。明らかにやばい部分があるので直すとCORRECT。

Cを読むと明らかに解いたことがある問題なのですが肝心の解法が思い出せず。つらい。

このままリハーサルは終了しました。

Dの概要を聞くと脳内ACしたので、よし後はライブラリを写すだけだね、と該当のコードを確認すると...なんとJavaで書かれていることが発覚(メンバーは全員C++使い)。OBの先輩からいただいたライブラリはC++とJavaが混在していた...

【悲報】ICPC大会前日のリハーサルでライブラリの致命的な欠陥を発見
— NOSS (@noss46) 2019年11月16日

チーム紹介

辞書順で後ろから順に行うことになり「Yokohama National University」の私たちがトップバッターに。なんの準備もしていなかったので簡単な自己紹介をして終了。他のチームは結構凝ったものがあったり、ネタに満載だったりとても面白かったです。

本番前夜

ライブラリが使えなくなったのでABC参加を断念しライブラリPDFを生成する作業をする。TeXの気持ちが分からず苦戦しました。

2日目

緊張で目覚ましより早く起きてしまう。集合時間より早く着いたもののやることもないので会場付近を散歩する。ここで幾何ライブラリを忘れてきたことに気づく。~~まあ解けないしいいか...~~

無事に参加登録を終えて初動の確認をしていると、9:24頃に突然「1分後にコンテストを開始します！5分前倒しです！」とアナウンスが入る。
会場も少しざわく。さっきトイレに行った人が居たけど大丈夫か？と思いつつもコンテストが開始した。

コンテスト

リハーサル通りnicklawさんが環境構築、Aをmhrb君、Bを私が担当。

Bの問題文の単語難しいと思っていたらmhrb君がAを実装しながら詰めたいそうなのでお願いする。

Bは各マス目の高さを最小化する問題とわかったので、高さが決まったマスから高さ順にBFS的に決定して行けばよさそう。nicklawさんに解法を確認すると同意が得られたので実装方針を固めておく。

mhrb君がAを通す(0:22)。交代して私がBを実装する。提出すると難なく通る(0:41)。

ここから分担して解けそうな問題を探す。

C ぱっと思いつかない。
D 明らかにやばい見た目をしているので飛ばす。
E おそらく2乗DPだけど計算量が落ちない。
G 01のTrie木を書いたけどそこから進まず。

mhrb君がFをやってみたいそうなのでお願いする。

順位表を見るとHが解かれているのでHを考察する。Hはかっこ列を末尾に追加/削除する問題で、いつもの通り(で+1、)で-1するのを前から順にやるとかっこ列の数え上げができる。あとは削除に対応するためにstackで状態を復元できるようにすればいけそう。

mhrb君のFの考察が破綻してしまったらしいので交代してHを実装する。実装途中で考察漏れが発覚するもなんとかカバー。サンプルが合ったので提出するとAC！(1:48) この時点では18位ぐらいだったのでそこそこのペース。

実装していた間に考察してもらった他の問題の概要を聞く。

I 閉路は潰せるので木の問題になる。けど計算量が落とせない。
J やばい幾何。
K どこから取り組めばいいのかすらわからない。

順位表をみるとEが解かれ始めているので考察する。持つべき情報を持とうとするとどうしても3乗になってしまうので難しい。

あれこれ考えているとmhrb君が「二部グラフで解ける」というので概要を聞くと本当に解けているので感謝する。あとはDPの漸化式を立てるだけでこの手のDPは解いたことがあるのでOK。私が実装に入る。

後ろで2人がおにぎりを食べていたので「早く実装をACしておにぎり食べたいなあ」と思いながら実装していた。このときかなり疲れていて実装がボロボロだったがmhrb君がペアプロでミスを指摘してくれたので助かった。サンプルを試すと一発で全部合うので嬉しくなる。提出すると...AC!(3:22)

昼食を食べながら次に解けそうな問題を考えるとGかIあたりだったのでGを考察する。

長さ高々16なのでやるとしたらbitDPだろうなあと思いつつも漸化式が立てられずそのままコンテスト終了。

結果はABEHの4完でした。

閉会式

ICPC運営の方やスポンサーの方のお話を聞ききました。解説は全体的に賢そうでA,B,Hくらいしか理解出来ず。

ICPC恒例のYes/Noはすごい盛り上がってYesのときはみんなで拍手をして称えるのがいい文化だなと思いました。北京大学が最後Dを通していたのは激熱だった。

Eldoradoの順位は23位でした。

懇親会

全体での記念撮影と企業賞の発表があったあと懇親会がスタート。ご飯を食べたり、企業ブースをまわって展示をみたりゲームで勝ってカバンをいただいたりクイズを解いたりしていました。 5hコンテストをした後に企業ブースをまわるのが体力的に厳しかったのでもっと体力をつけたいなと思いました。

三日目

企業見学で私のグループはNEC->しながわ水族館->Huaweiの順に見学しました。

NEC
企業説明をしてくださった方々が競プロerの笑いを誘うのが上手くてさすがだなあと思いました。内容もとても参考になりました。用意していただいた昼食が非常に豪華でNEC本社ビルの眺望の良さも相まってとてもよかったです。

昼食情報です pic.twitter.com/CV5EGfZv6m
— NOSS (@noss46) 2019年11月18日

しながわ水族館
岩から湧き出る水をみて「フローだ！」と言っていたり、ペンギンの恋人関係図をみて浮気を切る最小カットっぽいと言ったり、イルカショークイズで盛り上がっている集団がいたり。なんだかんだ楽しめました。

pic.twitter.com/Zo5DalWnYm
— NOSS (@noss46) 2019年11月18日

Huawei
すべての技術を自分達で作り上げてやろうというすごい熱意とパワーを感じました。3DCGの話がとても興味深かったです。

感想

非常に楽しいICPCでした。去年に国内予選落ちをしてから臥薪嘗胆で精進をしていたので、今年のアジア地区で4完できたのはちゃんと成長できたんだなとちょっと安堵しています。とはいえ満足しているわけではないので来年は今回の成績を超えられるようにがんばります。

2019-10-15

ハル研究所プログラミングコンテスト2019 参加記

参加記

ハル研プロコン2019に参加しました！
昨年に続き2回目の参加です。

2019-09-24

AtCoder黄色になるまでにやったこと

AtCoder

2019/9/15 AtCoder Beginner Contest 141で黄色になりました。
黄色になるまでにどんなことをしたのか書きたいと思います。

2019-09-22

ACPC2019 参加記

参加記 AOJ

9/18-9/20に行われた会津大学競技プログラミング合宿2019に参加してきました。

2019-09-16

JAG夏合宿2019 Day2,Day3 参加記

ICPC 参加記

JAG夏合宿2019にチームEldoradoとして参加しました。
チームメンバーは、ニクロー、まほろば、NOSS

Day1の記事はこちら

Day2

朝が早いのでちょっと眠たい。同室みんなで朝食を食べに行きました。

コンテスト

コンテストリンク:https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day2

まずBを読むと明らかにフローなので始点と終点が複数のフローで解けるのかなと思う。
まほろば君とAについて話して方針が固まったので実装をやってもらう。

(00:20) A AC

いまのところ解けている問題がないのでとりあえずBの最大流を蟻本を写経して投げる、がWA。
よく考えると致命的なケースがみつかったので断念する。ちゃんと考察をするべきですね…

順位表を見るとEが大量に解かれているのでメンバーに読んでもらう。やばそうな見た目をしているがよく読むとギャグらしい。

(00:57) E AC

Dの概要を聞く。生存である集合の部分集合に死亡であるものがあるとき不可能なのでこの場合を除く。なるべく小さい死亡の集合を見つけたいので1つずつbitを下ろして確認すればよさそう。

(01:19) D AC

ここから険しい時間が続く。

F 一般マッチングのライブラリがあれば解ける！持っていません...
G 直線上の問題ならABCの問題にあったけど円環上は？
J お互いに相手の根本を削るのが最善なので数列の最小値が問題になる。n乗和の式で表せるところまで進めたけどこれは求められないな...

順位表を眺めるとIが比較的通されているのでよく考察してみる。きちんと場合分けをすると割とキレイな性質があることがわかったのでこれは解けそうとなる。メンバーでよく確認しながら実装をする。

(04:19) I AC

一発ACできたときは嬉しくなった。

このままコンテスト終了。結果はADEIの4完でした。

感想・反省

きちんと考察してから提出しよう。
ライブラリは重要。

懇親会

開始直前まで昼寝をしていて同室の皆さんに起こしてもらった。会場に大量のカツサンドが積まれていて面白かった。

お話してくださった皆さんありがとうございました。

ABC

黄色への変色がかかっていたので懇親会から引きあげて参加する。

そしてついに黄色に...!

ついに黄色になれました！！！ pic.twitter.com/ygGiXaZrA1
— NOSS@JAG夏合宿 (@noss46) September 15, 2019

同室のyamadさんに「あ、黄色になりました」と言ったらすごく驚かれました。懇親会で何人かから今日で黄色ですね！と言われていたのでちゃんと変色できてよかった。

Day3

シーツ畳み込みのプロ・畳小宮になる。

コンテスト

https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day3

Aの概要を聞くと奇数に偶数を足していけば良さそう、となって最終的に奇数の個数の偶奇にで場合分けすればよいことがわかった。

(00:15) A AC

Cを読む。どの区間を最後に残すかが重要そう。ニクローさんと話すと最も区間が重複しているところがネックになって重複してる分だけ往復が必要だという結論に至った。あとは重複している区間のうち最も端に近いのを残したいということになったので本当にそれが達成可能なのか正当性を議論した。最終的に達成不可能にしようとすると重複の最大性に矛盾するということになったので正当性のある貪欲を書く。

(01:26) C AC

Bは最初の大小関係がずっと変化しないことがわかる。クエリをセグ木に乗せられるか？という話になったけどどうやっても割り算が無理そうなのでだめになった。なにもわからないので後ろの問題を読んでいるとニクローさんが解けたらしいので実装をお願いする。(すごい)

(02:44) B AC

Eがフローに見えたりJのパズルを解いてたりしたらコンテストが終了してしまった。結果はABCの3完。

全体の感想

上位チームの人々との圧倒的な力の差というのを感じました。いままで習得がおっくうになっていた技術をもれなく要求されたので、やはりやらなければならないなという意識が生まれました。とても刺激的な合宿で参加してよかったと思います。

運営のJAGの皆さんありがとうございました！

NOSSの雑記

主に競プロでやったことを書きます。

Codeforces #265 Div1 B. Restore Cube

問題

解法

Code

コメント

AOJ 0552 Exposition

問題

解法

Code

ICPC 2019 Asia Yokohama Regional 参加記

一日目

リハーサル

チーム紹介

本番前夜

2日目

コンテスト

閉会式

懇親会

三日目

感想

ハル研究所プログラミングコンテスト2019 参加記

AtCoder黄色になるまでにやったこと

ACPC2019 参加記

JAG夏合宿2019 Day2,Day3 参加記

Day2

コンテスト

感想・反省

懇親会

ABC

Day3

コンテスト

全体の感想