2019-11-06

AtCoder Beginner Contest 067 D - Fennec VS. Snuke

問題URL

解法

与えられるグラフは木なので、頂点 $1$ から頂点 $N$ までの経路は一通りです。
お互いにその経路上に自分の陣地を伸ばしていき、その後互いが塗ることのできる頂点に色を塗っていくことが互いにとって最適な戦略です。
まだその経路上の頂点が全て塗られてないうちに経路上の頂点以外を塗ってしまうと、相手が到達できる範囲を広げてしまうことになるからです。
これを幅優先探索を用いてシュミレーションすれば、答えを得ることができます。計算量は $O(N)$ です。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N;cin >> N;
    vector<vector<int>> E(N);
    for(int i = 0;i < N - 1;i++){
        int a,b;cin >> a>> b;
        a--,b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    vector<int> flag(N, -1);
    flag.front() = 0;
    flag.back() = 1;
    queue<int> que;
    que.push(0);
    que.push(N-1);
    while(!que.empty()){
        int q = que.front();
        que.pop();
        for(auto a : E[q]){
            if(flag[a] == -1){
                flag[a] = flag[q];
                que.push(a);
            }
        }
    }
    int F = 0,S = 0;
    for(auto a : flag){
        if(a == 0)F++;
        else S++;
        //cout<<a<<endl;
    }

    if(S < F){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
}

2019-11-05

AtCoder Beginner Contest 006 C - スフィンクスのなぞなぞ

問題URL

C - スフィンクスのなぞなぞ

解法

大人か老人か赤ちゃんのうちの一つを固定してしまえば、普通の鶴亀算になります。 $N \leqq 10^{5}$ であるので、 $10^{5}$ 回程度の計算で答えを得ることができます。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N,M;cin >> N >> M;
    for(int i = 0;i <= N;i++){
        if(i * 2 > M){
            break;
        }
        int remainAsi = M - 2 * i;
        int remainHito = N - i;
        if(remainAsi >= remainHito * 3 && remainHito - (remainAsi - remainHito * 3) >= 0){
            cout<<i<<" "<<remainHito - (remainAsi - remainHito * 3)<<" "<<(remainAsi - remainHito * 3)<<endl;;
            return 0;
        }
    }
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
}

2019-11-05

AtCoder Beginner Contest 080 D - Recording

問題URL

D - Recording

解法

$1 \leqq C \leqq 30$ と $C$ の種類がとても少ないので、これを利用することにします。
ある時間のテレビの利用状況は、 $32$ bit整数を一つ用いて、 $i$ 番目のbitが立っていたらチェンネル $i$ を録画するというように表現できます。
ここで、ある時間に、録画したいチャンネルを新たに加えることを考えます。
それは、ある時間の既に録画予定のチャンネルを表す整数を $X$ 、新たに録画したいチャンネルを $i$ として、bit演算を用いて、
$X \mid (1$ << $i)$ と表せます。
これは、ある時間のあるチャンネルを録画するクエリが複数来ることがないので、 $X + (1$ << $i)$ と加算の形で表してしまって問題ないです。
この操作を区間 $(s_i , t_i)$ について行います。
この操作は加算の形で表せるので、予め $0$ で初期化した長さ $10^{5}$ の数列に対し、クエリごとに区間 $(s_i, t_i)$ に $1$ << $c_i$ を加算します。
すべてのクエリを処理したあとに、数列の各要素について、立っているbitの数の中で最も多いものがこの問題の答えです。
区間加算にimos法を用いることによって、 $10^{5}$ 回程度の計算で答えを得ることができます。

ACしたコード

区間加算に遅延評価セグメントツリーを用いています。

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

