2016-02-03

DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 B問題ディスコ社内ツアー

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。

問題

B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 | AtCoder
面白さがそれぞれA_iの部屋が環状にならんでいて、面白さが広義単調増加となるように部屋を回る。
1番目の部屋を出発点としたとき何周する必要があるかをもとめる。
みたいな問題

解法

実際にぐるぐるまわる単純なシュミレーションを書くとO(N^2)になり部分点の20点が得られます。

満点解法もぐるぐるまわるシュミレーションなのですが、面白さが等しい部屋をまとめて管理することで高速化でき、O(N)で解くことができます。

まわる部屋はかならず広義単調増加になっているため、面白さが等しい部屋は必ず続けて通ることになります(例 : 2 1 3 2 2 2 -> 1 2 2 2 2 3 )
これに注目し、キーを「面白さ」、値を「"その面白さである部屋のindex"をもつvector」のmapを使用して、面白さが等しい部屋をまとめて管理します。
このmapを利用してシュミレーションを行います。

基本的にはmapのキーが小さい順に舐めていくだけなのですが、今いる部屋の更新の際に工夫が必要になります。
説明を簡単にするため、「map[i]」と書いたときのiを、mapのキーの中でi番目に小さいものとします。
また、map[i]の値(vector)は昇順にソートされており、大きい値が格納されている方を右と呼ぶことにします。

現在いる部屋のindexをnowとし、はじめは-1に初期化しておきます。
すると次に向かう部屋は「map[0]の値(vector)のうち、nowのindexから右にたどっていき、はじめに見つかったもの(右端にくると左端にローテーションする)」となります。
その後、向かった部屋と同じ面白さの部屋を全てまわることになります。
つまり今いる部屋のindexをnowとすると、以下のようにnowの値を更新していくことができます。

next = upper_bound( map[i].begin(),map[i].end() , now ) - map[i].begin();
now = map[i][  (next - 1 + map[i].size()) % map[i].size()  ]

now==1の時の更新を図にするとこんな感じで、この例ではnowの値は1から0に更新されます。
f:id:Yazaten:20160203074018p:plain

よく読むとわかるのですが、「(next - 1 + map[i].size()) % map[i].size()」は基本的にはnext-1の結果と一致し、next==0のときにのみ「map[i].size()-1」となります。

面白さが等しい部屋の左端と右端だけを持つと今いる部屋の更新がうまく行かず、例えば「2 1 3 2 2 2」というケースに対して3と出力してしまう(正解は2)ので注意が必要です。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int main(){
    int n;
    cin>>n;
    vector<int> vec(n);
    map<int,vector<int>> mp;
    rep(i,n){
        cin>>vec[i];
        mp[vec[i]].pb(i);
    }
    
    int count=1,now=-1;
    for(auto itr = mp.begin();itr!=mp.end();itr++){
        vector<int> sec = itr->second;
        sort(all(sec));
        
        int p = lower_bound(all(sec),now)-sec.begin();
        if(  now>sec[  (p+sec.size()-1)%sec.size()  ]  )count++;
        now = sec[  (p+sec.size()-1)%sec.size()  ];
        
    }
    if(now == 0)count--;
    cout<<count<<endl;
}

2015-12-13

CODE FESTIVAL 2015 参加記まとめ

CODE FESTIVAL 2015 の参加記まとめが少し寂しかったので、僕が観測できた範囲の参加記をメモしておきます。

togetter版 -> CODE FESTIVAL 2015 参加記まとめ - Togetterまとめ

参加記

投稿日が新しい順に並んでいます。

2015-12-04

CODE FESTIVAL 2015 参加記

CODE FESTIVALの参加記です。

前日

自費前泊したかったが試験があったので断念
当日遅刻が怖いので21時くらいに寝ました。

1日目

3時過ぎに起きる

今起きたからこどふぇす当日入り余裕っぽい
— やざてん (@Yazaten) November 13, 2015

新幹線の切符の予約予約はしていなかったので適当な時間の新幹線に乗る。
新幹線の中で各位の現地入りツイートを見ながらワクワク。

チョット早めに会場につく。
お馴染みの音楽が流れていて、「今年もこどふぇすに来たんだなぁ」という気持ちになりました。あの音楽配布はされないのかなぁ

色々な人との再開を楽しんでたらコンテスト開始時間になりました。
回線の不調で開始が少し遅れたので ichigo_o_re さんとDDRをしていました。その後は特に何事もなく無事開催。
ABCDEを解いて、FGHわからんぞ〜といってる間にコンテストは終了。結果は110位でした。
パーカー圏内ではあるけど、できれば6完して頭一つ抜け出したかった。精進案件。

