裏紙

ほぼ競プロ、たまに日記

programming

2016/11 solved(1)

11/1 CF #378(Div2)に参加 ABCDの4完だった。codeforcesは実装に罠が多い問題が多いような感じがしてきた。今回はちゃんと出したやつを全部通せたけど、実装方針とかは場数がどうしても必要になる感じがある。ここで紫に到達。 AOJ 2758 - Sendame AOJ 2759 …

CF 732 F - Tourist Reform

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。このグラフは連結であり、多重辺や自己ループは存在しない。さて、この辺を全て有向辺に変更することを考える。有向辺に変更した後のグラフ上で、を「頂点を始点としたときに訪れることの…

CF 732 E - Sockets

問題 Problem - E - Codeforces 問題概要 台のコンピュータがあり、それぞれ番目のコンピュータは電力を必要とする。今、会場には個のコンセントがあり、番目のコンセントは電力を供給できる。そして、を満たすときに限って、番目のコンピュータと番目のコン…

2016/10 solved(2)

10/17 imulan.hatenablog.jp ARC 021 C - 増築王高橋君 まず、個の家に対して、どこまで増築していいか値段を二分探索する。が大きいので、それぞれの家に増築の回数を1回ずつ余地を残すために回以下の増築が許されるところを探索して、それがおわったらそこ…

POJ 2429 - GCD & LCM Inverse

問題 2429 -- GCD & LCM Inverse 問題概要 の値と、の値が与えられるとき、の値を答えよ。ただし候補が複数ある場合には、その中でもが最小のものを答えよ。 アイデア まず、基本的な性質としてがある。両辺を2回で割ると となる。これらは全て当然割り切れ…

AOJ 2608 - Minus One

問題 Minus One | Aizu Online Judge 問題概要 頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。 からへはたどり着ける…

SPOJ METEORS - Meteors

問題 SPOJ.com - Problem METEORS 問題概要 ある惑星の軌道上には隕石が降り注いでくる。その軌道を個の領域に分割し、と番号をふる。このとき、番号は連続的に振られ、番目の領域と番目の領域は繋がっている。その個の領域に分けた領域に対してそれぞれつず…

2016/10 solved(1)

10/1 CF 721 C - Journey 方針自体は(現在地,訪れた超点数)=かかる時間の最小値というシンプルなDPだったのだけど、queueとBFSで実装してしまい本番はMLEで死んだ。dfsに書き直して様々な修正をしてようやくできた(submission)。 CF 721 D - Maxim and Array…

SRM 652 Div1 Easy - ThePermutationGame

問題 TopCoder Statistics - Problem Statement 問題概要 AliceとBobが次のようなゲームをする。まず、正の整数が与えられる。次に、Aliceは正の整数を選ぶ。最後に、Bobは~の順列を作成する。 そして、の番目の要素をと表すこととし、関数を次のように定め…

AGC 005 D - ~K Perm Counting

問題 D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder 問題概要 長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。 アイデア 答えを直接求めに行くのではなく、余事象を求めることにする。つ…

2016/9 solved(2)

9/16 ABC 045 A - 台形 / Trapezoids ABC 045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit) 最近簡単な問題を意識してPythonで解いている。 9/17 imulan.hatenablog.jp 9/18 CF 716 A - Crazy Computer ただシミュレーションしていく。 …

SRM 653 Div1 Easy - CountryGroupHard

問題 TopCoder Statistics - Problem Statement 問題概要 人が1列に並んだ椅子に座っている。人々はそれぞれ出身国があり、同じ出身国の人たちは固まって座る。インタビュアーが座っている人のうちの何人かに次のような質問をしました:「ここにあなたと同じ…

CF 716 D - Complete The Graph

問題 Problem - D - Codeforces 問題概要 頂点辺の無向グラフがある。辺にはそれぞれ重みがあり、その重さは正の整数である。いくつかの辺の重みがわからなくなってしまったので、その辺に重みを付け直したい。ただし、頂点から頂点への最短経路はでなければ…

CF 682 D - Alyona and Strings

問題 Problem - D - Codeforces 問題概要 アルファベットの小文字のみで構成される文字列があり、長さはそれぞれである。今、の中から共通部分を持たず、それぞれが空ではない部分文字列を個選ぶ。そして、その選んだ個の部分文字列が、の中にも同じ順番で現…

2016/9 solved(1)

9/1 CSAcademy - Addition CSAcademy - Great Common Divisor CSAcademy - Matrix Exploration CSAcademy Tasksのチュートリアル的3問。3問目は個の点を始めにqueueに入れてBFSすればよい。 9/2 CSAcademy #1 - Word Ordering CSAcademy #2 - Word Permutati…

Week of Code #22 - Number of Sequences

