Facebook Hacker Cup 2017 Round 1 - Manic Moving

問題 Manic Moving | Facebook Hacker Cup 2017 Round 1 考察 まずは、各都市間の最小移動コストを出します。 N=100と小さいので、ワーシャルフロイドで簡単に求まります。 制約として、荷物は最大2組まで積み込めますが、積み込み・荷降ろしはそれぞれ順番…

Facebook Hacker Cup 2017 Round 1 - Fighting the Zombies

問題 Fighting the Zombies | Facebook Hacker Cup 2017 Round 1 考察 円で移動させ、四角で攻撃するので、少し厄介な感じがします。 が、円の大きさは自由、四角の大きさは正方形で決まっています。 移動させる範囲が所定の正方形より大きくても結局攻撃で…

Facebook Hacker Cup 2017 Round 1 - Pie Progress

問題 Pie Progress | Facebook Hacker Cup 2017 Round 1 考察 購入する必要があるパイの個数は、日数と同じです。 N日間の中のどこでいくつ買うかを決定するので、以下のDPで処理できそうです。 dp[i][j] := i日目までにj個パイを買った場合の最小コスト 各…

Facebook Hacker Cup 2017 Qualification Round - Fighting the Zombie

問題 Fighting the Zombie | Facebook Hacker Cup 2017 Qualification Round 考察 Zは出目の合計を足した後に加算されるので、同じサイコロに対してX回振った場合の確率分布は一定になります。 dp[i][j] := i回同じサイコロを振った時に、合計が値jになる確…

Facebook Hacker Cup 2017 Qualification Round - Lazy Loading

問題 Lazy Loading | Facebook Hacker Cup 2017 Qualification Round 考察 一番上の重さだけが関係あり、他は個数しか見られません。 そのため、「一番上に手持ちの一番重たいもの」を使い、残りは個数だけ見て、「軽いものから順番に」使って50ポンドを超え…

Facebook Hacker Cup 2017 Qualification Round - Progress Pie

問題 https://www.facebook.com/hackercup/problem/1254819954559001/ 考察 基本的には角度を取って比較すれば良さそうに見えます。 0°の線を基準とした角度で図りますが、180°を超えると厄介なので素直に分けて考えます。 また、0°の線を挟んで反対側にPと…

「How Google Works」 感想

こちらも話題になっていたので読みました。 How Google Works (ハウ・グーグル・ワークス) ―私たちの働き方とマネジメント作者: エリック・シュミット,ジョナサン・ローゼンバーグ,アラン・イーグル,ラリー・ペイジ,土方奈美出版社/メーカー: 日本経済新聞出…

Codeforces Good Bye 2016 C. New Year and Rating

問題 codeforces.com 考察 折れ線グラフを書いてみるとわかりやすいです。 なるべくレートを高くしたいので、div2の一番高い状態でのレートが1899になると良さそうです。 その状態で、div1では1900を下回らないようにする必要があります。 これを実現するた…

Codeforces Round #389 (Div. 2) D. Santa Claus and a Palindrome

問題 codeforces.com 考察 スコアが付いている幾つかの文字列を組み合わせ、回文となる文字列の中で最大のスコアを算出する問題です。 全ての文字列は同じ長さなので、これらで回文を作るのは以下の2パターンに分けられます。 ABA'型 AA'型 ここで、AとA'は…

Codeforces Round #388 (Div. 2) D. Leaving Auction

問題 codeforces.com 考察 人が消えるオークションをする問題です。 注意点として、間の人が消えてある人が連続したら、その場合は圧縮されて落札可能な最も安い値段になります。 参加者の数もクエリの数もと多いですが、 除外する参加者の数が最大なので、…

Codeforces Round #383 (Div. 2) D. Arpa's weak amphitheater and Mehrdad's valuable Hoses

