読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Google Code Jam 2014 Round 1A : B. Full Binary Tree

GCJ

ちょっと手こずったけど何とか解けてよかった。 https://code.google.com/codejam/contest/2984486/dashboard#s=p1

Google Code Jam 2014 Round 1A : A. Charging Chaos

GCJ

GCJ R1Aに参加。事情で慣れない環境かつ時間いっぱい挑戦できない状態だったが、何とかA-LargeとB-Largeを通してR1A突破。 https://code.google.com/codejam/contest/2984486/dashboard#s=p0

Google Code Jam 2014 Qualification Round : D. Deceitful War

GCJ

問題文が長くわかりにくい…。 https://code.google.com/codejam/contest/2974486/dashboard#s=p3

Google Code Jam 2014 Qualification Round : C. Minesweeper Master

GCJ

段々難易度が上がってきた。Smallで数回Incorrectな回答をしてしまった。 https://code.google.com/codejam/contest/2974486/dashboard#s=p2

Google Code Jam 2014 Qualification Round : A. Magic Trick、B. Cookie Clicker Alpha

GCJ

今年もGCJが開始。 無事満点スタートで幸先が良いね。 https://code.google.com/codejam/contest/2974486/dashboard#s=p0 https://code.google.com/codejam/contest/2974486/dashboard#s=p1

Google Code Jam 2013 Round 2 : B. Many Prizes

GCJ

Bは最初手こずったものの、最終的にはきっちり解けて良かった。 https://code.google.com/codejam/contest/2442487/dashboard#s=p1

Google Code Jam 2013 Round 2 : A. Ticket Swapping

GCJ

今年もTシャツ+Round3進出をめざしGCJ R2に参加。 残念ながらA-Largeでlong long型のオーバーフローやらかしてA-Largeを落としてしまった。 B-Largeを当てたものの4年ぶりのRound2敗退。Tシャツはゲットできたけど残念…。 Bを解けたのは成長を実感したんだ…

Google Code Jam 2013 Round 1C : C. The Great Wall

GCJ

さてC。最初Largeが1時間位かかりそうな回答になってしまった。 これだと本番では解けなかったね。 https://code.google.com/codejam/contest/2437488/dashboard#s=p2

Google Code Jam 2013 Round 1C : B. Pogo

GCJ

さてB。この問題、largeの正答率が非常に低いのだけど、日本人の正答率は高かったはず…。 https://code.google.com/codejam/contest/2437488/dashboard#s=p1

Google Code Jam 2013 Round 1C : A. Consonants

GCJ

さてR1C。GCJのRound1は段々簡単になるイメージがあったけど、そうでもなかった。 今回はそうでもなかった。 幸いBは知ってる問題だったので、本番出てもAL・BL・CSは取れたな。 https://code.google.com/codejam/contest/2437488/dashboard#s=p0

Google Code Jam 2013 Round 1A : C. Good Luck

GCJ

ようやく1AのCも解けた。 本番はsmall1しか解けなかったけど、ようやくsmall2も解けた。 https://code.google.com/codejam/contest/2418487/dashboard#s=p2

Google Code Jam 2013 Round 1B : C. Garbled Email

GCJ

さてC。いつもと違い大容量データが与えられる。 https://code.google.com/codejam/contest/2434486/dashboard#s=p2

Google Code Jam 2013 Round 1B : B. Falling Diamonds

GCJ

さてB。これはなかなか面白いと感じた問題。 https://code.google.com/codejam/contest/2434486/dashboard#s=p1

Google Code Jam 2013 Round 1B : A. Osmos

GCJ

今年は1Aで抜けられたので、1Bは練習のみ。 こちらは途中A-Largeでミスもあったけど、最終的には全部自力で解けたのでこちらでもRound1は抜けられてたな。 https://code.google.com/codejam/contest/2434486/dashboard#s=p0

Google Code Jam 2013 Round 1A : B. Manage your Energy

GCJ

