phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

M-SOLUTIONS プロコンオープン C. Best-of-(2n-1)

問題 高橋くんと青木くんが、どちらかが合計N回勝つまでゲームを繰り返す。 1回のゲームでは、高橋くんが勝つ確率はA%、青木くんが勝つ確率はB%、引き分けになる確率はC%である。ゲームが行われる回数の期待値を出力せよ。 ただし、期待値は小数ではなく、互…

ABC128 F. Frog Jump

問題 N個の蓮が一列に並んでおり、0~N-1まで番号がついている。 最初、0の蓮におり、以下の手順に従ってゲームを行う。1. 正の整数A, Bを決める。得点は最初は0。 2. 現在の位置xとして、y=x+Aとする。xの蓮を消してyに移動する このとき、y=N-1ならゲーム…

ABC128 E. Roadwork

問題 東西に無限に続く1本の大通りがあり、数直線とみなせる。 大通りでN回の工事が行われ、i番目の道路工事はSi-0.5からTi-0.5の時刻にXi地点を通行止めにする。 Q人の人が座標0におり、i番目の人は時刻Diで出発し、速度1で進む。 しかし、工事中の通行止め…

Chokudai SpeedRun002 J. GCD β

問題 整数のペアがN組あり、i番目の整数のペアは(Ai, Bi)で与えられる。 すぬけくんは各ペアからちょうど1つずつ整数を選んで、選んだN個の整数の最大公約数として考えられる最大値が何になるか知りたい。 制約 1 1 解法 最初にA1かB1の約数の集合を考えると…

Chokudai SpeedRun002 I. カツサンドくんβ

問題 N種類の食べ物があり、食べ物iの体力がAi、攻撃力がBiで与えられる。 この食べ物同士を戦わせ、最強の食べ物を決めたい。最強の食べ物は、以下のような対戦を行ったとき、どの他の食べ物と戦っても勝利できるような食べ物とする。食べ物iと食べ物jが対…

ABC127 E. Cell Distance

問題 N*Mのマス目のKマスに1つずつ駒を置くことを考える。 ここで、K個の駒が(x1,y1), ...., (xK,yK)と置かれるときの配置コストを Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|) とする。 駒のすべての配置の仕方のコストを考えたとき、その配置コストの…

ABC126 F. XOR Matching

問題 以下の条件を満たす長さ2^{M+1}の数列aが存在するなら1つ構築せよ。 数列aには、0以上2^M未満の整数がちょうど2つずつ含まれる a_i == a_jになるi,jについて、a_i xor ... xor a_j == Kとなっている 制約 0 0 解法 明確にわかる条件から抑えていく。M=0…

Google Code Jam 2019 Round 2 A. New Elements: Part 1

0完だった。。。(点数分布的にAのlargeは通さないとACDのsmallだけでは無理そうだったので時間をかけてたけどsmallすら通せなかった・・・) 問題 CodiumとJamariumという新しい元素を研究しており、これらの原子量に関する統計を調べたいと思っている。 過去…

Google Code Jam 2019 Round 1B C. Fair Fight

問題 N種類の異なる武器が2つずつ並べてある。 あなたは審判で、まず(L,R)の範囲を指定する。 対戦者のCharlesとDelilaは、その範囲内の武器の一つを選んで対戦を行う。 また、それぞれ人の武器の熟練度がCiおよびDiで与えられ、それぞれ範囲内で一番熟練度…

Google Code Jam 2019 Round 1B B. Draupnir

問題 「X-day ring」というものがあり、これは、X日ごとに分裂し、2倍の個数になるリングである。 最初は、1-day ringから6-day ringまでの6種類のリングがそれぞれ何個か(0個以上100個以下)ある。今、1日目から500日目までのいずれかの日でのリングの合計数…

Google Code Jam 2019 Round 1B A. Manhattan Crepe Cart

問題 グリッドがあり、各交差点は0からQまでの番号の組で表現できる。 今、P人の人が交差点に立っており、それぞれ、東西南北のいずれか一方を向いている。 各人は、向いている向きの方向に1交差点進んだ領域のどこかの交差点に用事があることがわかっている…

Tenka1 Programmer Contest 2019 D. Three Colors

問題 N個の整数aiが与えられる。 この整数に赤、緑、青のいずれかの色を塗る。 このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。 「それぞれの色で塗った整数の和をR,G,Bとするとき、三辺の長さがそれぞれR,G,Bであ…

エクサウィザーズ2019 C. Snuke the Wizard

問題 N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。 ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。 マスの外側に移動させられたゴーレムは消滅する。 Q回の呪文…

Topcoder MM108 CrosswordPuzzler

概要 1週間マラソンはきつい。 最終順位は、20位(58人参加)で、結構良かった。 問題 W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。 このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場…

第3回RCO日本橋ハーフマラソン予選 参加記

概要 第3回RCO日本橋ハーフマラソン予選に参加してみた。 atcoder.jp結果は、A問題が102位、B問題が45位の総合67位でした。(結構善戦できたと思う) 問題 A. ツーリストXの旅行計画 N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考…

みんなのプロコン2019 D. Ears

