飛行機の移動が暇なので蟻本を読んでまとめることにしました。 今回は組み合わせ問題編です。 分割数 問題 個の互いに区別できない品物を個以下に分割する方法の場合の数をで割ったあまりを求めよ。 たとえば、4つの品物を(1, 1, 2)と分割するのと(1, 2, 1)…

D - Factorization 長さの正整数の配列で、各要素の積が正整数となるようなものが何通りなるか、という問題。 解法 の素因数分解を考え、とします。今の問題は次のように言い換えることができます。 個の箱があり、個のを重複を許して入れます。 それぞれの…

F - The Shortest Statement 問題概要 頂点辺の連結な重み付き無向グラフが与えられる。個のクエリに答えよ。番目のクエリでは頂点間の最短距離を答えよ。 考えたこと 木っぽいグラフが与えられるということなので、とりあえず木に場合について考えてみるこ…

CでWAを引きすぎて飛ばしてしまい、Dから解いたので574位になってしまいました、、、 C - Vasya and Golden Ticket 0を除いて考えても同じなのではじめに0を除去しておきます。除去後の文字列が空列なら、これは"0...0"という入力に対する場合であり、"YES"…

ABCD解いて443位でした。可もなく不可もなくといった感じ。Fの解法がめっちゃ気になっているので別記事にします。 C - Vasya and Multisets 1回だけ現れる要素が偶数種類だったら同じ種類ずつ振り分けて、複数回現れる要素を片方にまとめる。 1回だけ現れる…

ABC早解きで123位でした。DはHack中にミスに気づいて厳しい気持ちになってました Div. 1との同時開催だったので普段より強い（早い？）人が少なくて、A, Bを解き終えた時点でほぼトップだったのでびっくりしてました C - Enlarge GCD まず制限時間1秒を見て…

C - Chokutter かなり古い企業コンの問題です。点数はついていませんが、感覚では500ぐらいかなと思います。 問題概要 頂点のグラフが与えられます。はじめグラフには辺がまったく張られていません。 個のクエリが与えられます。クエリには以下の3種類があり…

JAG Camp 2018 Day 3の問題 J - Prime Routing 問題の本質を抽出すると次のようになります。 問題 連結で単純な無向グラフが与えられる。頂点Sから頂点Tに向かう奇数長の最短路の長さはいくらか（辺の長さはすべて1）。存在しない場合は-1を出力せよ。 こん…

原題はE - Self-containedですが、問題の本質は以下のとおりです。 問題 0以上未満の整数からなる集合が与えられる。この中の相異なる3要素で、となるものはあるか。 知識 今回は要素の大きさに制限がありますが、制限がない場合、のアルゴリズムが限界だと…

595位でした。前日に比べればかなりマシですが、AとCをHackされ、 さらにEよりCを優先したためさほど難しくないEを捨ててしまうという散々な結果でした。 追記）Eやっぱむずかったです。じゃあまあいつも通りの結果という感じですかね C - Array Product 0の…

散々な成績でした。C, 正解者数的にも絶対シンプルなアルゴリズムがあるのに思考を切り替えられなかったです。 codeforces.com C - Coffee Break 1日目には、が最小なものから、差をより大きくして、選べるだけ選びます。選んだものはその都度、setから削除…

問題 以下の相異なる3つの素数の組のうち、が素数になるものはいくつあるか。 No.732 3PrimeCounting - yukicoder 解法 100000以下の素数の個数は10000個ぐらいなので、で間に合う。ただしは以下の素数の個数。この問題の場合、自明な解が10分ぐらい待てば動…

University Codesprint 5で唯一解けなかった問題。ツイッターを見る限りFよりもずいぶん簡単という評価だったのでコンテスト中に解けるようになりたい www.hackerrank.com 番目の店で本の剣を買う費用は円で、それを番目の店ですべて売ると、円の利益がでま…

A - Function Height 入力が大きい整数のときはdoubleの精度が足りなくなるので、整数のまま処理をしましょうという問題 B - Diagonal Walking v.2 まずゴールまで最短で行ってから、(1,1), (-1,-1)のムーブを繰り返すという戦略が最適なのであとはやるだけ …

AからFの6完で144位でした。 AからBの難易度の跳ね方がすごすぎて焦りました。 D問題は既出のようですね。 SPOJ.com - Problem SUBXOR B - Array Triplets 全探索をうまくやります。最初これでTLEすると思っていて別解法を模索してたのですが、１時間経って…

17位！！Ratedコンテストでこんな順位取りたい、、 D - Make Them Even 左上から順に見ていき奇数のマスがあったら右か下に追いやったとしても偶数の数は減らない（追いやる先が奇数か偶数かは関係ない）。 これよりかはかなり難しいですが、この問題を思い…