mayoko’s diary

プロコンとかいろいろ。

GCJ

GCJ Round3 Problem B. Forest University

GCJ

問題 Dashboard - Round 3 2016 - Google Code Jam長さ N の文字列が与えられる。また, 「i 番目の文字は j 番目の文字が現れた後しか現れてはいけない」という条件が与えられる。このような条件を満たす文字列はたくさん考えられるが, この中で「できた文字…

GCJ Round3 Problem A. Teaching Assistant

GCJ

せっかく Round3 にまで進むことができたので参加してみたんですが, 上位陣のレベルの高さを実感してしまい場違い感を感じました…ついていけるようになりたいですね。 問題 Dashboard - Round 3 2016 - Google Code Jam長さ 2n の C か J のみが書かれた文字…

GCJ Round 2 2016 Problem B. Red Tape Committee

GCJ

問題 Dashboard - Round 2 2016 - Google Code JamN 人の人がいる。それぞれの人は, YES という確率が P[i] で, NO という確率が 1-P[i] である。N 人の中から K 人の人を選んで YES という人と NO という人の確率が K/2 人ずつになる確率を最大化したい(K …

GCJ Round 2 2016 Problem A. Rather Perplexing Showdown

GCJ

問題 Dashboard - Round 2 2016 - Google Code Jamじゃんけんトーナメントをする。各参加者はあまり戦略的でないので, 常に同じ手を出す(例えばグーしか出さない人とかがいる)。なので, もし同じ手を出す人同士が対戦すると, トーナメントが永遠に終わらなく…

GCJ Round 1C Problem C. Fashion Police

GCJ

問題 Dashboard - Round 1C 2016 - Google Code JamA 枚のジャケット, B 枚のパンツ, C 枚のシャツがある。これらを適当に組み合わせて, (a, b, c) というようなペアにして服を着る。 ところでこの世界にはファッション警察がいて, (a, b, c) というペアの服…

GCJ Round 1C Problem B. Slides!

GCJ

GCJ はなんか苦手(得意なのもないけど)。 問題 Dashboard - Round 1C 2016 - Google Code JamB 個の頂点からなる有向グラフを考える。頂点 1 から頂点 B までの経路の数を M 個にしたい。これを満たすグラフは作れるか。作れるなら 1 つそのようなグラフを示…

GCJ Round 1B Problem C. Technobabble

GCJ

この問題とは関係ないですが windows でそれっぽくプログラミングができるようになりました。 問題 Dashboard - Round 1B 2016 - Google Code Jam前半, 後半に分かれたワードの組が N 個与えられる。 あるワードの組 (s, t) について, 「すでに s と同じ文字…

GCJ Round 1A 2016 Problem C. BFFs

GCJ

問題 Dashboard - Round 1A 2016 - Google Code JamN 人の人がいる。それぞれの人 i には一人特別な存在の人がいて, BFF[i] がそれである。いま, m 人からなる以下の条件を満たすサイクルを作りたい。 サイクルをなす各人 i の左右いずれかに BFF[i] がいる …

GCJ Round 1A 2016 Problem B. Rank and File

GCJ

問題 Dashboard - Round 1A 2016 - Google Code Jam行列が以下の条件を満たしている。 各行について, 要素が左から右に狭義単調増加 各列について, 要素上から下に狭義単調増加 各行, 各列単位で見るとそれぞれ N 個の要素がある。これらのうち, 2*N-1 個の…

GCJ Qualification Round 2016 Problem D. Fractiles

GCJ

問題 Dashboard - Qualification Round 2016 - Google Code Jam'G', 'L' のみで構成された長さ K の文字列 original を C 回操作する。 文字列 s を操作するときは, 'G' -> K 個の 'G' が連なったものに変換 'L' -> original に変換 と操作する(なので C 回…

GCJ Qualification Round 2016 Problem C. Coin Jam

GCJ

問題 Dashboard - Qualification Round 2016 - Google Code Jam長さ N(N >= 2) の文字列 s が以下の条件を満たしていると嬉しい。 s[0] = s[N-1] = '1' s の各文字列は '0' または '1' 文字列 s を基数 b (2 文字列の長さ N が与えられるので, 以上の条件を…

Google Code Jam 2008 World Finals E:The Year of Code Jam

GCJ

最小カットの練習その2。問題:Dashboard - World Finals 2008 - Google Code Jam解法:最小カットを使って「燃やす埋める問題」を解くの54ページあたりから。引っかかったので一応実装について注意すると,'?'と'?'を結ぶ辺は1回しか結んではいけない。 一応ソ…