kmjp's blog

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

2013-01-01から1ヶ月間の記事一覧

TopCoder SRM 568 Div2 Hard ShuffleSort

SRM

さてDiv2 Hard。 本番終了後、「Div2 HardよりDiv2 Medium(Div1 Easy)の方が簡単!」って騒いでる人がいたけど、確かに今回Div2とはいえHardの割に優しかった。 http://community.topcoder.com/stat?c=problem_statement&pm=11156 カードをランダムにシャッ…

TopCoder SRM 568 Div2 Easy TheSimilarNumbers

SRM

Div1がひどかったのでDiv2も練習。 http://community.topcoder.com/stat?c=problem_statement&pm=10553 片方の数字がもう片方の10倍より大きい場合、similarでない。 数値の最小値と最大値が与えられた場合、similarでない数値群の最大数を求める。これは単…

TopCoder SRM 568 Div1 Easy BallsSeparating

SRM

またしょうもないミスでEasyを落とした。 Mediumは今回難しくてどうにもならなかったし…。 http://community.topcoder.com/stat?c=problem_statement&pm=12398 最大50個の箱に赤青黄色の玉が1~100万個ずつ入っている。 これらの玉を箱の間で動かして各箱は…

Codeforces #163 Div2. D. BerDonalds

さて本番中に解き切れなかったDへ。 http://codeforces.com/contest/266/problem/D

Codeforces #163 Div2. C. Below the Diagonal

さて3問目。 本番は少しCを見て、その後しばらくDに挑み、またCに戻ってきたのでだいぶ回答がおくれてしまった。 http://codeforces.com/contest/266/problem/C NxN行列のうち、N-1個の要素が1でその位置が与えられる。それ以外の要素は0である。 この時、行…

Codeforces #163 Div2. A. Stones on the Table, B. Queue at the School

さて#163。今回が初本戦参加。 A,Bだけ極端に簡単だったが、両方で1回ずつしょうもないミスをしてひどい順位になった。 ただ、なんとかCを解ききったらまぁまぁな順位でギリギリDiv1昇格になりました。 その後Dも本番時間中に方向性を定めて、その後ノーヒン…

Codeforces #162 Div2. E. Choosing Balls

これは少し考えて案が思いつかなかったので、解説を見て解いた問題。 http://codeforces.com/contest/265/problem/E 問題 最大100000個のボール列が与えられる。各ボールは、色と価値(整数)を持つ。 ここに、最大500個のクエリが来る。クエリにはAとBのパラ…

Codeforces #162 Div2. D. Good Sequences

どんどん行きます。 http://codeforces.com/contest/265/problem/D 単調増加の整数列が与えられる。 その部分列のうち、隣接する要素が互いに素じゃないようなもので最長の部分列の長さを答える。元の整数列のうち任意の2値について、互いに素かどうか判定…

Codeforces #162 Div2. C. Escape from Stones

さて次の問題。Div1 Aと同じ。 http://codeforces.com/contest/265/problem/C 最初リスは[0,1]の領域を保持している。 リスの保持している領域の真ん中に岩が落ちてくるので、リスは領域の左半分か右半分に逃げるため保持領域が半分になる。 リスの逃げた履…

Codeforces #162 Div2. A. Colorful Stone, B. Roadside Trees

続いて#162も練習。とはいえ#163で初参加した後に解いたんだけどね。 最初の2問は簡単なのでまとめて行きましょう。 http://codeforces.com/contest/265/problem/A http://codeforces.com/contest/265/problem/B A. Colorful Stone 石が1列に並んでおり、…

Codeforces #161 Div2. E. Rhombus

さて最後の問題。 http://codeforces.com/contest/263/problem/E 各点の周囲をピラミッド状にスコアをカウントしたときの最大値を答える問題。 数式を見てぱっと思いついたのがAutumnFestのPyramidだった。ということで今回もimos法でチャレンジ。 imos方で…

Codeforces #161 Div2. D. Cycle in Graph

さて4問目。 http://codeforces.com/contest/263/problem/D N個の点からなるグラフで、各点は必ずK本以上の辺をもつ。 そのうち、K+1個以上の点を通る閉路を出力する問題。各点K本の辺をもつので、適当に未到達点を辿ってもK+1個の点まではたどり着く。 後…

Codeforces #161 Div2. C. Circle of Numbers

#161は本参加でなく練習だけなので、これも練習。 http://codeforces.com/contest/263/problem/C N個の点に対して2N個の辺が与えられる。 このN点が閉路になっており、かつ「隣接点および隣接点の隣接点に辺が張られている」という点の並びが取れるグラフな…

TopCoder SRM 567 Div2 Hard MountainsEasy

SRM

続いてDiv2 Hard。 http://community.topcoder.com/stat?c=problem_statement&pm=12380

