kmjp's blog

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

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

TopCoderOpen 2013 Round1A Hard DirectionBoard

SRM

さてHard。本番中には解けなかったけど、終わってみて再チャレンジしたらすぐ解けた。 そんな問題。 http://community.topcoder.com/stat?c=problem_statement&pm=12390 問題 平面上の各マスに、上下左右のいずれかを向いた矢印がある。 各マスから開始して…

TopCoderOpen 2013 Round1A Medium TheFrog

SRM

本番は計算量見積もりがいまいちで落とした問題。 周りの人の正答率も1/4以下と何気にみんな苦戦。 http://community.topcoder.com/stat?c=problem_statement&pm=12397 問題 1直線上に、いくつか池が与えられる。 原点から距離Xずつジャンプした際、どこの…

TopCoderOpen 2013 Round1A Easy HouseBuilding

SRM

初のTCO参加。Round1B/1Cは日程的に出られないので、1Aで抜けておきたい。 結局、Mediumはsubmitしたものの計算量見積もりミスで失敗。 Easyをかなり速く解けたので、それで1Aを突破。 http://community.topcoder.com/stat?c=problem_statement&pm=12396 問…

TopCoder SRM 571 Div2 Easy FoxAndGame

SRM

Div2 Easyも練習しよう。 http://community.topcoder.com/stat?c=problem_statement&pm=12438 問題 ゲーム1回につき0~3のスコアに応じて、"---"、"o--"、"oo-"、"ooo"の文字列が与えられる。 複数回ゲームを行った場合に文字列の配列が与えられるので、総…

TopCoder SRM 571 Div1 Easy FoxAndMp3

SRM

ああ、またやらかしてしまった。 Easyをしょうもないミスで落としたうえ、Challengeをミスってスコアマイナス。 自分はミスが多いのかTopCoder向いてないな…。AtCoderやCodeForcesの方が気が楽。 http://community.topcoder.com/stat?c=problem_statement&pm…

AtCoder ARC #012 : C - 五目並べチェッカー

ARC

さて問題C。 練習の際、解法はすぐわかったけどWAを2回してしまった。 これでは本番参加しててもそこそこの順位にしかなんなかったな。 http://arc012.contest.atcoder.jp/tasks/arc012_3

AtCoder ARC #012 : A - 週末、B - アキレスと亀

ARC

ARC #012は不参加なので練習のみ。 まずは2問まとめて。 http://arc012.contest.atcoder.jp/tasks/arc012_1 http://arc012.contest.atcoder.jp/tasks/arc012_2

TopCoder SRM 570 Div2 Hard CentaurCompanyDiv2

SRM

Div2 MediumはDiv1 Easyとほぼ同じなので、次はDiv2 Hardに行く。 http://community.topcoder.com/stat?c=problem_statement&pm=12426 問題 木となっているグラフ与えられる。 ここからいくつかの辺を選んで、小さな木を作れる組み合わせの数を答える。 解法…

TopCoder SRM 570 Div2 Easy Chopsticks

SRM

さてDiv2も練習。 http://community.topcoder.com/stat?c=problem_statement&pm=12424 問題 色んな長さの箸が1本ずつある。 同じ長さの箸が2本あると1組の箸となる。 箸の長さが配列で与えられたとき、作れる箸の組数を答える。 解法 長さ別に数を数え、2…

TopCoder SRM 570 Div1 Easy RobotHerb

SRM

SRM570に参加。何とかEasyだけそこそこの時間で解ききってちょっとレート上昇。 http://community.topcoder.com/stat?c=problem_statement&pm=12427 問題 整数値Tと整数値配列Aが与えられる。 ロボットは最初(0,0)にいて上を向いている。整数値配列Aの各要素…

TopCoder SRM 569 Div1 Medium TheJediTest

SRM

さてDiv2 Easyのアレンジ問題、Div1 Medium。 http://community.topcoder.com/stat?c=problem_statement&pm=12265

TopCoder SRM 569 Div2 Hard MegaFactorialDiv2

SRM

続いてDiv2 Hard。 Div2 Hardは自分も何とか解き切れる位の問題が多くて、好みなんだよね。 http://community.topcoder.com/stat?c=problem_statement&pm=12400 問題 演算子!は以下の性質を持つ。 n>0, k>0ならn!k = (n-1)!k * n!(k-1) n=0 なら n!k = 1 k=0…

TopCoder SRM 569 Div2 Medium TheDeviceDiv2, Div1 Easy TheDevice

SRM

