裏紙

ほぼ競プロ、たまに日記

programming

CF 738 F - Financiers Game

問題 Problem - F - Codeforces 問題概要 長さの数列が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。 ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分の…

SRM 643 Div1 Easy - TheKingsFactorization

問題 TopCoder Statistics - Problem Statement 問題概要 自然数の素因数分解を求めよ。ただし、の素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。 例えば、であるとき、素因数分解はであるから、小さい方から数えて奇数番目…

CF 701 F - Break Up

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。グラフが連結である保証はない。 いま、ある辺を削除して頂点から頂点への移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストが…

CF 701 E - Connecting Universities

問題 Problem - E - Codeforces 問題概要 頂点数の木があり、頂点にはからの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、個の頂点番号が指定される。それらをとする。これら個の頂点から、個のペアを作る。そ…

ARC 068 E - Snuke Line

問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 問題概要 個の駅があり、駅に対してからまでの番号が振られている。列車は駅から駅ごとに停車する。また、種類の名産品があり、番目の名産品は駅から駅の区間で売られており、その駅に停まると…

FHC 2017 R2 C - Fighting all the Zombies

問題 Fighting all the Zombies | Facebook Hacker Cup 2017 Round 2 問題概要 RPGをやっている。主人公は魔法使いである。 体のゾンビがいる洞窟がある。番目のゾンビの強さはである。いま、レベリングのために、この洞窟を回周回しようと考えている。この…

CF 749 E - Inversions After Shuffle

問題 Problem - E - Codeforces 問題概要 からまでの数を並べた長さの順列がある。1回だけ以下の操作を行う: 全ての区間個のうち、区間(から)をランダムに選ぶ。そして、その区間の長さをとし、その区間に対して、シャッフルを行う(つまり、通りの並び替え方…

2016/12 solved(2)

12/17 yukicoder No.467 - 隠されていたゲーム Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった... AOJ 2601 - Evacuation …

CF 733 F - Drivers Dissatisfaction

問題 Problem - F - Codeforces 問題概要 個の町と、それらを双方向に結ぶ道が本ある。それぞれの道に対して、ドライバーの不満度がある。 この不満度を下げるために、その道に対してコストがかかる(つまり、ある道の不満度をだけ低下させるためにはだけかか…

2016/12 solved(1)

12/1 yukicoder No.450 - ベー君のシャトルラン 往復したりなんだりでなんだかややこしそうに見えるが、結局シャトルランを続ける時間は2つの電車が出会うまでなので、その時間は簡単に求められる。その時間が求まれば総移動距離も簡単に分かる。 POJ 3293 -…

ARC 064 F - Rotated Palindromes

問題 F: Rotated Palindromes - AtCoder Regular Contest 064 | AtCoder 問題概要 長さの数列としてあり得るものを全て用意する。ただし、は は回文(つまりとの逆順に並べたものは一致) という条件を満たす。このようにして得られたに対して、「先頭の要素を…

CF 733 E - Sleep in Class

問題 Problem - E - Codeforces 問題概要 段の階段がある。各段は、下から順に番号がからまで付けられており、その各段にはupかdownかのどちらかが書かれており、その段にいるときに進む方向を示している。そして、そこから移動した瞬間に、その段の示す方向…

CODE FESTIVAL 2016 Final E - Cookies

問題 E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを…

2016/11 solved(2)

11/16 AOJ 0282 - Programming Contest segtreeを使って最大得点のチームを管理。 AOJ 0269 - East Wind 愚直にシミュレーション。香りが届くかどうかの判定は、距離チェックと角度チェックをそれぞれすればよい。 AOJ 0221 - FizzBuzz シミュレーションすれ…

CODE FESTIVAL 2016 Final G - Zigzag MST

問題 G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 頂点が個のグラフがあり、からまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリが個来る。 頂点番号とと重みが与えられて、 とに重みの辺を張る…

CODE FESTIVAL 2016 参加記

CODE FESTIVAL 2016に参加してきました。かなり大規模な競プロのオンサイトイベントです(国内200人+海外20人)。今回は(自分の参加は)去年に引き続き2回目ということで、このイベントの本戦が2016/11/26,27で行われたので行ってきました。 ここでは問題の内容…

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