ARC021 C - 増築王高橋君
問題
解法
最小費用で増築するためには，現段階で費用が最小の建物を毎回選んで増築し続ければ良いことがわかる． しかし，毎回すべての建物の費用を確認すると計算量がO(KN)となり，40点しか得られない．
満点解法
貪欲法で増築する建物を選び続けたと仮定して，K回目の増築にかかる費用をPとする．
各建物の増築にかかる費用Piは，
となり，費用Pに達するまでに
Xi回増築を行うことができる．この操作はO(1)で行える．
Pはを満たす最小の値を2分探索で求める．
Pが求まれば，後は各建物の増築費用を足していくだけ．
建物の増築費用PiがPと等しい場合は余分に料金が足される場合があるので，最後に引いてやる必要がある．
計算量はO(NlogL)(LはPの最大値: 1012ぐらい?)
コード
AtCoder緑になったよ
2018/8/25のABC107にて緑になりましたー
2017/2/18のABC055から競プロを初めて1年半…コンテスト回数16回……
実際は競プロから離れてた期間があるので、ほぼ一年ですね。
そこで、僕が緑になるまでにやったことをまとめようかと思います。
やったこと
問題を解いて復習した
具体的に言うと、解けない問題があった時、何故解けなかったか、どうすれば解けるかを解説や他の人のコードを見ながら理解して自分の言葉でまとめてました。分からない問題を分からないままにしない！
例えば解けない問題があったとして、その時のパターンは下の大体３つに分類できると思います。
1. 何をしたら良いかもわからなかった
2. 糸口は見えたが実装できなかった
3. 実装できたけどなんかバグる
1の場合は解説読んでもう一回解いてみる。解説がわかりにくかったら、解説ブログをよむか競プロerが突っ込まれているTwitterのリストがあるので、コンテスト終了後に眺めてみる良いと思います。使ったアルゴリズムの名前とかつぶやいている方がいると思います。
↓こんな感じ
ABC105
— ミドリムシ+ (@Euglenese) 2018年8月11日
A : !!(N % K) or N % K > 0
B : I have code of the O(1) (https://t.co/xhgdg1gIYt)
C : absのbitを下から見る
D : 累積和をとる 詳しくはこちら(https://t.co/7paiWpjIBG)
Perl始めました！(いいえ)https://t.co/rm3TSGvZ5D
強そうな競プロerをTwitterで見かけたらとりあえずフォローしときましょう。
ライバルを見つけておくとモチベ維持にも繋がります。
2の場合は実装方法の問題なので、具体的なアルゴリズム名 + 言語名とかで検索するか、他の人の提出を見て勉強してました。僕はPythonのitertoolsの便利さを最近学びました。他の人のコードを見ながら勉強することで、だいぶスマートにコードを書けるようになった気がします。
3の場合は問題をもう一度読み直すか、条件設定を見直してます。それでもわからないときは解説読んで、ミスした場所をメモっておきましょう。
そして、解いて終わった問題はブログなりGitHubなりEvernoteなりにまとめて置きましょう。自分や他の人が助かります。よく使うアルゴリズムなんかは自分用にライブラリを作ってまとめておいても良いと思います。
僕は今はGitHubでまとめてますが、今後はブログの方も活用していけたらなと思っています。
便利なツール・サイト
僕がよく使っていたツールとサイトを紹介します。
AtCoder Problems
自分が解いていない問題がひと目で分かるので進捗管理で重宝してます。
僕は過去問の全然解けてないので、とりあえず毎日少しづつ埋めていきます。
@drkenさんの過去問精選10問
まずどの問題からを始めれば良いか分からない時はこのページの問題から解けば良いと思います。基本的な操作とアルゴリズムを学べます。
最後に
ここに書いたことはあくまで僕が緑になるまでにやったことであって、これが全て正しいというわけでは無いと思いますが、他の競プロ初心者の役に少しでも立てれば幸いです。コンテストが上手くいかず、モチベが下がることもあるとは思いますが、そういう時は僕を含め、Twitter上の競プロerに相談してみてください。
とりあえず緑になれて良かった！
次は水色になれるように頑張りたいと思います！！
MacでLogicool製webカメラのオートゲインをオフにする方法
Macでカメラとプロジェクタのキャリブレーションをする時にLogicool社のウェブカメラのオートゲインをオフにするのに少々手こずったのでまとめる。
環境
- Mac OS X El Capitan
- HD Pro Webcam C920r
手順
OpenCVを使ってオフにする方法もあるらしいが，Logicool社が提供しているソフトウェアからカメラの設定をいじることができたのでこちらを使う。
- ここからLogicoolゲームソフトウェアをダウンロードしてインストールする。ゲーミングマウスおよびキーボードのカスタマイズとしか書かれていないが、カメラの設定も行える。
- カメラを接続してLogicoolゲームソフトウェアを起動する。
- サポートページに従ってカメラの機能をカスタマイズする。オートフォーカスや自動露出もオフにできる。
第48回情報科学若手の会に参加してきました #wakate2015
9/19(土)〜9/21(月)に静岡県伊東市で開催された
第48回情報科学若手の会に参加してきました．
「帰宅してブログを書くまでが若手の会」ということでブログ始めました．
このイベントを知ったきっかけは@yumu19さんのツイートだったと思います．
自分は大学院進学を決意したのは良いが，
「これから何をしたらいいんだろう？」
という超愕然とした疑問を抱えていたため，
このイベントを通して何かしらの答えが出せたら良いなと思い参加しました．
発表を聞いて
情報科学といってもIoT，HCI，クラウドサービスから福祉機器，哲学，宇宙までと
内容は幅広く，とても面白かったです．いくつか発表をピックアップしました．
IT×宇宙で何をしよう!?
JAXA 館下博昭さん
- ハードだけでなくソフトにも力を入れている
- 衛星からのデータをオープンにしている
http://www.jaxa.jp/projects/db/tebiki_j.html
若手特別講演：ぼくらのプログラミングから、みんなのプログラミングへ
産総研 加藤 淳(@arcatdmz)さん
http://junkato.jp/ja/talks/people-are-programmers/?p=1
- 「実世界情報を扱うプログラミングは難しい」
- 「各データの扱いに特化した開発環境が必要」
- TextAliveの紹介
動画を映像ではなく関数として保存することで簡単にfpsや解像度をいじれる
プログラマやそうじゃない人も使うことができる - プログラミング=🆒
はじめてでもわかる！IoTの過去・現在・未来（特にホームネットワーク）
@yumu19 さん
http://www.slideshare.net/TsubasaYumura/iot-52973276
- IoTの大まかな時代の流れを掴めた気がする．とてもわかりやすい
- 1988年の時点でIoTについて言及していた．「電脳社会論」
- BLEは名前くらいしか知らなかったから参考になった
@izumin5210 さんのLTもわかりやすかったです．
https://github.com/izumin5210/Bletia - 「研究でやるなら流行に飛びつかず先を見据えて」
- PICALAおもしろい！！
自分がへぇ〜って思ったら他の人もオレンジボタン押している
スライドの方を向いていながら他の聴講者と意思疎通ができる..？
言葉に言い表せないが不思議な感覚でした
HCI分野の紹介と最新研究
@ota42y さん
http://ota42y.com/blog/2015/09/20/wakate2015-hci/
- CHI勉強会2015でHCI分野に興味を持ち始めた身としてはすごくありがたい
- 魔法の布は見た瞬間へぁっ！？ってなった
https://vimeo.com/73164578 - HCI分野がどんなものであるかなんとなく理解できた気がする
Denkinovelをどうして作り続けているのか
@katryo さん
- 「もともと絵を描けない人のために作った」
絵が描ける人と差がついてしまうため立ち絵機能はわざと入れていない - すごく考えさせられた３つのこと
- 自分が欲しいと思うサービスを作る
- 勉強のために作る
- ユーザがいるから作り続ける
ルータで斬り込め！おうちIoT
@puhitaku さん
https://drive.google.com/file/d/0B_UoBqSniI1ZcFdiQVk1VHhpYTQ/view?pli=1
参加してみて
本当に参加して良かったと思います．２泊３日があっという間でした．
初参加で知り合いもおらずイベント前日は少し不安でしたが，始まってみると
交流会や懇親会もあり，とても居心地の良い雰囲気でした．
また他の参加者との交流の中で自分のやるべきことが見えた気がしました．
幹事の皆様，参加者の皆様，本当にありがとうございました．
来年も参加するつもりなのでよろしくお願いします．
追記：9/27
「院に行くべきなのかなぁ？」
「IT系の仕事って何やるんだろう？」
という疑問を持っている人
若手の会はインフォーマルで初めてでも参加しやすいと思います．
また様々な分野や出身の人たちが集まるので何かしらの答えが見つかると思います．
是非参加してみてはどうでしょうか？