さてB。 割と大雑把な解法で自信がなかったが、何とか通って良かった。 時間を見ると、Al・Bl・Csとここまで半分の時間で通ってるんだよな。 https://code.google.com/codejam/contest/2418487/dashboard#s=p1

Google Code Jam 2013 Round 1A : A. Bullseye

GCJ

さてGCJのRound1。 AのLargeをミスして落としたが、幸いBのLargeを取れたのですんなりRound2進出。 Aを取れてればかなりいい順位になったのだが…まぁ1Aを抜けられたのでよしとしよう。 https://code.google.com/codejam/contest/2418487/dashboard#s=p0

Google Code Jam 2013 Qualification Round : D. Treasure

GCJ

さてD。本番はSmallが精一杯で、Largeは解説を見てトライ。 https://code.google.com/codejam/contest/2270488/dashboard#s=p3&a=3

Google Code Jam 2013 Qualification Round : C. Fair and Square

GCJ

さてここからが本番。 GCJとしては珍しくLargeが2段階ある。 https://code.google.com/codejam/contest/2270488/dashboard#s=p2

Google Code Jam 2013 Qualification Round : A. Tic-Tac-Toe-Tomek、B. Lawnmower

GCJ

今年もGCJに参加。今回は予選から手ごたえのある問題で、本番にD-Largeは解けず…。 C-Large2を解けたのは手ごたえがあって良かった。 では復習。 https://code.google.com/codejam/contest/2270488/dashboard#s=p0 https://code.google.com/codejam/contest/…

Google Code Jam 2008 Round 1C : B. Ugly Numbers

GCJ

さて2問目。流石に1問目よりは難しい。 http://code.google.com/codejam/contest/32015/dashboard#s=p1 数字の文字列が与えられたときに、間に+-を挟んでUgly Numberになる組み合わせ数を求める。 2か3か5か7で割り切れるとUglyである。最近はこういう問題…

Google Code Jam 2008 Round 1C : A. Text Messaging Outrage

GCJ

さて1Cも解いていきます。 まだ1問めなので難易度は低め。 http://code.google.com/codejam/contest/32015/dashboard#s=p0 携帯電話風の文字入力において、各アルファベットのキーへの割り当てを変えられる。 各アルファベットの登場回数が与えられたときに…

Google Code Jam 2008 Round 1B : C. Mousetrap

GCJ

R1BのBで止まっていたので、Cも回答。 http://code.google.com/codejam/contest/32017/dashboard#s=p2 1~NのN枚のカードが並んでいるとき、M番目にMが来ていたらそれを取り除く。 M+1番目が先頭に来るように1~(M-1)番目を後ろに持って行って、また同じ処理…

Google Code Jam 2008 Round 1B : B. Number Sets

GCJ

さて2問目。 http://code.google.com/codejam/contest/32017/dashboard#s=p1 最大100万までの差がある整数A,Bと、B以下の整数Pが与えられる。 A~Bまでの整数をグループ分けする際、グループ間で1組でもP以上の素数を共通因数とする整数があれば、そのグル…

Google Code Jam 2008 Round 1B : A. Crop Triangles

GCJ

さて1Bも行きますか。 http://code.google.com/codejam/contest/32017/dashboard#s=p0 最大10万個の点の座標が与えられるので、3点選んで重心が格子点にくる組み合わせの数を求める。 重心がいっしょでも、3点の選び方が別なら別カウントする。 10万個の座…

Google Code Jam 2008 Round 1A : C. Numbers

GCJ

この問題はGCJ2009の宣伝で使われていたので印象深い問題。 この宣伝みてGCJ出るの決めたんだよね。 http://code.google.com/codejam/contest/32016/dashboard#s=p2 問題はnを与えられたときの整数部分下3桁を答えるというもの。 nは最大2000000000なので、…

Google Code Jam 2008 Round 1A : B. Milkshakes

GCJ

続いて2問目。さすがに1問目より難しい。 http://code.google.com/codejam/contest/32016/dashboard#s=p1 N種類のミルクがあって、それぞれ麦芽入り・麦芽なしの2通りがある。 M人の人のミルクの好みを満たすように麦芽入り・麦芽なしを選択する。 麦芽入…