問題 Programming Problems and Competitions :: HackerRank 問題概要 要素数の数列について、以下の条件を満たしていれば「数列はniceである」とする: がの約数となっているような全てのの組に対して、が成立 いま、数列がとして与えられる。しかし、何箇…

SRM 655 Div1 Easy - BichromePainting

問題 TopCoder Statistics - Problem Statement 問題概要 のグリッドがあり、最初は全て白に塗られている。の領域を白または黒に塗るという動作をすることが何回も出来るときに、最終状態がboardとして与えられるのでこの最終状態を作ることができるか否かを…

CS Academy #1 - Unfair Game

問題 https://csacademy.com/contest/archive/#task/unfair_game/ 問題概要 個の整数で構成される集合がある。この集合を使ってAlexとBenはゲームを行う。Alexが先手、Benが後手となって交互に自分のターンを行うが、このゲームでは先手と後手ではできる行動…

2016/8 Solved(2)

8/17 ABC 043 A - キャンディーとN人の子供イージー / Children and Candies (ABC Edit) ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit) 8/18 WUPC2nd A - 団子とうさぎ 和の公式と剰余. WUPC2nd B - 雨上がり 最低限踏む水たまりの数を…

SRM 656 Div1 Easy - RandomPancakeStack

問題 TopCoder Statistics - Problem Statement 問題概要 枚のパンケーキがある。それらのパンケーキは~までの番号が振られており、番目のパンケーキは大きさがでおいしさがである。パンケーキをいくつか選んでプレートにのせてタワー状のパンケーキを作ろう…

CF 711 D - Directed Roads

問題 Problem - D - Codeforces 問題概要 番から番まで番号が振られた個の街がある。この街の間には本の有向辺があり、それらは番の街から番の街へ伸びている()(つまりそれぞれの街から1本ずつ有向辺が出ており、自己ループはない状態))。 今、自由に何本で…

AGC 003 D - Anticube

問題 D: Anticube - AtCoder Grand Contest 003 | AtCoder 問題概要 要素数の重複を許す整数の集合が与えられる。この集合の部分集合の中で、その部分集合のどの2つの要素の積も立方数にならない部分集合の最大のサイズを求めよ。 アイデア まず、2数をかけ…

ARC 060 E - 高橋君とホテル / Tak and Hotels

問題 E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder 問題概要 件のホテルが一直線上に並び、座標はで与えられる。一日に移動可能な距離の上限がである。次のようなクエリが個与えられるので、各クエリに答えよ: 一日ごとに…

ARC 059 F - バイナリハック / Unhappy Hacking

問題 F: バイナリハック / Unhappy Hacking - AtCoder Regular Contest 059 | AtCoder 問題概要 キーボードには0,1,Bの3種類のキーがある。Bは空文字列でなければ末尾の一文字を削除する。このキーボードのキーを回押して文字列を入力したい時、入力方法は何…

ARC 043 C - 転倒距離

問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder 問題概要 からまでの整数を並び替えたものをサイズの順列として,サイズの順列とに対して,その2つで順序が入れ替わっている数字の組の個数をとの転倒距離とするときに,ともとも転倒距離の等しい…

GCJ 2016 Round2 D - Freeform Factory

問題 Dashboard - Round 2 2016 - Google Code Jam 問題概要 工場には個の機械がある.それぞれの機械にはオペレーターがひとりずつ必要になる.いま,オペレーターを人雇おうとしている.そして,次の正方行列が与えられ,の位置には従業者が番目の機械を扱…

2016/8 Solved(1)

8/1 AGC 002 D - Stamp Rally UnionFindと二分探索を「クエリ全部に同時並行的に」行っていく.まず,クエリが1つだったときのことを考えてみるとこの兄弟はスコアi以内で収まるかどうかというものを判定しながら二分探索していくことになる.その際に,i番…

GCJ 2016 Round2 C - The Gardener of Seville

問題 Dashboard - Round 2 2016 - Google Code Jam 問題概要 行列のセルの中に,/または\の斜めの線を入れて迷路を作る.そして,そのセルの外周の四つ角以外の部分に左上から時計回りに順に番号を振る(個).以下に,2*2行列の周りに番号が振られている例と…

ARC 024 C - だれじゃ

問題 C: だれじゃ - AtCoder Regular Contest 024 | AtCoder 問題概要 長さの文字列がある.この中から長さの連続する部分文字列を2つ取り出して,アナグラムになっている位置があるかどうか判定せよ. アイデア 文字列内の文字はアルファベット小文字のみな…

CF 677 D - Vanya and Treasure

問題 Problem - D - Codeforces 問題概要 のグリッドとして表される宮殿の中にいる.それぞれの部屋の中には引き出しがあり,上から行左から列の位置には番の引き出しがある.番の引き出しには,番の引き出しを開けるためのカギが入っており,番の引き出しは…