今年はご飯が立食では無くなっていたので慌ただしくて少し残念でした。
お寿司を貰ってトークライブへ。
トークライブフェイズでは、けんしょーさん、秋葉さんを見に行きました。

その後は去年特に楽しかったイベント、エキシビションマッチを見ました。
尊敬するプロ達のコーディングが見れて最高！

最後に2日目のチーム対抗リレーのチーム決めをして解散しました。
チームで集まった際に eha さんがリュックにつけていたマムルのぬいぐるみに気付いてくれ、風来のシレンの話が出来たので嬉しかったです。

夜は眠かったのですぐに寝ました。

2日目

高層ホテルなのでエレベータがなかなか捕まらず集合にTLE、タクシーであさプロへ。
あさプロはEasyに参加したけれど、ハマりにハマって全完できず…

その後は様々なお弁当が準備されていたので天丼のお弁当を選びました( 焼肉にしておけばよかったと少し後悔した )。
急いでお弁当を食べ、chokudaiさん、りんごさんを見に行きました。
りんごさんクイズがぶっ飛んでいて非常に面白かったです。

↓参考

なんだこれｗｗ #code_festival pic.twitter.com/9A1HyrPOeH
— 180_shora_kujira16 (@shora_kujira16) November 15, 2015

競プロの世界的権威が出題する謎のクイズに翻弄される競プロのルーキーたち #code_festival
— Masaki⊣Hara (@qnighy) November 15, 2015

ここで残っているスタンプを埋めるとギリギリタンブラーが貰えることに気付いたので、急いでボードゲームや太鼓の達人などなどをやりました。
一緒に遊んで頂いた nikollsonさん、kyosさん、dohatsutsuさんありがとうございます楽しかったです♪

その後は最後のイベントチーム対抗リレー。
僕はE問題( 時計を回転させてあさプロに間に合わせるアレです )を担当したもののバグを埋め込んでしまい、「全探索してみれば」との助言を基にAC。チーム対抗っぽいぞ。

その他の問題にはあまり貢献出来ませんでしたが無事全完して2位。
余った時間で eha さんにゴミ箱の作り方を伝授するという貴重な体験をしていました。
参考 : 『広告チラシで折るゴミ箱』で便利＆エコ [家事] All About

表彰式では、全体的にはWAを結構出しつつも2位を取れたということでMVPならぬMVTをいただきました。
商品としてスウェットを頂いたので、CODE FESTIVALでもらった物だけで外出が可能になりました！！

最後の懇親会で強い方と話す機会があったのでCODE FESTIVALの話をしました。
強い人は実は退屈だったりはしないのかと気になっていたけれどどうやらそんなことはなく、コンテストよりも催しが楽しみだ！という強い人もいる( 誇張かもしれないけれど )らしく、改めて凄いイベントだなぁと思いました。

おわりに

CODE FESTIVAL は最高のプロコンイベントなので来年も参加したいのですが、今年の予選の順位を考えると難しいかもしれません…
ただ「来年も来るために精進するぞ！」と思えたので来年に向けて頑張ります！

CODE FESTIVALで貰ったものを眺めているけれど、僕は一体何のコンテストに参加したんだみたいな気持ちになる #code_festival pic.twitter.com/WDgKY0MytM
— やざてん (@Yazaten) November 15, 2015

2015-08-04

ラズパイでMeCab-Pythonを使えるようにした

このへん見ながらやった

MeCab: Yet Another Part-of-Speech and Morphological Analyzer

Ubuntu12.04にMeCabをインストールする - Pythonに萌えているか - Is Python Burning?

Ubuntu 10.04にMeCabをインストール - へにゃぺんて＠日々勉強のまとめ

2015-08-04

ラズパイの固定IPの設定をイジった

ルータを買い替えたので固定IPの設定をイジった。

/etc/network/interfaces を変更してもwebページが見れなかった

/etc/resolv.conf に書かれたDNSが古いルータの時のままになってて、書き換えたらできた

参考文献

固定IPアドレスの設定

2015-03-31

RUPC2015参加記

いまさらだけど2週間くらい前にあった立命館大学競技プログラミング合宿の参加記です

day1

集合30分前頃に立命館大学到着。同じバスに乗っていたにっしーさん、ぬまさん、向日葵さんと会場へ
お昼ごはんに学内のSUBWAYに行きたかったけど、時間がなかったので断念

時間になってもなかなか始まらず暇だったのでAOJをやる

しばらくすると、人も集まりチーム決め
div2とdiv1に別れてごにょごにょした結果、2人グループを作っていた @tsukasa_diary さんと T.Nagasawa さんに混ぜてもらって無事チーム決定
Yazaten, nagasawa, tsukasa の頭文字を取った、チームYanatsuで出場することに