Google Code Jam 2008 Round 1A : A. Minimum Scalar Product

GCJ

さてGCJ2001のRound1に行きます。 http://code.google.com/codejam/contest/32016/dashboard#s=p0 2つのベクトルが与えられるので、内積をとって最小になるようベクトルの要素を並べ替える。 片方を小さい順、片方を大きい順にして掛けて足すだけ。 int N; …

Google Code Jam 2008 Qualification Round : C. Fly Swatter

GCJ

予選最終問題。 http://code.google.com/codejam/contest/32013/dashboard#s=p2 ラケットとガットとボールの大きさが与えられるので、ボールを返せる確率を返す。 全体の面積がR*R*piなので、そこからガットの隙間の面積を返せばよい。 ガットで構成される1…

Google Code Jam 2008 Qualification Round : B. Train Timetable

GCJ

続いて2問目。 http://code.google.com/codejam/contest/32013/dashboard#s=p1 A駅からB駅と、B駅からA駅のダイヤ、および折り返しにかかる時間が与えられる。 このダイヤを運行するのに最少の電車数を答える問題。これは貪欲に、残ったダイヤのうち一番早…

Google Code Jam 2008 Qualification Round : A. Saving the Universe

GCJ

GCJ2008は参加していないので練習。 http://code.google.com/codejam/contest/32013/dashboard#s=p0 検索エンジンリストと、そのあとに単語リストが与えられる。 単語リストの単語を順に検索する際、単語と同じ検索エンジンで検索してはいけない。 最少何回…

Google Code Jam 2010 Round 2 : C. Bacteria

GCJ

本番Smallしか解けていないので、復習してみた。 http://code.google.com/codejam/contest/635102/dashboard#s=p2&a=3 Smallは問題文をそのままシミュレートすれば解け、自分もそうした。 Largeは点が100万とか行くのでシミュレートは無理。細かい証明はAnal…

Google Code Jam 2011 Round 2 : D. A.I. War

GCJ

こちらも本番Smallだけ解いて放置していたので再チャレンジ。 http://code.google.com/codejam/contest/1150486/dashboard#s=p3 Analysisにしたがって解いてみた。 この問題は、辺0->1を最短ルートで行くルートのうち、最短ルートに隣接する点を最大化するも…

Google Code Jam 2011 Round 2 : B. Spinning Blade

GCJ

GCJ2011のRound2は、本番でAl・Bs・Cl・Dsが解けていたがBlは解けなかったので、復習チャレンジ。 http://code.google.com/codejam/contest/1150486/dashboard#s=p1&a=1 解法 最初に、重さDは全くこの問題に影響しないので無視する。 あとは重心が真ん中にく…

Google Code Jam 2011 Round 1B : C. House of Kittens

GCJ

これも昨年解き残していたので復習。 本番でsmallは全数列挙で通したけど、largeは解けていなかったので。 http://code.google.com/codejam/contest/1150485/dashboard#s=p2凸のN角形中に、交差しない複数の対角線を引っ張ったとき、辺の両端の点が異なる色…

Google Code Jam 2011 Round 1C : C Perfect Harmony

GCJ

GCJの過去問を見ていて、この問題をまだ解いていないのでチャレンジ。 数列と数値の上限・下限が与えられる。 数列のすべての数値に対し、割り切るか割り切られる値のうち、上限下限の範囲内にあるものをこたえる問題。 たとえば数列が1 2 5 20で、上限下限…

掲載問題一覧(GCJ)

GCJ

GCJ2008 Qual A B C GCJ2008 Round1A A B C GCJ2008 Round1B A B C GCJ2008 Round1C A B GCJ2010 Round2 C GCJ2011 Round1B C GCJ2011 Round1C C GCJ2011 Round2 B D GCJ2013 Qual A B C D GCJ2013 Round1A A B C GCJ2013 Round1B A B C GCJ2013 Round1C A B…