phyllo’s algorithm note

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

ABC141 F. Xor Sum 3

問題 N個の非負整数A_iが与えられる。 これを1個以上が属する2つのグループにわける。 各グループ内の整数のすべてのxorを取ったものの和を最大化するような選び方をした場合、その最大値を返せ。 制約 2 0 解法 すべての与えられた整数のxorを取ったものをs…

ABC139 F. Engines

問題 N個の2次元ベクトルが与えられる。 ここからいくつか選んだ和のベクトルの大きさの最大値を求めよ。 制約 1 -1,000,000 解法 答えとなるベクトルの向きを固定して考える。 このとき、この向きに寄与するベクトルは、その向きの成分が正となるベクトル(±…

ABC137 E. Coins Respawn

問題 1からNまで番号がついたN頂点M辺の有向グラフが与えられる。 頂点1から頂点Nまで辺を辿っていくことを考える。 辺iは通過するのに1分かかり、通るたびにコインがCi枚もらえる。 頂点Nにたどり着いておいてあるボタンを押すと「それまで回収したコインの…

AGC036 A. Triangle

問題 整数Sが与えられる。以下の条件をすべて満たす6つの整数X1,Y1,X2,Y2,X3,Y3を1組求めよ。 0 二次元平面上の3点(X1, Y1), (X2, Y2), (X3, Y3)を頂点とする三角形の面積がS/2 制約 1 解法 変数が多いので、1点を固定して考える。(X1, Y1) = (0, 0)とする。…

ABC134 F. Permutation Oddness

問題 1からNまでの順列pの「奇妙さ」を「Σ_{i=1}^N |i - p_i|」と定義する。 奇妙さがkであるような順列の個数の10^9+7で割った余りを求めよ。 制約 1 0 解法 「1からNを並べたもの」と「順列p」のペアを考える。 順列pでの数字を線でつないで表現すると以下…

yukicoder No.848 なかよし旅行

問題 N個の町がM本の道でつながっており、道の移動にかかる時間が与えられる。 今、2人が町1にいるが、T分以内に町Pと町Qを回って町1に戻ってきていなければならない。 町Pと町Qは2人のうちどちらか1人でも回ればよい。 ただし、道の途中で引き返すような行…

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!通り考えられるが、その…