class SegmentTreeRSQ {
private:
    int n;
    vector<LL> node, lazy;

public:
    void init(vector<LL> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, LL x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

   LL getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        LL vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        LL vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

int main(){
    int N,C;cin >> N >> C;
    SegmentTreeRSQ Seg;
    Seg.init(vector<LL>(1e5+1));
    for(int i = 0;i < N;i++){
        int s,t;cin >>s >> t;
        s--,t--;
        int c;cin >> c;
        Seg.add(s, t+1, (1 << c));
    }
    int ans = 0;
    for(int i = 0;i < 1e5+10;i++){
        ans = max((int)bitset<60>(Seg.getsum(i, i+1)).count(), ans);
    }
    cout<<ans<<endl;
}

2019-11-05

#procon30 参加記

はじめに

　もう終わってからだいぶ経っているのですが、第30回高専プロコンに自由部門で参加したので、思い出しながら参加記を書いてみようと思います。YoutubeのHack Uチャンネルに配信のアーカイブが残ってるので、興味があったらそっちも見てみてください。

なにをつくったか

　レゴで作品を作ると、センサーでそのブロックを認識して、3Dゲームに反映されてVRで遊べるというものです。 (プレゼン)
　4月にアイデア出しをしたのですが、それがかなり難航しまして、予選資料の提出の時期ギリギリに出たアイデアがこれでした。自由部門のリーダーによると、顧問からはこのアイデアについて反対を受けていたらしいのですが、無理矢理やることにしたらしいです。つよいなぁ。
　開発のタスクは、3Dゲーム、ブロックの情報を管理するサーバー、ブロックの認識、筐体制作って感じで分類することができて、僕はブロックの認識を担当しました。

ブロックの認識について

センサーにはRealSense D415を用いました。普通のカメラでは、写っている範囲のピクセルの色情報を取得できる(つまり写真が撮れる)と思うのですが、それに加えてピクセルそれぞれの距離情報も取得できるものです。
f:id:hamuhei4869:20191027201610p:plain
↑こんな感じで、深さを取得することができます。1280 × 720の大きさの深さ画像を30fpsで取得できるらしいです。すげえ。
　このセンサーを1台用いて上からブロックを認識しました。(はじめは複数台のセンサーを使おうと思っていたのですが、サンプルのコードが動かなくて真面目に原因の調査もせずにやめてしまいました...。) その深さ情報から3次元の座標が得られるので、ブロックが置かれる台の、どの辺りがどのくらいの深さかというのを特定してブロックを認識しました。
　ブロックの形状認識は9月始めの段階でできていて、そこからちょっとだらだらして、色の認識まで全部終わってマージされたのが10月に入った辺りだったかな。あんまり精度が出なくてやべえ〜〜〜って言いながら結局この辺りから最後まで精度は改善されませんでしたね。

-2日目(木曜日)

　台風19号の関係で、本戦に出場するメンバーだけ明日に輸送するぞ！となり。本当は土曜日に飛行機で行く予定だったのですが、金曜日に新幹線で行くことになりました。先輩たちが便の振替とかキャンセルをめっちゃ頑張っててすごかった。

台風19号緊急対策本部を設置 #procon30 pic.twitter.com/ut5hAuIMya
— たき∇ (@_nosita) 2019年10月10日

実際この判断は正しくて、土曜日は飛行機が飛びませんでした。

-1日目(金曜日)

　前述の通り、今日出発ということになっていました。13時くらいに東京駅集合で新大阪で乗り換えを挟んで鹿児島中央駅まで新幹線で、そこから在来線で1時間ちょっと揺られて都城へ。全部合わせて8時間くらい、結構な強行軍だと思うのですが、全部の区間で座ることができて意外と疲れはそんなにでした。車内ではちょっとしたタスクをやったりアニメを見たりしていました。

0日目(土曜日)

　高専プロコンは前日に受付を済ませる必要があるので、だいたいの高専が開催日の前日(つまり今日)に移動すると思うのですが、我々は昨日移動を済ませてしまったので、暇。という感じでした。(タスクも昨日電車の中で終わらせてしまっていたし)
　都城は快晴で、テレビで東京の様子を眺めたりしてました。お昼ご飯に親子丼を食べました。あと、髪を切ったりしましたね。床屋さん(美容院？区別がつきません...)の息子が都城高専に在籍しているらしく、学科の違いとか進学先とかの違いで話が弾みました。

1日目(日曜日)

　いよいよ高専プロコン開幕です。開会式を終え、デモブースへ向かいます。デモの審査は明日なのでそんなに忙しくないのですが、一般の人への展示を行いました。子供が結構遊んでくれて嬉しかった。

午後に入って認識の精度がめっちゃ落ちたのですが、おそらく太陽の光の当たり方によってRGBの値が大幅に変化したんじゃないかなあって思ってます。(深さの認識はうまくいっていたので)(この対策してないのガバガバすぎひんか...?)

その日の夜はエンカした人々とラーメンを食べました。おいしかった。

f:id:hamuhei4869:20191104220214j:plain

明日デモ審査があって、それの練習に付き合っていたのもあって、この日はかなり遅くに寝ました。眠かった...

2日目(月曜日)

　デモ審査は3回あって、1回目は少し認識に失敗してしまったのですが(でも、そこまで悪い雰囲気はなかった気がします)、2回目と3回目は自分らが満足のいくデモができたのではないかと思っています。
マニュアル審査(自分らが作ったマニュアルどおりに動くかどうかの審査)は時間が切れるまでは完璧に動いていたので、満点に近い数字がもらえたと思います。
正午辺りに、競技部門が決勝進出とか、優勝とか聞こえてきて、つえ〜ってなってた。

閉会式

　最優秀賞と企業賞 × 2をもらえました。

最高の笑顔の自由部門最優秀賞です!!!　#procon30 pic.twitter.com/FVxs6FGJKl
— 【公式】東京高専プロコンゼミ (@NITTC_SPC) 2019年10月14日

フォーラムエイト企業賞、アバナード企業賞自由部門受賞しました pic.twitter.com/Eo5HNWYY3u
— 【公式】東京高専プロコンゼミ (@NITTC_SPC) 2019年10月14日

また、学校としても東京高専は3部門制覇しました。

3冠だ!!!! #procon30
— 【公式】東京高専プロコンゼミ (@NITTC_SPC) 2019年10月14日

本当によかった、発表前はかなりブルーになっていたというか、こんな↓感じの負のツイートを垂れ流すやつになっていました。 f:id:hamuhei4869:20191104214802p:plain

発表順が競技部門 -> 課題部門 -> 自由部門だったので、競技と課題の受賞が確定した状態で自分らの発表を待つことになり、かなり辛かったです...。

この日の夜は打ち上げをしました。

高専プロコン焼き肉部門優勝です!!! #procon30 pic.twitter.com/Z1cuoqZgg4
— 【公式】東京高専プロコンゼミ (@NITTC_SPC) 2019年10月14日

3日目

何もしなかったのであんまり書くことがないです。shibh308さんと一緒に行動しました。

感想

　認識部分の開発は殆ど自分がやりました。タスクを分割することが難しかったので、当初の予定通りといえばそうなのですが、今思えばもうちょっと人に割り振ることもできたかなあって思います。(この辺りのマネジメントをするのが面倒だったというのが大きかったのかな。)

　チーム開発は楽しいなって感じました。今回の作品は動くフローがわかりやすく別れていたので、それぞれをそれぞれで開発してマージ、みたいなのはとても開発してる感じがあってよかった。
　今回このような結果を取れたのは、移動や宿泊の手配をしてくれた先輩方や、パンフレットやプレゼンの監督をしてくださった先生方等、多くの人に支えられたおかげだと思います。本当にありがとうございました。
　プロコンは今年で引退する予定なので、来年は開発に多分携わらないのですが、観戦しに行きます。
　#procon31で会いましょう！！！！

links

https://www.youtube.com/watch?v=wtwmTxAGg5E

https://www.youtube.com/watch?v=AawH3L6bfSU

https://www.youtube.com/watch?v=FOi_t-h9DXg&t=

https://www.youtube.com/watch?v=E2jj-3nB6XQ

https://www.youtube.com/watch?v=iyP65AwYa80&t=6s

https://www.youtube.com/watch?v=jVUPNk1f05Q&t=3130s

2019-02-11

情オリ本戦参加記

はじめに

こんにちは、はむへいです。情オリの本戦に参加してきたので、振り返っていきたいと思います。

一日目

エンカ

秋葉原で人々とエンカしました。

#JOI_ho pic.twitter.com/3cS86OtEGc
— zohe (@zohen0) 2019年2月9日

UDXのフードコート(？)みたいなところでラーメンを食べました。おいしかったです。

それからつくばエクスプレスでつくばへ

f:id:hamuhei4869:20190210222646p:plain

つくばについたら駅の中にあるファミマでお菓子を買いました。タイミング的にここで買っておくのが最適ムーブっぽい。

プラクティス

プラクティスがありました。難易度1~6くらいの過去問が何問かでました。ぼくはIOIOIに1時間かけたり、二分探索をバグらせて結局通せなかったりで、始まる前から冷えているとはまさにこのことかと。

人々が全完して談笑している中、ひとり黙々と問題に取り組むきもち！！小学校の給食の時間を思い出しました。

夕食会

バイキング形式のお食事でした。美味しかったです。
全員が全員の前で自己紹介をするイベントが生えて、自己紹介をしました。
塚本って名前のひとの自己紹介を聞き逃してしまったのが残念でした。(もしかして自己紹介してない?)

まあそんなこんなでバスにのって宿舎へ

独房生活

僕も念願の独房入りを果たしました！！やったね！！
f:id:hamuhei4869:20190210223124p:plain

なんだけど、そんなに喜んでいる暇もなくみんプロが始まりました。

コンテスト中に風呂に入るムーブを要求されていたので、風呂に入るタイミングを探りながら問題を解くことに。

Cで式変形をガバってACに50分くらいかけてしまった。なんかこれ簡単な問題らしくみんな僕より早く通してる、はめつ。

Dを読む、わからん。考えながら風呂へ。
f:id:hamuhei4869:20190210223413p:plain

入浴中に考えたけどやっぱりわからない。風呂から上がって終了、冷え。

コンテスト後にやがて君になるを摂取しました。爆死した後の精神にやさしい。

f:id:hamuhei4869:20190210223443p:plain

部屋にnaoppyと塚本が来ておはなしした。

二分探索がバグらないように、因幡めぐるちゃんにお祈りをした。 f:id:hamuhei4869:20190211130342p:plain
ねね

二日目

あさごはん

鮭もご飯も美味しかったです。

本戦

A

累積和をやってえいほい
20分くらいで通した。

B

むずかしい、ぱっと見じゃわからない。
ここで答えを二分探索しようってお気持ちが生える。
i枚を飾れる時はi-1枚飾ることは自明に可能なので、にぶたんできそう(?)
何枚飾れるかどうかを二分探索して、判定をO(N)でよしなにやってやると通る。因幡めぐるちゃんに感謝。ここまで1時間。

C

結局 'R'と'G'のときの小課題しか解いてません。これめっちゃバグらせて三時間半くらいの時にやっと通した。よわい。

D

わかりません。

E

この小課題1なんで見えなかったんだろう。よわい。

けっか

100-100-15-0-0 の215点でした。実力にしてはまあまあな点数ではないでしょうか。春合宿？しりません。

かんそう

春合宿に行けなかったことだけが悔やまれますが、TLの人々とエンカできて楽しかったです。ありがとうございました。

2018-12-09

日本情報オリンピック予選参加記

はじめに

この記事はプロコンゼミ(SPC同好会) その１ Advent Calendar 2018９日目の記事です。
最近になって急に冷え込んできましたね。季節を感じます。みなさんお体のほうは大丈夫でしょうか、僕は元気にやらせてもらってます。ありがとうございます。

さて、この記事では、12/9に行われた日本情報オリンピックに参加した話を私自身の結果を交えて書いていこうと思います。

参加記

A

目標のコインに到達するまでシュミュレートしてやればよいです。%7とか使うと楽かも

B

駒がおいてある/ないのフラグをもってシュミレーション

C

ループをN-1まで回して長さ2のsubstringを考えます。それが"OX","XO"ならループさせる変数に+1して答えにも+1

for(int a = 0;a < N-1;a++){
   string s = S.substr(a,2);
   if(s == "XO" || s == "OX"){
       a++;
       ans++;
   }
}

D

priority_queueで小さい順に処理、ある区画が沈む時に影響を与えるのはたかだかその両隣だけなので、島の端っこかどうかのフラグを持ってあげてなんかよしなに処理する。

E

セグ木を使いそう(ここで思考が止まる)
bit全探索をすると10点の部分点がもらえます。うれしいね。

F

N!とかnCrとかいろいろ試したけど無理だった。
next_permutationが使えると6点がもらえます。やったね。

おわりに

ということで、僕は総合で416点という結果でした。~~まあこの点数なら予選は通ったでしょう、やったね。:v:~~

各所でボーダーが400を超えると言われていて、通ってるかどうか心配です。こわい。

いろいろ調べたけど今年はいつボーダーが発表されるのかわからなかったので、知ってる人は教えてください。(去年は12/14だったっぽいので近日中にはありそう)