2016-01-01から1年間の記事一覧
12/17 yukicoder No.467 - 隠されていたゲーム Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった... AOJ 2601 - Evacuation …
問題 Problem - F - Codeforces 問題概要 個の町と、それらを双方向に結ぶ道が本ある。それぞれの道に対して、ドライバーの不満度がある。 この不満度を下げるために、その道に対してコストがかかる(つまり、ある道の不満度をだけ低下させるためにはだけかか…
12/1 yukicoder No.450 - ベー君のシャトルラン 往復したりなんだりでなんだかややこしそうに見えるが、結局シャトルランを続ける時間は2つの電車が出会うまでなので、その時間は簡単に求められる。その時間が求まれば総移動距離も簡単に分かる。 POJ 3293 -…
問題 F: Rotated Palindromes - AtCoder Regular Contest 064 | AtCoder 問題概要 長さの数列としてあり得るものを全て用意する。ただし、は は回文(つまりとの逆順に並べたものは一致) という条件を満たす。このようにして得られたに対して、「先頭の要素を…
問題 Problem - E - Codeforces 問題概要 段の階段がある。各段は、下から順に番号がからまで付けられており、その各段にはupかdownかのどちらかが書かれており、その段にいるときに進む方向を示している。そして、そこから移動した瞬間に、その段の示す方向…
問題 E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを…
11/16 AOJ 0282 - Programming Contest segtreeを使って最大得点のチームを管理。 AOJ 0269 - East Wind 愚直にシミュレーション。香りが届くかどうかの判定は、距離チェックと角度チェックをそれぞれすればよい。 AOJ 0221 - FizzBuzz シミュレーションすれ…
問題 G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 頂点が個のグラフがあり、からまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリが個来る。 頂点番号とと重みが与えられて、 とに重みの辺を張る…
CODE FESTIVAL 2016に参加してきました。かなり大規模な競プロのオンサイトイベントです(国内200人+海外20人)。今回は(自分の参加は)去年に引き続き2回目ということで、このイベントの本戦が2016/11/26,27で行われたので行ってきました。 ここでは問題の内容…
11/1 CF #378(Div2)に参加 ABCDの4完だった。codeforcesは実装に罠が多い問題が多いような感じがしてきた。今回はちゃんと出したやつを全部通せたけど、実装方針とかは場数がどうしても必要になる感じがある。ここで紫に到達。 AOJ 2758 - Sendame AOJ 2759 …
問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。このグラフは連結であり、多重辺や自己ループは存在しない。さて、この辺を全て有向辺に変更することを考える。有向辺に変更した後のグラフ上で、を「頂点を始点としたときに訪れることの…
問題 Problem - E - Codeforces 問題概要 台のコンピュータがあり、それぞれ番目のコンピュータは電力を必要とする。今、会場には個のコンセントがあり、番目のコンセントは電力を供給できる。そして、を満たすときに限って、番目のコンピュータと番目のコン…
10/17 imulan.hatenablog.jp ARC 021 C - 増築王高橋君 まず、個の家に対して、どこまで増築していいか値段を二分探索する。が大きいので、それぞれの家に増築の回数を1回ずつ余地を残すために回以下の増築が許されるところを探索して、それがおわったらそこ…
問題 2429 -- GCD & LCM Inverse 問題概要 の値と、の値が与えられるとき、の値を答えよ。ただし候補が複数ある場合には、その中でもが最小のものを答えよ。 アイデア まず、基本的な性質としてがある。両辺を2回で割ると となる。これらは全て当然割り切れ…
問題 Minus One | Aizu Online Judge 問題概要 頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。 からへはたどり着ける…
問題 SPOJ.com - Problem METEORS 問題概要 ある惑星の軌道上には隕石が降り注いでくる。その軌道を個の領域に分割し、と番号をふる。このとき、番号は連続的に振られ、番目の領域と番目の領域は繋がっている。その個の領域に分けた領域に対してそれぞれつず…
10/1 CF 721 C - Journey 方針自体は(現在地,訪れた超点数)=かかる時間の最小値というシンプルなDPだったのだけど、queueとBFSで実装してしまい本番はMLEで死んだ。dfsに書き直して様々な修正をしてようやくできた(submission)。 CF 721 D - Maxim and Array…
問題 TopCoder Statistics - Problem Statement 問題概要 AliceとBobが次のようなゲームをする。まず、正の整数が与えられる。次に、Aliceは正の整数を選ぶ。最後に、Bobは~の順列を作成する。 そして、の番目の要素をと表すこととし、関数を次のように定め…
問題 D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder 問題概要 長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。 アイデア 答えを直接求めに行くのではなく、余事象を求めることにする。つ…
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 ただシミュレーションしていく。 …
問題 TopCoder Statistics - Problem Statement 問題概要 人が1列に並んだ椅子に座っている。人々はそれぞれ出身国があり、同じ出身国の人たちは固まって座る。インタビュアーが座っている人のうちの何人かに次のような質問をしました:「ここにあなたと同じ…
問題 Problem - D - Codeforces 問題概要 頂点辺の無向グラフがある。辺にはそれぞれ重みがあり、その重さは正の整数である。いくつかの辺の重みがわからなくなってしまったので、その辺に重みを付け直したい。ただし、頂点から頂点への最短経路はでなければ…
問題 Problem - D - Codeforces 問題概要 アルファベットの小文字のみで構成される文字列があり、長さはそれぞれである。今、の中から共通部分を持たず、それぞれが空ではない部分文字列を個選ぶ。そして、その選んだ個の部分文字列が、の中にも同じ順番で現…
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…
問題 Programming Problems and Competitions :: HackerRank 問題概要 要素数の数列について、以下の条件を満たしていれば「数列はniceである」とする: がの約数となっているような全てのの組に対して、が成立 いま、数列がとして与えられる。しかし、何箇…
問題 TopCoder Statistics - Problem Statement 問題概要 のグリッドがあり、最初は全て白に塗られている。の領域を白または黒に塗るという動作をすることが何回も出来るときに、最終状態がboardとして与えられるのでこの最終状態を作ることができるか否かを…
問題 https://csacademy.com/contest/archive/#task/unfair_game/ 問題概要 個の整数で構成される集合がある。この集合を使ってAlexとBenはゲームを行う。Alexが先手、Benが後手となって交互に自分のターンを行うが、このゲームでは先手と後手ではできる行動…
8/17 ABC 043 A - キャンディーとN人の子供イージー / Children and Candies (ABC Edit) ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit) 8/18 WUPC2nd A - 団子とうさぎ 和の公式と剰余. WUPC2nd B - 雨上がり 最低限踏む水たまりの数を…
問題 TopCoder Statistics - Problem Statement 問題概要 枚のパンケーキがある。それらのパンケーキは~までの番号が振られており、番目のパンケーキは大きさがでおいしさがである。パンケーキをいくつか選んでプレートにのせてタワー状のパンケーキを作ろう…
問題 Problem - D - Codeforces 問題概要 番から番まで番号が振られた個の街がある。この街の間には本の有向辺があり、それらは番の街から番の街へ伸びている()(つまりそれぞれの街から1本ずつ有向辺が出ており、自己ループはない状態))。 今、自由に何本で…