Aを僕とNagasawaさんが読み、Bをツカサさんが読む
Bの方針が立ったそうなのでお願いしたけれど、誤読していたようで一回休み。
そのころにはAの方針が立ってたので若干時間がかかりながら1発AC
そしてB,Cの方針が立ったツカサさんに交代し、ツカサさんが立て続けにB,CをAC
順調だったのはここまで。

Nagasawaさんと二人でD (こころぴょんぴょんするやつ) 考えてたけどわからず
ツカサさんが時間ギリギリでdpでかける! と実装し始めたけど時間切れ
3完でした。

懇親会は隣の建物で立ち食い
ツボクラさんと喋ったり、怒髪君にD問題の解法を聞けたりして楽しかった〜

宿は去年と同じ漫画喫茶。

day2

10時からindeedについてのお話がある予定だったけど、流れたので10:30くらいからチーム決め。
今日は実力の近い人同士で組むことに

とりあえずdiv1とdiv2に別れてウダウダ言っていたら、@bn_naoyuki くんから何故かチーム決めクエリが飛んできた
緑コーダー or ABC3完できる人がその他の人の名札を引いて適当にチームを作成するやつをやった。今日は @pappagukun さんと TMさんと組むことに
s="pappagukun"+"Yazaten"+"TM" をソート後の部分文字列っぽいppttuzというチーム名で出場決定。

AをTMさん、Bを @pappagukunさん、Cを僕が読む作戦
テストケースが通らず紙デバックをしつつAをTMさんがAC
@pappagukun さんがBを書くも、バグらせてWA
交代してもらって紙コーディングが完了していたCをdp解で書いて提出→WA→区間ミスってる→WA→WA→WA→・・・・・
僕がダメなのでpappagukunさんに交代してBを書いて貰うが、思うように言っていないようだった
簡単な割にややこしくて辛そうだったので、代わりに書かせてもらってAC*1。

その後はDが2800周期っぽいけど自信ないからなんとなく手がつけたくなかった。Hは解法見えてて重いだけだったから一応解く
TMさんが辞書の問題を考えてくれてたけど結局時間切れ。

2完でした。

コンテスト後は2週間ぶりくらいに再会した、くに君と話しながら駅まで移動。くにくんは懇親会不参加なので駅でお別れ

懇親会では@evimaプロやにっしープロ、@Mi_Sawaプロ、@Darseinプロに囲まれプロプロ。
競プロのこともそうじゃないことも色々話せた
SRMの英語が読めないならば沢山やって慣れるのが良いらしい。

あと、初めてきゅうりと話せた。「黄色いアイコンのヤツ」と認識してくれていたらしくちょっとうれしい

その後はMi_Sawaプロと、謎の道譲り合いをしたり、銭湯に行って怒髪君と四畳半神話大系の話とかをして楽しかった

この日の宿も漫画喫茶。

day3

集合が9~10時なので早起きして会場に到着。
会津のdiv1勢と立命のdiv2勢で2人組を作り、余った人は2人組に入れてもらう。
しかし「参加者 mod 3 == 2」だったため、会津のUraOmote(間違ってたらごめんなさい)さんと2人チームになってしまう。不安。

コンテストが始まると僕がAを、ペアがBを読む。
JIS配列 && 非IDE && テキストエディタがemacs　という普段と大きく違う環境に戸惑いつつ、時間をかけてAをACしてペアに交代
横から見てるとBは結構実装が重そうだったけど、すんなりBをACしてもらう
Cを読んだけど、重そうだしきゅうりチームが解いてなかったしでDに移る。

出発地点、落し物を落とした地点、届け先のノード以外を意識して通る必要がない。
各地点間の最短距離だけを事前に計算しておく。( O( (1+k*2)*ElogV )らしい )
その後13地点を回る順番を枝刈り全探索した。
もしかしたら間に合わないかもなぁと思いながらコーディングするのはちょっとつらかった。

なんとか書き終えたのがコンテスト終了数分前で、デバッグ出力とかを消してる間にコンテスト終了。
終了後に提出したけどTLEをもらう。解法は枝刈り全探索の代わりにbitDPをするらしい。

まとめ

立命館合宿に3日間参加したけれど、自明しかとくことができなくて悔しい。
自明をバグらずに解く力は少し上がったと感じたので、この調子でAOJ-ICPCを埋めようと思う。

ホテルでビュッフェ形式のやつを食べました

昼ごはん

鮭おにぎりを食べました

晩ごはん

ハッカソン先でお寿司やからあげを食べました