kmjp's blog

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

2012-01-01から1年間の記事一覧

UTPC2012 : J - きたまさの逆襲

ここまで来ると解き方が思いつかないのでもう実装練習。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_10

TopCoder SRM 564 Div2 Hard KnightCircuit

SRM

SRM564、Div2 Hardが1050ptということで見てみた。 http://community.topcoder.com/stat?c=problem_statement&pm=10966 Div2 HardがDiv1 Easyのアレンジという珍しいパターン。 残念なことにまともに解く前にEditorialを見てしまったのだけどね…。Div1 Easy…

UTPC2012 : I - 最短路クエリ

さてここから300ptの問題。 ノーヒントで解くのが難しいので、ここからは解説読みながら解いてる。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_09

TopCoder SRM 563 Div1 Medium SpellCards

SRM

さてSRM563。こちらは本番にどうにもならなかった問題。 http://community.topcoder.com/stat?c=problem_statement&pm=12329 左右に並ぶN枚のカード列からカードを選択すると、そのカードからLevel枚数分右に続くカードを消し、カード規定のダメージを与える…

TopCoder SRM 562 Div1 Medium CheckerFreeness

SRM

さて不参加だったSRM562の復習。 http://community.topcoder.com/stat?c=problem_statement&pm=11565 最初にcheckerの定義があるが、簡潔に書けば「白点と黒点の集合が与えられて、白点同士を結ぶ線と、黒点同士を結ぶ線が交差するかどうか」を求める。白点…

UTPC2012 : H - 区間スケジューリングクエリ

ここまでは配点200ptの中級問題。 これでもこちらはヒーヒー言ってるのに、UTPCレベル高過ぎだろ… http://utpc2012.contest.atcoder.jp/tasks/utpc2012_08

UTPC2012 : G - k番目の文字列

うーん、これも自前で解こうと思ったけど無理だった。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_07

TopCoder SRM 561 Div1 Medium CirclesGame

SRM

さて本命のDiv1 Medium。 本番は最後まで解き切れなかった…。 http://community.topcoder.com/stat?c=problem_statement&pm=12170 交差しない多数の円に対し、どれか円を選んで内部の点を置くと、その点を含む円は以後利用できなくなる。 2人で交互に上記ス…

TopCoder SRM 561 Div2 Hard FoxAndTouristFamilies

SRM

続いてDiv2 Hard。 これはなかなかお手頃な問題。 http://community.topcoder.com/stat?c=problem_statement&pm=11811

TopCoder SRM 561 Div2 Easy FoxAndVacation

SRM

以前の解き残しを練習しておく。 ということでまずはSRM561 Div2 Easyから。 http://community.topcoder.com/stat?c=problem_statement&pm=11813 休暇の日数と、各街を訪れるのに必要な日数の入れるが与えられる。 休暇中に行ける最大の街の数を答える問題。…

AtCoder ARC #010 : D - 情報伝播

ARC

さて4問目。 本番は後述の強連結成分分解がわからず、部分点10しか取れなかった。 というわけで復習。 http://arc010.contest.atcoder.jp/tasks/arc010_4

TopCoder SRM 565 Div2 Hard DivisibleSequence

SRM

Div2 Hardも挑戦。 Div1 Mediumとは別だけど、これはこれで面白い問題。 今回はDiv1 Mediumの方が難しいかな。 http://community.topcoder.com/stat?c=problem_statement&pm=12274 数Nが与えられ、H個の数列を作る。数列の各要素は前の数の約数でなくてはい…

TopCoder SRM 565 Div2 Easy ValueHistogram

SRM

Div2も練習。 http://community.topcoder.com/stat?c=problem_statement&pm=12275 ヒストグラムを作る問題。 各数値の最大の高さを求め、その高さ+1から順に文字列を作っていけばよい。 class ValueHistogram { public: vector <string> build(vector <int> values) { i</int></string>…

TopCoder SRM 565 Div1 Medium TheDivisionGame

SRM