問題 Problem - D - Codeforces 考察 問題を要約すると、「あるグループから"全員"・"1人"・"0人"のいずれかを選んでいったとき、重さがwを超えないbの合計値の最大を求めよ」となります。 まず、グループを判定するのはUnionFindで行えます(rootが同じなら…

Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan

問題 Problem - C - Codeforces 考察 色々と試して見ると、まず「輪っかにならない長さ2以上の数列」ができるとアウトになることがわかります。 また、輪っかの長さが偶数ならその半分の長さで済み、奇数ならその長さが必要なこともわかります。 1つの問題中…

Codeforces Round #383 (Div. 2) B. Arpa’s obvious problem and Mehrdad’s terrible solution

問題 Problem - B - Codeforces 考察 xorを各ペアに対して取っていく問題ですが、普通にやると間に合いません。 そこで、A xor A = 0であることを利用し、 A xor B = xの両辺にxor BをかけるとA = B xor xにすることができます。 事前にそれぞれ値の個数を算…

Codeforces Round #383 (Div. 2) A. Arpa’s hard exam and Mehrdad’s naive cheat

問題 Problem - A - Codeforces 考察 というトンデモ数字が出てきて面食らいますが、 結局一番下の桁だけが必要なことに着目します。 ...8 * ...8 * ...8 という繰り返しなので、最後の桁はn=1で8、n=2で88=64なので4、n=3で84=32なので2、n=4で6、n=5で8...…

「Team Geek」 感想

こちらも話題になっていたので読みました。 Team Geek ―Googleのギークたちはいかにしてチームを作るのか作者: Brian W. Fitzpatrick,Ben Collins-Sussman,及川卓也,角征典出版社/メーカー: オライリージャパン発売日: 2013/07/20メディア: 単行本(ソフトカ…

Scala関数型デザイン&プログラミング 6章

概要 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ出版社/メーカー: インプレス発売日: 2015/04/30メディア: Kindle版この商品を含むブログ (2件) を見る を読…

「Soft Skills」 感想

ひとしきり話題になっていたので読みました。 SOFT SKILLS ソフトウェア開発者の人生マニュアル作者: ジョン・ソンメズ,まつもとゆきひろ(解説),長尾高弘出版社/メーカー: 日経BP社発売日: 2016/05/20メディア: 単行本この商品を含むブログ (5件) を見る 総…

Scala関数型デザイン&プログラミング 〜5章

概要 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ出版社/メーカー: インプレス発売日: 2015/04/30メディア: Kindle版この商品を含むブログ (2件) を見る を読…

陸でマイルを稼ぐ方法 調査まとめ 2016/10

マイルについて色々調べたり、メインのクレカを変えたりしたので、備忘録としてさっくり残しておきます。 ちなみに、飛行機に乗りたくない人にとっては全くもって無益な記事です。 詳細はあまり書いていないので、興味がある方は調べてみてください。 参考に…

Scala関数型デザイン&プログラミング 〜4章

概要 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ出版社/メーカー: インプレス発売日: 2015/04/30メディア: Kindle版この商品を含むブログ (2件) を見る を読…

Scala関数型デザイン&プログラミング 〜3章

概要 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ出版社/メーカー: インプレス発売日: 2015/04/30メディア: Kindle版この商品を含むブログ (2件) を見る を読…

yukicoder ★★★ No.307 最近色塗る問題多くない?

問題 No.307 最近色塗る問題多くない? - yukicoder 考察 同じ色で塗った時、塗りつぶしは行われずすぐ終わります。 違う色で塗った時、少なくとも1つはマスの色が変わります。 違う色で塗る処理はその色を全て辿ればいいので、最悪でもで終わります。 また…

yukicoder ★★★ No.1 道のショートカット

おみくじで記念すべき1を引きました。 問題 No.1 道のショートカット - yukicoder 考察 グラフ、に見せかけて、パスは番号が増加するものしかないためDPできます。 お金、時間の2つのパラメーターがあるため、1つはDP表に入れてしまえば答えを求めることがで…

Codeforces Round #371 (Div. 2) D. Searching Rectangles

問題 codeforces.com 考察 大きな範囲をカバーするクエリから徐々に片側を縮めてゆくことで、1辺の境界が分かります。 また、四角形は2つあるので、クエリの答えが「2->1」または「2->0」になった箇所で1つ、「1->0」「2->0」になった箇所にもう1つの辺があ…

「小さなチーム、大きな仕事」 感想

読み終わりました。 小さなチーム、大きな仕事〔完全版〕: 37シグナルズ成功の法則作者: ジェイソン・フリード,デイヴィッド・ハイネマイヤー・ハンソン,黒沢 健二,松永 肇一,美谷 広海,祐佳 ヤング出版社/メーカー: 早川書房発売日: 2012/01/11メディア: 単…

ARC061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 arc061.contest.atcoder.jp 考察 こういう1つのノードが複数の状態を持つグラフは、状態ごとにノードを分割してあげると上手くいくことが多いかと思います。 今回もご多分にもれず、駅と会社の2つをペアで考えてみます。 各行では駅2つと会社が与えられ…

Codeforces Round #370 (Div. 2) C. Memory and De-Evolution

問題 codeforces.com 考察 前提として、三角形になるのは辺の長さが「最小 + 2番目 > 最大」という状態です。 3番目のサンプルにあるように、単純に「初手はなるべくyに近づける」という手法では上手くいきません。 減らす上限を固定しても上手くいかなさそ…

yukicoder ★★★ No.413 +5,000,000pts

問題 No.413 +5,000,000pts - yukicoder 考察 一風変わった問題ですね。 Hackできるケースを考える問題のようです。 与えられたコードを読むと、いかにもな解の公式が書かれています。 +側しか取っていませんが、tは最大の整数なので問題なさそうです。 全く…

Scala関数型デザイン&プログラミング 〜2章

概要 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ出版社/メーカー: インプレス発売日: 2015/04/30メディア: Kindle版この商品を含むブログ (2件) を見る を読…

AGC004 D - Teleporter

問題 agc004.contest.atcoder.jp 考察 K回の移動を行った際に全ての点が首都(1)にいないといけないという条件があります。 これにより、必ず1は1自身に戻るループにしないといけないことが分かります。 1以外の行き先だと、「全ての点が同着で1にいないと…