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をすごぷろさんが実装したほうが間に合った可能性が高かったのでそのあたりうまくやりたい。
チーム戦はとても楽しい
boost/any.cppなんだよっ
C++のboost/any.cppを使ってみた.
ドキュメントとかはなんかこの辺みた.
Chapter 3. Boost.Any - 1.61.0
boostjp.github.io
基本的には任意の型を代入できるような型(多分).
STLも代入できるし,自作クラスとかも代入できる.
つまりvector<boost::any>とかするといろんな型を収めた可変長配列が使用できそう...
値を取り出すときは, boost::any_cast<T>を用いて型をキャストする.
型を判定するには .type()がtype_info型を返すので x.type()==typeid(int)のように判定すれば良い...(はず)
以下試してみたコード
出力は
type int : 1
type char : A
type double : 3.3
type vector<int> : [10,20,30,]
type string : hoge
type fuga : 4
となる.
**追記
どうやらanyはC++1y,14ならstd::experimental::any,C++17ならstd::anyがあるらしい.
わざわざboostを使う必要は無いっぽい?
std::experimental::any - cppreference.com
texliveにjlistingを追加するんだよっ
texliveにjlisting.styを追加するときに少し困ったのでメモ
環境はubuntu15.04
tex-live2015
jlisting.styをどこかから落としてくる(なんかhttp://mytexpert.osdn.jp/index.php?Listingsのリンクが消えててそれ以外のところは散らばっているみたい)。
jlisting.styを
/usr/share/texlive/texmf-dist/tex/latex/listings
にコピーする。
sudo cd jlisting.sty /usr/share/texlive/texmf-dist/tex/latex/listings/
とか。
この後に
sudo mktexlsr
とするとパッケージにjlistingが追加される。
とここまで書いてあるサイトは多いけどこれだけだと動かなかった。
この時jlisting.styに読み込み権限がなかったので
sudo chmod +r jlisting.sty
とする必要があった。まあそりゃ読み込み権限がなければ読み込めないよねって話。
OpenTemplate.vimを作ったんだよっ!!!
タイトルどおりOpenTemplate.vimというvimプラグインを作ってみた。
まあ、作ろうと思った理由はテンプレートファイルをどうやって管理すればいいか分からなくてそれなら自分でプラグインを作ってみるかってなったから。
github.com
:OpenTemplate
とすれば拡張子に応じたテンプレートファイルを展開するようになっている。
これまでVimScriptを書いたことが殆ど無かったためtwitterでkoturnさんにいろいろ教えていただきながら書いた。
VimScriptについてappendとかgetとかの便利な使い方を知らなかったことがあった。意外とググっても調べにくかったりするし恐らく:helpを見るのがいいんだろうなぁって思ったけど英語だしね(._.)...........
autoload/に置いたファイルがいつ読み込まれるかとか分からなくて困ったりしたよ(o_o)!
verboseなんだよっ!!
vimを使っているときに想定しない折りたたみが起こっていたので
:echo foldmethod
を見ると
syntax
になっていた。
しかし、vimrcを確認すると
set foldmethod=marker
としている。おそらく何らかのプラグインがfoldmethodを書き換えていると推測。
しかし、なんのプラグインが書き換えているかは分からない。
:set runtimepath
を見ながらプラグインをいちいちチェックしていくのも面倒くさい。
そこでコマンドverboseを使用すると楽になる。
:verbose set foldmethod
とすると最後に変数foldmethodを書き換えたファイルを調べることができる。
つまり
:verbose set 変数名
で変数名が最後に書き換えられたファイルを調べられる。やったね!便利(._.)!!!
Haskellで文字と数値の変換したんだよっ
文字通りHaskellで文字(Char)と数値(Int)への変換方法を記しておく。
文字から数値へ
文字から数値にする1つの方法はordを使う方法。Data.Charをインポートする必要がある。
例では'a'を対応するasciiコード97に変換する。
Prelude> import Data.Char Prelude Data.Char> ord 'a' 97
別の方法はfromEnumを使用することである。
Prelude> fromEnum 'a' 97
ordとfromEnumの違いはIntを入力として与えた時である。
Prelude> import Data.Char Prelude Data.Char> fromEnum 100 100 Prelude Data.Char> ord 100 <interactive>:8:5: No instance for (Num Char) arising from the literal `100' Possible fix: add an instance declaration for (Num Char) In the first argument of `ord', namely `100' In the expression: ord 100 In an equation for `it': it = ord 100
このようにfromEnumにInt型の入力を与えるとそのまま帰ってくるがordに与えるとエラーとなる。
これはfromEnumはEnum型を入力として受け取るのにたいして,ordはChar型を入力に受け取るからである。下のようになっている。
Prelude Data.Char> :t fromEnum fromEnum :: Enum a => a -> Int Prelude Data.Char> :t ord ord :: Char -> Int
数値から文字へ
Int型からChar型への変換方法はtoEnumまたはchrを用いる。chrを使用するにはData.Charをインポートする必要がある。
それぞれ下のように使用する。asciiコード97を'a'に変換する。
Prelude> import Data.Char Prelude Data.Char> toEnum 97 :: Char 'a' Prelude Data.Char> chr 97 'a'
それぞれの型は次のようになっている
Prelude Data.Char> :t toEnum toEnum :: Enum a => Int -> a Prelude Data.Char> :t chr chr :: Int -> Char
上の通りtoEnumはIntからEnum aに変換する。そして変換先の型Charを::を用いて指定する必要がある。(これをしないとエラーになる)