SRM699 Div1 Easy OthersXor
問題
TopCoder Statistics - Problem Statement
要はN個の数字があり入力x[i]にはi番目の数字以外の数字のxorを取ったものが入っている。
入力xを満たすようなN個の数字の組み合わせのうち合計が最小となるようなものを見つけその最小値を求める(ただしそのようなN個の数字がなければ-1を返す)
解説
神ペーパーさんに教えて貰った。
各bitを個別に考えることができる(xorをとってるので繰り上がり、繰り下がりが発生することはない).
そして、数列の要素のうちiビット目が1のものがいくつあるかをそれぞれのbitについて確かめればいい。
それぞれのbitについて1がk個でxの条件を成立できるかを確かめ、成立できるkのうち最小のものを求めればよく、k個で可能かどうかは
kが奇数 かつ x[i]%2=1 なら i番目の数字の見ているビットは0(自分以外が奇数個)
kが偶数 かつ x[i]%2=1 なら i番目の数字の見ているビットは1(自分以外は偶数個)
(あとkが偶数/奇数で x[i]%2==0のときも考える)
としていって確かめればよい
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) typedef long long ll; const int BITS = 30; class OthersXor{ public: long long minSum(vector<int> x){ int N = x.size(); ll sum=0; vector<vector<int>> ans(N,vector<int>(30,-1)); vector<int> cnt(BITS); rep(i,BITS){ // see i-bit bool f=false; for(int num=0;num<=N;num++){ // num個にできる? int ones = 0; int undefine = 0; for(int j=0;j<N;j++){ if(x[j]==-1){ undefine++; continue; } // x[j]をみる int b = (x[j]>>i) & 1; if(num%2==1 and b==0){ ones++; }else if(num%2==0 and b==1){ ones++; } } if(ones > num) continue; if(undefine < num-ones) continue; for(int j=0;j<N;j++){ if(x[j]==-1) ones++; if(ones == num) break; } f=true; cnt[i] = num; break; } if(!f) return -1; } for(int i=0;i<BITS;i++){ ll t = 1 << i; sum += t * cnt[i]; } return sum; } };
感想
はじめてのDiv1だったから1問くらい解きたかった....
1問くらい解けないと緑に戻ってしまうだろうし怖い...
vim-autocloseで括弧入力直後にスペースを入力した時...
括弧の補完プラグインTownk/vim-autoclose(https://github.com/Townk/vim-autoclose)において、補完対象の括弧を入力直後にスペースが2つ入力されていた。
つまり
for(<ここでスペースを入力>
とした場合に、
for(__)
(_はスペース)
となってしまった。
これの解決策はここに記してあった。
github.com
つまり
let g:AutoCloseExpandSpace=0
としたら正常に動作した
技術室奥プログラミングコンテスト#2 C問題 有給休暇を解いたんだよ...
解法
二分探索で長さL(実際のコード中では"mid")の連続した1を作るか確認していき、作れる最長の長さを出力すればいい。
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(i,n) for(int i=0;i<n;i++) #define INF INT_MAX/3 #define LINF LLONG_MAX/3 #define MP make_pair #define PB push_back #define EB emplace_back #define ALL(v) (v).begin(),(v).end() #define debug(x) cout<<#x<<":"<<x<<endl #define debug2(x,y) cout<<#x<<","<<#y":"<<x<<","<<y<<endl template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; #define MAXN 100001 int main(){ int N,K; int H[MAXN]; cin>>N>>K; rep(i,N) cin>>H[i]; int sum[MAXN+10] = {}; // sum[i] : [0,i)の0の個数 int cnt=0; for(int i=0;i<=N;i++){ sum[i] = cnt; if(!H[i]) cnt++; } int ul=0,ur=N+1; while(ur-ul>1){ int mid=(ul+ur)/2; // 長さmidの1の列を作れるか bool f=false; for(int i=0;i+mid<=N;i++){ int zero = sum[i+mid] - sum[i]; // [i,i+mid)に含まれる0の個数 if(zero<=K){ f=true; break; } } if(f){ ul = mid; }else{ ur = mid; } } cout << ul << endl; }
感想
コンテスト中には最初は左か右からK個全ての0を1に帰ればいいかと思ったけど
011000110 (K=3)の時とかに落ちてしまう。
そのあと二分探索を書いたけどWAが出てしまい解けなかった。とても悔しい。
コンテストの後りあん氏に聞いたらWAになってた原因は提出したコードで urの初期値を ur=Nとしていたので連続した1の個数がN個の列を作れる場合に落ちてしまっていた。
教訓 : 境界を求めるような二分探索での上界は必ず答えにならないような値にする必要がある。
自明なことではあるんだけど普通に気がつけなくて悲しい(o_o)
tmuxをビルドしたんだよっ
ubuntu15.10でtmuxをaptで入れてもバージョンが2.0とかしか入らないので最新版を使うためにはソースからビルドする必要がある。
cd /usr/loca/src sudo git clone https://github.com/tmux/tmux.git cd tmux sudo ./autogen.sh sudo ./configure --prefix=/usr/local sudo make sudo make install
としてビルドすることができた。
もしこれでエラーが出たら
sudo apt-get install libevent-dev
とかしてみるといいかもしれない。
感想
aptを使って入れられるのが一番楽なんだけどaptを使うと古いバージョンだったりするから結局最新版を使うためにはビルドする必要があるのちょっと面倒くさいよね(o_o)....
ICPC2016国内予選
ICPC2016国内予選に参加しました。
チームnikkuとして参加し、メンバーはすごプロ(@jken_ull),いしづ(@ish_774),僕でした。
結果としてはA,B,Cの3完で97位でした。
以下当日の流れです(時間はだいたい。記憶は結構あやふや)
16:30 -- 開始 --
とりあえず問題を印刷して、A僕,Bいしづ,Dすごぷろさんの担当。
10分くらいでA問題を通して僕はC問題を読む。
16:45
いしづがB問題を書き始めるがバグったらしく、苦戦している。僕はC問題考察終了、F問題を読み始める。
このあたりかもう少し後ですごぷろさんがD問題の考察を終了したらしく、E問題を考察を始めてる。
17:10くらい
いしづがB問題に詰まっているので画面の半分でいしづがコードとにらめっこし、もう半分ですごぷろさんがD問題を書き始める。
17:30 くらい？
とりあえずいしづがB問題を通した。すごぷろさんがD問題提出するが、WA. サンプルがあっているのでデバッグがつらそう。
F問題の考察にいしづが参加。
D問題がすぐには通らなさそうなので僕がCが問題を書くがサンプルが合わない。
合わないサンプルの値が小さいので手で確認したらバグが判明して書き直す。
最大ケースを解くのに十秒くらいかかったので焦ったがとりあえずサンプルが合うので提出。AC。
すごぷろさんはD問題のデバッグ。
この後、僕はF問題の考察を諦める。G問題を読んでみる。
G問題、問題の意味がよく分からず放棄。F問題の考察に戻る。
18:30 くらい？(たぶんもう少し後)
すごぷろさんがD問題のデバッグ続けるよりE問題書いたほうが良いと判断。E問題を書き始める。
いしづはF問題の考察を続行。
僕はD問題のデバッグに移る。
19:10
Eの問題のサンプルが合わないらしい。F問題は考察が出来たとしても実装が間に合わないのでいしづがD問題のデバッグに参加。
19:28
いしづがD問題のデバッグでおかしな挙動を見つけるが、間に合わず。。。。
19:30 --終了--
感想
今回のコンテストでは思考が必要な問題をすべてすごプロさんにまかせてしまい申し訳なかった。
ぼくがD問題くらいまで担当できるようになりたい。
TCO2016Round2C Easy BearBall
TCO2016Round2C Easy BearBallの解き方
問題
N個の点がある。
N個の点から始点と終点を選ぶ方法はN*(N-1)通り。
この全ての始点と終点の組み合わせについて、始点から終点に向かってボールを飛ばしたい。
ただし、点1と点2の間に点が存在しなければコスト1で点1から点2に到達できる。
点1と点2の間に点3が存在する場合、点1から点2に直接到達することは出来ないので別の点を経由する必要がある。
全ての始点と終点の組み合わせについて、始点から終点にボールを飛ばすのにかかるコストの合計の最小値はいくつか?
解法
始点を1つ選びその始点からコスト1で到達できる点の個数を求める。コスト1で到達出来ない点はコスト2となる。
これは直線状にいくつ点があろうとも直線状に無いコスト1で到達できる点を経由することでコスト2で終点に到達できるからである。
コスト1で到達できる点はベクトルを用いて、ベクトルが同じ方向ならば同一直線状にあると見なせる。(ベクトルの方向はベクトルのx,y方向の大きさをそれぞれの大きさの最大公約数で割れば異なるベクトルは区別、同じベクトルは同一視できる)
ただし、全ての点が一直線上にある場合は上の図の赤い点が経由出来ないので別に解く必要がある。
この場合、左からi番目の点が始点で始点より左にX個、始点より右にY個だった場合、自分より左の点に達するコストの合計は
自分より左側には
右側には
となるのでこれを直線上の全ての点に対して計算して合計すればよい。
コード
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <queue> #include <string> #include <climits> #include <set> using namespace std; typedef long long ll; typedef pair<int,int> pii; int gcd(int a,int b){ if(b>a) swap(a,b); if(b==0) return a; else return gcd(b,a%b); } class BearBall { public: int countThrows(vector <int> x, vector <int> y) { int N = x.size(); ll ans = 0; for(int i=0;i<N;i++){ set<pii> st; for(int j=0;j<N;j++){ if(i==j) continue; int vx = x[j]-x[i]; int vy = y[j]-y[i]; int m=gcd(abs(vx),abs(vy)); vx /= m; vy /= m; st.insert(make_pair(vx,vy)); } int n = st.size(); if(n==1){ ans=0; for(int i=0;i<N;i++){ int j=N-1-i; ans += i*(i+1)/2; ans += j*(j+1)/2; } return ans; } ans += n + (N-1-n)*2; } return ans; } };
感想
これを時間内に解けなかったのでRound2を通過することが出来なかった。悔しい。
コンテスト中にバグらせてしまい無限に時間が溶けてしまった。このくらいは解けるようになりたい。
ICPC2016国内模擬Bにでたんだよっ
6/12に行われたICPC2016国内模擬Bにで出ました。
チーム名はnikku,メンバーはすごぷろさん(@jken_ull),いしづ(@ish_774)、僕でした。
開始前(13:20) : 大岡山駅前で宗教勧誘を受けた。「聖書を読んだことありますか」って聞いてきたのでキリスト教とかそのあたりだとおもうけど日曜日って安息日のはずなのにスーツ着て勧誘ってどうなんだろうか?(どうでもいい)
計算機室到着(13:30) : 計算機室に到着。とりあえず、vim,zsh,tmuxの設定を始める。vimは.vimrcと.vimフォルダを別のPCからそのまま持ってきてホームディレクトリに置いたけどNeoBundleが動いてなくてうまくいかない。時間もないからXcodeを使うことにする。
コンテスト開始(14:00) : コンテスト開始。とりあえず方針としては僕といしづでCまで解いて、すごぷろさんにDから始めてもらう。僕がA、いしづB、すごぷろさんDが問題にとりかかる。
14:05 :
僕「あの、なんかテンパッてA問題理解できない」
いしづがB問題を書きはじめるが、いしづ久々にC++書くため大量のエラーを出す。なんかコンパイルが通らないらしくその間に僕の精神状況が回復。A問題を通す(xに関して0から100くらいまでの濃度を求めていき、濃度がCを超えた時が答え)。
~~~以降時間あやふやなので...~~~
僕はC問題にとりかかる。いしづはB問題をデバッグしてる。
僕「座標全探索だとO(40000*40000)になって無理っぽいんですけど。。。。座標圧縮なしでなんとかならないですかね」
(僕は座標圧縮を書いたことがない！！！)
すごぷろさん「座標圧縮で....X,Y軸の片方だけ圧縮すればいいかも」
すごプロさんがD問題書き始めた...と思ったらvimrcを書き始めた(o_o)....と思ってたらいつのまにかD問題を通す。
いしづがつらそうだったからB問題僕にチェンジ。
とりあえず書く。何回かバグったがいしづが横からチェックしててとりあえずサンプル通るから提出。
→ †WA †
は？サンプル通ってるが？いしづとデバッグしつづける。
コーナーケースも思いつかないのですごぷろさんに投げる。
すごぷろさんがB投げる。
→ †WA†
え？？？？
B問題を諦める。この時点で残り30分くらい。
僕がCが問題を書き始める。が、間に合わずに終了。
結果: A,Dの2完で84位？
感想
B問題で詰まったのがキツイ。本来ここは僕といしづでさくっと終わらせるべきだったのでとてもつらい。
すごぷろさんはE問題の考察が終わってたらしく、僕がC実装するよりEをすごぷろさんが実装したほうが間に合った可能性が高かったのでそのあたりうまくやりたい。
チーム戦はとても楽しい