問題 数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。 このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後…

ABC117 D. XXOR

問題 N個の非負整数A_iと、非負整数Kが与えられる。 ここで、f(X) = Σ (X xor A_i) (0 この関数fの最大値を求めよ。 制約 1 0 0 解法 関数fはビットごとに0にするか1にするかで関数の値を独立に求められるので、雰囲気、上から貪欲に求められそうに見える。 …

NIKKEI Programming Contest 2019予選 C. Different Strokes

問題 1~Nまで番号が付いたN皿の料理がある。 高橋くんがi番の料理を食べたときはA_iだけ幸福度が増し、青木さんがi番目の料理を食べたときにはB_iだけ幸福度が増す。 高橋くんから、交互に、2人とも「最終的に自分が得る幸福度の総和」-「最終的に相手が得…

ARC067 E. Grouping

問題 1からNまで番号がついたN人がいる。 どのグループも、そのグループに含まれる人数がA人以上B人以下 i人のグループの数をF_iとしたとき、F_iは0またはC以上D以下 このようなグループ分けが何通りあり得るかmod 10^9+7で求めよ。 制約 1 1 1 解法 解説、…

AGC029 B. Powers of two

問題 N個のボールがあり、i番目のボールには正の整数A_iが書かれている。 このとき、2つのボールを取り出してペアを作り、その数字の和が2ベキ(2^t)になっている場合、そのペアを取り除くことができる。 最大で何回ペアを取り除くことができるか? 制約 1 1 …

ARC066 D. Xor Sum

問題 正の整数Nが与えられる。 ここで、2つの整数0 答えは1,000,000,007のあまりを答えよ。 上記の^はビットごとの排他的論理和を表す。 制約 1 解法 まだイマイチ理解できていないところが残っているけど、とりあえずまとめ。 制約が非常に大きく、xorがビ…

yukicoder No.749 クエリ全部盛り

問題 すべての要素が0で初期化された長さNの数列{a_i}が与えられる。 Q個のクエリが与えられるので、処理せよ。 各クエリ(q,l,r,k)はqの値に応じた処理を行うこと。 q=0: k*Σ_{i=l}^r a_iのmod 10^9+7を出力 q=1: l q=2: l q=3: l q=4: l ただし、F_iはフィ…

Tenka1 Programmer Contest 2018 E. Equilateral

問題 HxWのグリッドにコインがいくつか置かれている。 このとき、相異なるコインの3つ組で「その3つのうち、どの2つのコインを取っても、それらの存在する座標の間のマンハッタン距離が一定」であるようなものの個数を求めよ。 制約 1 解法 「マンハッタン距…

AGC028 B. Removing Blocks

問題 1~Nの番号が書かれた箱が1列に並べてあり、各箱の重さは整数A_iで与えられる。 この箱を一つずつ取り除いていくことを考える。 ある箱を取り除くときのコストは、その両隣に連続している箱の重さの総和になる。 取り除き方はN!通り考えられるが、その…

yukicoder No.743 Segments on a Polygon

問題 M頂点の凸多角形の頂点同士をN本順番に線分で結ぶ。 このとき、頂点は一度線分に使われたら2度は選ばれない。 i番目に結んだ線分の頂点a_iとb_iの情報が与えられるので、追加した線分同士の交点の総数を答えよ。 (もし、ある交点が複数の線分からなる場…

ARC103 E. Tr/ee

問題 各文字は0または1の長さnの文字列sが与えられる。 n頂点の木について考えたとき、 i文字目が0なら、木からどのように辺を1つ取り除いてもサイズiの連結成分が作れない i文字目が1なら、木からある辺を1つ取り除いてサイズiの連結成分を作れる を満たす…

ARC103 D. Robot Arms

問題 m本の腕とm+1個の関節からなるロボットアームを考える。 腕iの長さはd_i。 関節iは腕iと腕i+1をつないでおり、関節1は原点に置かれ、各関節の角度は上下左右方向に指定できる。 いま、N個の平面上の整数点が与えられる。 すべての整数点にぴったり関節m…

yukicoder No.737 PopCount

問題 Nが与えられる。 を求めよ。 (popcount(i)は、iを2進数表記したときの立っているビットの数) 制約 1 解法 法則性がないか見るために、各数字のビットを書き出してみる。 1bit目が1になるものは、{1},{3},{5},{7},{9},... 2bit目が1になるものは、{2,3},…

ABC110 C. String Transformation

問題 英小文字からなる文字列S, Tがある。 Sに対して、次の操作を0回以上行える。 2つの異なる英小文字c1, c2を選び、Sに含まれるすべてのc1をc2に、c2をc1に同時に置換する 操作を行うことでSをTにすることができるか? 制約 1 Sの長さ = Tの長さ 解法 Sの…

AGC027 B. Garbage Collector

問題 数直線上にN個のゴミが落ちており、左からi番目のゴミの位置はx_iにある。 ゴミ箱は位置0にあり、掃除ロボットを動かすことですべてのゴミをゴミ箱に入れたい。掃除ロボットには以下の制約がある。 最初は位置0にいる 現在持っているゴミの数をkとする…