さてMedium。500ptとはいえ割と正解者が多い回。 自分もあと一歩というとこまで行ったのにバグが取きれなかった…。 http://community.topcoder.com/stat?c=problem_statement&pm=12264 [A,B]の範囲の数列があった場合、2人が数列のうち1より大きい数値を1…

TopCoder SRM 565 Div1 Easy MonstersValley

SRM

さてSRM565。 Easyはすんなり解けた。Mediumは方針自体はあっていたけど、最後までバグが取りきれずsubmitできなかった。 最近レートがグダグダなので、Easyだけでもなんとかレートは上がったけどね。この問題はDiv2 Mediumを少し簡単にしたもの。 http://co…

AtCoder ARC #010 : C - 積み上げパズル

ARC

さて3問目。 ARCはいつも3問目あたりで少しややこしいグラフ・DP系の問題を出してくるよね。 http://arc010.contest.atcoder.jp/tasks/arc010_3

AtCoder ARC #010 : A - 名刺交換、B - 超大型連休

ARC

ARC#010に参加。Bでしょうもないミスでかなり苦戦したため、結局Dのsmallまでしか行かなかった。 もっとも、今の自分の知識的にDの完答には少しギャップがあったのだが…。 ではまずAとBから。 http://arc010.contest.atcoder.jp/tasks/arc010_1 http://arc01…

UTPC2012 : F - Uinny

これは自分で解けなかったので、解説を見て解いてみた。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_06

UTPC2012 : E - 選挙

ここから配点が上がって難易度増加。 なんとかこれはノーヒントで解けました。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_05

UTPC2012 : D - 地図が2枚

続いて4問目。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_04

UTPC2012 : C - 森ですか?

続いて3問目。 ここらで結構難易度高い…。http://utpc2012.contest.atcoder.jp/tasks/utpc2012_03

UTPC2012 : B - 残像に口紅を

さて2問目。 2問目からちょっと考えさせられる。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_02

UTPC2012 : A - 2012年12月02日

本番参加はしてないけど、東京大学プログラミングコンテスト2012を練習してみた。 ノーヒントで行けるのはE位までだったな…。 まだ全部は解いてない。では最初は簡単な1問目。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_01

TopCoder SRM 564 Div1 Medium AlternateColors2

SRM

続いてDiv1。 本番はかなり手こずったけど、最終的に解けて良かった。 解き方はまだしも、もう少しきれいにすんなり書きたかったけどね。 http://community.topcoder.com/stat?c=problem_statement&pm=12345 Div2と同じようにボールを減らすが、今回の場合K…

TopCoder SRM 564 Div2 Medium AlternateColors

SRM

続いてDiv2 Medium。Div1 Mediumと近い問題。 http://community.topcoder.com/stat?c=problem_statement&pm=12343===赤緑青のボールの個数が与えられ、赤緑青の順で1個ずつボールを減らしていったとき、K個目のボールの色を答える。 Kが最少のボールの3倍…

TopCoder SRM 564 Div2 Easy FauxPalindromes

SRM

練習でDiv2 Easyも。 http://community.topcoder.com/stat?c=problem_statement&pm=12325

TopCoder SRM 564 Div1 Easy KnightCircuit2

SRM

先ほど終わったSRM564。 前回やらかしてしまったので今回は慎重に…と思ったがEasyが簡単で拍子抜け。 Mediumで苦労したものの何とか解ききった。 Mediumのポイントがいまいちだったけど、そこそこレートが回復。ではEasyから。 http://community.topcoder.co…

2012 WUPC2 : H - ダイヤグラム

こちらは最近の練習のおかげで解けるようになった問題。 http://wupc2nd.contest.atcoder.jp/tasks/wupc_08

2012 WUPC2 : G - だるま落とし

続いてG。 これ、以前なら部分点しか解けなかった問題なので、今回解き切れてよかった。 http://wupc2nd.contest.atcoder.jp/tasks/wupc_07

2012 WUPC2 : F - 僕は宇宙人

さて続いてF。こちらは本番ミスもあったけど、割とスムーズに解けた問題。 http://wupc2nd.contest.atcoder.jp/tasks/wupc_06