Codeforces #161 Div2. A. Beautiful Matrix、B. Squares

Codeforcesにも手を出してみた。 #162開催中に申し込んで、横で#161 Div2の問題にトライ。 http://codeforces.com/contest/263/problem/A http://codeforces.com/contest/263/problem/B A. Matrix 5x5の行列が与えられる。1が1か所だけあるので中心からの距…

TopCoder SRM 567 Div1 Medium StringGame

SRM

さてDiv1 Medium。 本番は方向性を間違えてWrong Answerになった問題。 http://community.topcoder.com/stat?c=problem_statement&pm=12378 いくつかの文字列が与えられる。1人目のプレイヤーが1つ文字列選んで、文字列内の文字を並べ替えたうえで、さらに…

TopCoder SRM 567 Div2 Easy NinjaTurtles

SRM

Div2も練習。 http://community.topcoder.com/stat?c=problem_statement&pm=12376 PとKが与えられるので、3*(N/K)+(N/3)==PとなるようなNを求める問題。 上の式を変形するとN=3KP/(9+K)。 分数で小数点以下を切り擦れる処理を考慮して、上記Nの周辺を探索し…

TopCoder SRM 567 Div1 Easy TheSquareRootDilemma

SRM

今回はMediumで方針を間違ってしまいEasyのみAC。 Challengeを1ミスしたこともありレートが微減してしまった。 http://community.topcoder.com/stat?c=problem_statement&pm=12377 NとMが与えられるので、が整数になるような1との√内の数値が同じならいいの…

UTPC2012 : K - ラッピング

UTPCもようやく終盤。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_11

AtCoder ARC #011 : D - きつねさんからの挑戦状

ARC

さて、なんかインチキっぽい解法で通ってしまった問題。 http://arc011.contest.atcoder.jp/tasks/arc011_4

AtCoder ARC #011 : C - ダブレット

ARC

続いて3問目。ここらへんからちょっと骨のある問題に。 http://arc011.contest.atcoder.jp/tasks/arc011_3

AtCoder ARC #011 : A - 鉛筆リサイクルの新技術、B - ルイス・キャロルの記憶術

ARC

今年初のARC、インチキ臭い解法でDが解けてしまってえらい順位に。 ほかの人はちゃんと解いているっぽいのに…。 ではまずは小手調べの2問から。 http://arc011.contest.atcoder.jp/tasks/arc011_1 http://arc011.contest.atcoder.jp/tasks/arc011_2

Autumn Fest 2012 : K - Batch Style Mastermind

ついにAutumn Festの最終問題。 回答見ながら解いたけど、想像以上にコードが膨らんでかなり疲れた…。 http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_11

TopCoder SRM 566 Div2 Hard FencingPenguinsEasy

SRM

さて続いてDiv2 Hard。 Div1 Mediumとどちらが難しいかな…。 http://community.topcoder.com/stat?c=problem_statement&pm=12341 円周上に並んだ杭をロープで囲い、中のペンギンを内包するような図形を作ったとき、その面積が最少となるものを求める。 まず…

TopCoder SRM 566 Div2 Medium PenguinPals

SRM

続いてDiv2 Medium。 http://community.topcoder.com/stat?c=problem_statement&pm=12355 円形に赤か青のペンギンが並んでいる。同じ色のペンギンをペアにしたとき、ペアのペンギン同士を結ぶ線分が交差しないようにして出来るペア数の最大値を求める。円周…

TopCoder SRM 566 Div2 Easy PenguinTiles

SRM

続いてEasyも練習。 http://community.topcoder.com/stat?c=problem_statement&pm=12335 ブロックの配置が与えられるので、最初左にスライドさせ、次に上にスライドすることを考える。 この最終状態と同じ状態にするには、最低何回スライド(0~2)させるか答…

TopCoder SRM 566 Div1 Medium PenguinEmperor

SRM

続いてMedium。 今回解けた人が100人以上いたので、500ptとはいえそこまで難しくはない問題。 http://community.topcoder.com/stat?c=problem_statement&pm=12338 円形に配置された都市群で、X日目に時計回りまたは反時計周りにX個先の都市に移動される。 都…

TopCoder SRM 566 Div1 Easy PenguinSledding

SRM

新年初SRM。 後述の通りEasyで予想外に時間かかってしまったが、ラスト1分半でMediumをsubmitさせ、なんとか2問解け切った。 おかげでSRM563で大ミスして暴落したレートが元の水準まで戻った。では1問目から。 http://community.topcoder.com/stat?c=prob…

Autumn Fest 2012 : J - Ninja of Train

10問目に突入、ぼちぼち終盤。 http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_10

Autumn Fest 2012 : I - Pyramid

Autumn Festも解いてない問題があるので練習。 http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_09