RUPCに参加してきました
RUPC2017に参加してきたので参加記を...
~前日~
前日まで大学の友人と旅行をしていたので昼神温泉から中津川まで車に乗せていってもらい、中津川からはrian,葦くんとともに名古屋→京都に行く.
京都でちょっと観光してからホテルに向かおうということで伏見稲荷大社を訪れて山登りしたが僕の体力が底をついて途中リタイア
https://twitter.com/chakku_000/status/844120166547968000
京都駅で夕食を探して歩き回るも何も見つからずラーメン街へ
https://twitter.com/chakku_000/status/844131183550128128
その後瀬田駅まで行ってホテルへGO.
~1日目~
https://twitter.com/chakku_000/status/844385394791612417
余裕を持って?到着。立命館大学では卒業式をやっていたらしく大量に人がいた.
--コンテスト--
コンテストではらてさんと葦くんと同じチーム(Achalatte)になり、僕はまずAを担当したがRE.どうもAOJはC++でreutrn 0をしないとREになるらしく再提出→WA.バグらせた。なんか実装ミスってたので葦くんにコーディング譲ってその後にAC.次にEを担当し、DPだとはわかるが状態の持ち方が悪くてTLEしそうなのでらてさんにアドバイスもらって書く.最期見る所を間違えてサンプルとおらないがらてさんに教えてもらってAC.気がついたら葦くんがCをACしてた.
あとはらてさんが無双して全完.すごかった...
解説聞いたらAで無駄なことしまくってて泣いた.
~2日目~
---コンテスト---
rianと葦くんと「1回はこの三人ででたいよね」という話をしていたのでこの3人で組んだ.トイレから帰ってきたらチーム名がtaitekku_000で決まってて笑った.
最初A,B,Cをぱぱっと通していこうということでrianがAをサクッと通せば良くない?(結論)みたいな会話が行われrianがAを通す.僕はBを担当したが問題名が「GPAじゃんけん」で2週間後くらいにほんとにGPAじゃんけんすることを思い出して泣く(どうでもいい).Bを通した後にD,Eを読むが無理そうなので葦くんに渡してFをやる.Fは「壁が4つあって実装めんどいな...」って言ってたらりあんに「右下と左上だけでよくない」と言われてコーディング開始.最初dfsで書いてたらバグったのでbfsにしたらxとnxを間違えたり,bfsで訪れたところのチェックミスったりしてTLEやWAを連発しまくるもりあんにデバッグしてもらいながらAC.こういうミスをやめたい...
Fでコーディング時間を無限に奪ってしまったのが申し訳なかった...
---懇親会---
https://twitter.com/chakku_000/status/844858238000521216
https://twitter.com/chakku_000/status/844864270999285761
~3日目~
---コンテスト---
rian,葦と出てもよかったがせっかくなのでチーム決めに参加した.kawabysさんとRIKAさんとチームckrででた.
とりあえずRICAさんA,僕B,kawabysさんCで...ということになったが問題読んで僕とRICAさんがA,Bを交換.気がついたらkawabysさんがC問題を通しててプロかった.そして僕はAを書くがWAしてkawabysさんに手伝ってもらいながらデバッグするも通らないのでkawabysさんに投げる.D,Eがダイクストラとセグ木かなって話になりセグ木を書き始めるが計算量的に無理だと気が付きkawabysさんに相談すると遅延セグ木と言われたがそんなものは知らないのでDを書き始める.拡張ダイクストラは書き慣れていたのですんなりかけてAC(オーバーフローしたくせにすんなりとは...).RIKAさんがBをとおしてkawabysさんがAをとおして終わり.
Aを投げてしまったのが本当に申し訳なかった...
---帰路---
帰るときに京都によって昼飯を食べることに...四条に行ってみたが「ビジネス街やん！」ってなってぶらぶらしながら昼飯を探し適当にラーメン屋に行ってみる.濃口醤油というのが美味しかった.
京都駅に戻って「抹茶スイーツを食べないと...」という使命感にかられるもどこも人が多くて新幹線の時間に間に合わなさそう....なので諦めかけたら西尾の店に入って抹茶パフェを食べることができた...よかった...
https://twitter.com/chakku_000/status/845193664133414912
~~~~~~
RUPCとても楽しかったです！運営の方々ありがとうございました！
BCU30に参加したっぽい?
3/11にBattle Conference U30にプロコン枠で参加しました.
(行くぞ~)
浜松町から思ったよりも遠くてお昼ごはんの時間がなくなった...
のでコンビニを探したがなかなか見つけられなくて日の出駅?の近くでローソン?を見つけてお昼ごはんを買う.
https://twitter.com/chakku_000/status/840420558978211840
(会場到着)
なんか14:00までに入場かと思ってたら13:30らしいという噂もあって遅刻かとおもったけど入れた...
今回のプロコンは3人1チームで2時間で6問を解くことになりチームはmkiken氏,HORI氏とのチームになりました.
とりあえず問題を割り振り、なんか適当に順番に振り分ければいいかってなり
mkikenさん: A,D
僕 : B,E
HORIさん : C,F
と担当し分からなければお互いに教え合うことにしました.
(コンテスト開始)
とりあえず開始したらmkikenさんがAを通し次に僕がBのコーディングするがコピペしたあとにインデックス直しわすれて3WAだしてしまった....
ここでHORI氏がCに詰まっているのでmkikenさんがDをコーディングして通す.僕はEを考えるがO(N^2K^2)の解法しか思い浮かばない...
のでこれを提出してみると2ケースがTLEになるだけなので定数倍高速化で通せるのでは?と判断し高速化を始める.
一旦コーディングを交代してHORI氏がC問題を実装+AC.
Fはどうしようもないと判断しE問題を高速化(cin,coutをやめたりinline関数にしたり...).. 5回くらいTLEした後に残り5分でAC.
https://twitter.com/chakku_000/status/840469975970205696
(コンテスト終了)
(解説)
どうもEはやはりO(N^2K^2)は想定解でなかったらしい。C++が好きになった.
(起業ブースめぐり)
色々な起業から色々頂く.個人的にサイボウズさんのサイボウズキャンディーが面白かった.
あとabemaTVのシール!abemaTVでアニメ見まくってるので嬉しい
(懇親会)
なんかあちこちから🍣がすごいとの噂を聞いていたらすごかった.マグロの頭が置いてあった...
あとホットドック食べた.ソーセージ2本刺したらなんか嬉しくなった.
https://twitter.com/chakku_000/status/840498466438565888
(帰宅)
家に帰ったら誰もいなくて鍵も持ってないのでカラオケにいった.楽しかった
https://twitter.com/chakku_000/status/840529475800461312
https://twitter.com/chakku_000/status/840535699354861568
(___)
プロコンしてたのでバトルトークみれなかったのが残念だった...
いくつか見たかったのあった...
tmux-256colorを入れる
tmuxでdefault-terminalをtmux-256colorにしたかった.
しかしなんかubuntu16.04でtmux-256colorが入ってなかった.
https://github.com/tmux/tmux/blob/master/FAQ#L366-L373
これを試した見たけれど失敗....
ここでaptでncurses-termを入れてみたら/usr/share/terminfo/t/tmux-256colorができた！
Xmas Contestに参加したっぽい?
クリスマスイブ！
とくに予定もないのでXmas contestに参加しました。このコンテストはチームでの参加が許されていたので、すごぷろさんにチームを組んで頂いて参加しました。(開始4分前に突然チームを組もうとお願いする馬鹿の図👇)
https://twitter.com/chakku_000/status/812522220375281664
部室に集まって解くことにしました。
とりあえずA問題.
僕「とりあえずできるだけ大きい2の累乗を取っていったらどうですかね!」
とこのまま実装して56点を取る。流石に56点じゃ悲しいので考察を続けて「N/2を超える最大の2の累乗の数を左と右からとっていって被った部分を引く」という解法を考え,最初の1回だけに適用する。これで75点。ここまで順調だったので「毎回これにすればいいんじゃない!」とか調子に乗る。実装して提出してみると27点。絶望。改善を入れても33点程度。ならば2の累乗の数2個 or 3個に分割できるときだけ別で分ければ良いのじゃないかと考えたりしてみる。
ここですごぷろさんがBを出して24点獲得してEを時始めてた。
この時点で自分らより上にA100点が結構いたのでAをもう少し頑張るが、いい方法が思い浮かばなくて困る(;´･ω･)。
諦めてI問題にうつる。
I問題を読んでたらすごぷろさんがEで100点をだす。凄い。。。そのまますごプロさんはJ問題を始めた。
とりあえずIの部分点を狙うが実装が面倒臭そうなのと計算量が厳しそうなのですごぷろさんに相談。計算量についてはすごぷろさんと部分点なら行けるのではと考え実装し始める。
実装つらい。
ここで僕が実装をバグらせる && 実装をそもそも間違える
をしてしまい計算量が凄く大きくなって(多分予定の10^4倍くらい大きくなった...)しまうが残り数秒なので諦め。
すごぷろさんは知らない間にJを50点とってた。。。。
終了。
昼の部21位で結構良い順位じゃないかとおもったけどどう考えても僕の功績殆ど無いですよね！！！すごぷろさんチーム組んでくれてありがとうございました！
その後部室で考察したりおしゃべりしたりでぐだぐだ~して帰りました(o_o)v
XPS13(9360)にubuntuを入れた
DellのXPS13(9360)を買ったのでubuntuを入れようとした。
目的としてはwindows10とubuntuのデュアルブートをしようとしたが、それ以前の問題でubuntuのインストール時にSSDを認識できなかった。
とりあえずArchwiki
Dell XPS 13 (2016) - ArchWiki
また、dellのxps13は9350のときも問題があったらしくその解決方法が日本語であった.
qiita.com
ぶつかった問題
上記したとおりubuntuの起動usbを作成し、起動後にDELLマークが出ている間にF12を連打してOne Time Bootからubuntuの起動usbを指定して起動する。このときに使用したubuntuのバージョンはubuntu16.04であった。
Try without install ubuntuを選択し起動するとまずWifiが使用できない。おそらくドライバの問題?
更にインストーラーを起動するとSSDが認識されていないのでインストールする先がなくエラーでインストーラーが停止してしまう。
つまりこのままではインストールできない。
実際にやったこと
とりあえずwindowsの回復ドライブを作った。デュアルブートの場合あとで使用するので作成は必須である。ubuntuのみにするなら必須ではないが作っておいてもUSBメモリ1本分くらいしか損はしないので作っておいて良いのではないだろうか...
まずubuntuからSSDが認識出来ない問題について、これはどうもSATA controllerがRaidになっているのが問題らしい(そもそもなんでSSD1台のノートの初期設定をraidにしているのか意味不明である). これをAHCIにするとSSDが認識できるらしい。
これはPCを起動してDELLマークが表示されている間にF2を連打してBIOSの設定を開く。そしてSystem ConfigurationのSATA OperationがRaidになっているのでAHCIを選択して終了する。
これでWindowsを起動しようとすると起動に失敗する！！！
が上のQiita通りなので問題なし。
回復ドライブからwindowsを起動して再インストールすれば何も問題がない。
windowsを再インストールしたらPCにubuntuの起動usbを挿し、PCを起動。
DELLマークが表示されている状態でF12を連打してusbから起動する。
Wifiが使用できないのは変わらないがインストーラーを使用して落ちることなくインストールできる。
これでインストールは終了。
これで終わりとおもってubuntuを起動したら、
問題が発生する！！！
まず、解像度が800x600に固定されてしまい変更ができない。更にusbからの起動時同様にWifiが使用できない。
「おいおいまってくれ、、、Wifiはともかく君usbから起動した時は解像度問題なかったやろ...その時の状況で動いてくれ」
状況は依然厳しい。
まあどちらもディスプレイと内蔵Wifiアダプタのドライバがはいっていないことが問題なきがする。とりあえずカーネルのバージョンを調べたらkernel4.4.0だった。
カーネルのバージョン的には(適当にググったあたり)大丈夫そうな感じはしたがとりあえず16.10にしてみることで解決を目論んだ。
ubuntu16.10の起動usbを作り起動してみるとwifiが動いている。そのままインストールして起動するとwifiは動き解像度も正しく表示されている。
おそらくubuntuのインストールはこれで完了!!!
疑問点
疑問1 16.04のときにusbから起動して解像度は問題なかったのになぜインストールしたらおかしくなったのだろうか?wifiが使えなかったから「ubuntuのインストール中にアップデートをダウンロードする」と「「サードパーティソフトウェアをインストールする」を選択できなかったのが問題だったのだろうか?
疑問2 海外ではxps13 developer editonなるものがあってそれにはubuntu16.04がインストールされておりドライバ周りなどの動作が保証されているらしい。おそらく同じwifiアダプタ使ってるのではと思っていたのだが16.04で動作しなかったのはなぜだろうか....
疑問3 xps13のドライバでlinuxから使えるのってどこにあるんですか.....(dellの公式みてもwindows用しかない)
だれかこの疑問点解決(特に疑問3)を解決できるひといたら教えてくださいっ
感想
Dellさん頼むからDeveloper Editionを日本でも販売してくださいお願いします
gemでneovimをインストールできなかった
なんか
sudo gem install neovim
とかしたら
ERROR: Failed to build gem native extension
とか出てきて困った。
sudo apt-get install ruby-dev sudo gem install neovim
としたらいけた
SRM 700 Div1 Easy FindingFriend
解法
(2017/4/29:解き直したので下にちょっと付け足す.解法を確認するなら下に追記した部分を読んだほうがよい)
leader[i]がfriendPlaceよりも大きい場合、部屋i以降はleader[i]以上のランクの人だけで調整しなければならないのでleader[i]がfriendPlaceよりも小さいiのみ考えれば良い。
各部屋に収まる人数はroomSizeでそのうちleaderは決まっているので残りのroomSize-1人を埋めればよい。
leaderをソートしておきleaderのランクの小さい順にみる。
もしleader[i]-1 = roomSize*iだった場合、部屋0~i-1に入る人(roomSize*i人)は確定するのでfriendPlaceが入る余地はないので求めるパターンは0~i-1では0になり、部屋iから数え直す。
leader[i]のいる部屋iに対し、ランクがleader[i+1]-1の人までは部屋0~iのどこかに入らなくてはならない。
もし部屋iにleader[i]からleader[i+1]-1のランクの人を埋めてもランクleader[i]~leader[i+1]-1の人が余ったら以前の余っている部分を埋めて、それでも部屋0~iに余裕があるならその余裕の部分にfriendPlaceランクの人を入れることができるので余裕の部分が部屋iにできるようにすれば部屋iにfriendPlaceをいれることができる。
ソースコード
class FindingFriend{ public: int find(int roomSize, vector<int> leaders, int friendPlace) { int roomCount=leaders.size(); if(roomCount==1 or roomSize==1) return 1; rep(i,roomCount) if(leaders[i]==friendPlace) return 1; sort(ALL(leaders)); int ret=0; int rem=0; rep(i,roomCount){ if(leaders[i]>friendPlace) break; if(rem==0) ret=0; if(i==roomCount-1){ ret++; break; } assert(leaders[i]<=roomSize*i+1); int rs=roomSize-1; int diff=leaders[i+1]-leaders[i]-1; rem += rs-diff; ret++; } return ret; } };
感想
自分で解けなくて他の人のコードを見て理解した。なんか気がつけば当然の問題だけど全く気が付けない。。。friendPlaceの移動によりそれ以降の部分にも影響が出てしまうような気がしてしまうので難しかった。次に似た問題を見ても解けない気がする。。。
2017/4/29追記
解き直した.ソースコードがシンプルになったのであげ直す.
class FindingFriend{ public: int find(int roomSize,vector<int> leaders,int friendPlace){ int roomCount = leaders.size(); sort(all(leaders)); auto itr = std::find(all(leaders),friendPlace); if(itr!=leaders.end()){ return 1; } ll ans=0; for(int i=0;i<roomCount;i++){ if(leaders[i]>friendPlace) break; if(leaders[i]==i*roomSize+1){ ans=0; } ans++; } return ans; } };
解法は変わらないが,frindPlaceがleadersに含まれていないときに,
1.leaders[i]がfriendPlaceよりも大きければfrindPlaceをその部屋に追加するとleaders[i]よりfrindPlaceが小さくなり矛盾が生じるので考えなくて良い.
2.leaders[i]==i*roomSize+1の場合,部屋[0,i)は全て確定するのでfriendPlaceが追加される余地がない.ここでfriendPlaceはleaders[i]よりも小さいことが保証されているのでfriendPlaceは部屋iには入れる.
3.その他.普通に入れる.
2,3の場合は部屋iには入れるので前からカウント(+1)していけば部屋0~iは入れないが,i+1からjは入れるみたいな状況のときにi+1のときにカウントが0から再カウントされるので大丈夫.