さてDiv2 MediumとDiv1 Easy。 これらは若干内容が異なるがほぼ同じなのでまとめて紹介。 http://community.topcoder.com/stat?c=problem_statement&pm=12388 http://community.topcoder.com/stat?c=problem_statement&pm=12399 問題 ある計算機がある。この…

TopCoder SRM 569 Div2 Easy TheJediTestDiv2

SRM

今回は不参加のためゆっくりと復習。 Div1はEasyもHardも1発Correct出来ず、複数回でCorrectしたので、今回不参加で良かった…。 ではDiv2 Easyから。 http://community.topcoder.com/stat?c=problem_statement&pm=12404 問題 色々ストーリー仕立てしてあり…

Codeforces #165 Div1. C. Flawed Flow

Div2ならEになる問題。ここまで解ければDiv2は余裕のはず…。 ということでCにチャレンジ。 http://codeforces.com/contest/269/problem/C 問題 辺あたりの容量がついた無向グラフが与えられる。 このグラフの始点から終点に対し、すべての辺を使って最大フロ…

AtCoder ARC #002 : D - ボードゲーム

ARC

ちょっと古い問題だけど、ARCで解ききってないのはこれだけなので解いてみた。 公式の解説が無いので、他のソースを見ながら自分なりに解釈して回答。 http://arc002.contest.atcoder.jp/tasks/arc002_4

TopCoder SRM 564 Div1 Hard DefectiveAddition

SRM

SRM564はDiv1 Hardだけど850ptと割と低めなのでチャレンジしてみた。 http://community.topcoder.com/stat?c=problem_statement&pm=12346 問題 整数値の配列が与えられる。 この配列の各要素に対し、0~要素の間で整数値を選んで全要素分XORを取ったとき、そ…

Codeforces #164 Div2. E. Playlist

本番一部分最後まで詰められなくて解けなかった問題。 http://www.codeforces.com/contest/268/problem/E 問題 曲の長さと好みである確率が与えられる。 ある曲が好みの場合、それを聞いた後好みの曲のリストに加える。 曲が好みでない場合、曲を聞いた後口…

Codeforces #164 Div2. D. Wall Bars

さて本番解けなかった問題D。 周りを見ても、EよりDの方が正解者が少ないようだ。 http://www.codeforces.com/contest/268/problem/D 問題 中央の棒を取り囲むように4本の脚がある遊具がある。 1~Nの高さで、それぞれ1本ずつ中央といずれかの脚に棒を渡す…

Codeforces #163 Div2. E. More Queries to Array...

Div2とはいえ、Eになると実装が結構しんどい… それでは最終問題。 http://codeforces.com/contest/266/problem/E 数列に対してクエリが送られるので、数値を更新したり部分列から計算されるスコアを返す問題。 数列の要素数Nが最大100000個、クエリ数Qも1000…

Codeforces #165 Div2. A. Fancy Fence, B. Multithreading

次回はDiv2になってしまったので、Div2の問題も復習。 http://codeforces.com/contest/270/problem/A http://codeforces.com/contest/270/problem/B A. Fancy Fence 1~179の整数値Aが与えられるので、1つの内角がその数値になるような正多角形が作れるかを…

Codeforces #165 Div1. B. Greenhouse Effect

さてB。苦戦しつつも何とか本番中に解けた。 http://codeforces.com/contest/269/problem/B 1次元の数直線上に木が並んでおり、木の種類と木の座標が与えられる。 木を並べ替えて、木の種類が1列にソートされるようにしたい。 並べ替えのために植え替える…

Codeforces #165 Div1. A. Magical Boxes

#165に参加。Aを最初10分で解けたと思ったら最後までバグが取れなかった…。 なんとかBだけ解いたけど微妙な順位でまさかのDiv2落ち。 ひどい結果だ…。http://codeforces.com/contest/269/problem/A サイズ2^(k-1)の箱は2^kに4つ収まる。 色んな数とサイズ(2…

Codeforces #164 Div2. C. Beautiful Sets of Points

さて、気づくか気づかないかで難易度が大幅に変わる問題。 http://codeforces.com/contest/268/problem/C 2次元座標のうち長方形の領域(0,0)-(W,H)が指定される。 その中で複数の格子点を選び、その格子点同士の距離が非整数になっているような格子点群のう…

Codeforces #164 Div2. A. Games, B. Buttons

#164はDiv2のみだったので非正規参加。時間中にはCまで解けた。 ではAから練習。 http://codeforces.com/contest/268/problem/A http://codeforces.com/contest/268/problem/B A. Games 30個のチームがあって、ホームとアウェイ用のユニフォームの色が与え…