phyllo’s algorithm note

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

ABC155 F. Perils in Parallel

問題 数直線上にN個の爆弾が仕掛けられており、i番目の爆弾はA_iの位置で、スイッチの状態がB_i(OFFは0、ONは1)で与えられる。 制御装置にはM本のコードがあり、j番目のコードを切ると、L_j以上R_j以下の位置にある爆弾のスイッチの状態が入れ替わる。 切る…

ABC155 E. Payment

問題 AtCoder王国では、価値が1,10,100,1000,...,10^(10^100)の紙幣になっている。 今、商品の価値がNであるような商品を買いたい。 各紙幣は十分な枚数を持っているとした場合、この商品を買うために払う枚数とおつりの枚数を適切に最小化した場合、最小で…

ABC155 D. Pairs

問題 N個の整数A_iが与えられる。 このうち、2つを選んだ積の組合せをすべて考えると、これはN*(N-1)/2個できる。 小さい方からK番目の積が何になるか答えよ。 制約 2 1 -10^9 解法 積を小さい方から並べた数列Bを考える。(これは実際には列挙できない) Bの…

ABC153 F. Silver Fox vs Monster

問題 N体のモンスターが一列に並んでいる。 i番目のモンスターは、座標x_iにいて、体力がh_iである。今、爆弾を座標xに落とすと、x-D以上x+D以下の範囲にいるモンスターにダメージAを与えることができる。 すべてのモンスターの体力を0以下にするために必要…

ABC133 F. Colorful Tree

問題 N個の頂点からなる木がある。 各辺iは、頂点a_iとb_iをつないでおり、1~N-1の整数で表される色c_iと、辺の長さd_iが割り当てられている。 このとき、以下のQ個の問いに答えよ。 「問いj: 色x_jのすべての辺の長さをy_jに変更したと仮定して、二頂点u_j…

ABC132 F. Small Products

問題 正の整数K個を一列に並べたもので、隣接するどの2つの整数の積もN以下であるようなものの個数を求めよ。 答えは10^9+7のあまりで求めよ。 制約 1 2 解放 計算量を無視して考えると、 dp[i][j] := i番目の整数がjだった場合の通り数 のように考えられる…

yukicoder No.973 余興

問題 N個のシュークリームが一列に並べてあり、左からi番目のシュークリームはa_iキロカロリーである。 AさんとBさんは、Aさんから始めて交互に以下のいずれかの操作を繰り返す。 左側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを…

ABC152 F. Tree and Constraints

問題 N個の頂点からなる木が与えられる。この木の辺を白か黒で塗ることを考える。 M個の制約が与えられ、i番目の制約は「2つの頂点u_i, v_iのパス上の辺には黒色の辺が1つ以上存在しなければならない」となっている。M個すべての制約を満たすような塗り方の…

ABC151 F. Enclose All

問題 平面上のN個の点が与えられる。 これらすべてを内部または周上に含む円の半径の最小値を求めよ。 制約 2 0 与えられる点はすべて異なる 解法 いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか?をチェッ…

ABC150 D. Semi Common Multiple

問題 長さNの偶数の整数からなる正数列Aと整数Mが与えられる。 任意のk(1X = A_k * (p + 0.5)を満たす負でない整数pが存在する1以上M以下の整数のうち、Aの半公倍数の個数を求めよ。 制約 1 1 2 A_iは偶数 解法 Xについて考える。 0.5を1/2として整理すると…

ABC131 F. Must Be Rectangular!

問題 2次元座標にN個の点が与えられる。 このとき、「座標(a,b),(a,d),(c,b),(c,d)のうちちょうど3箇所に点が存在するようなa,b,c,d(a!=c, b!=d)を選んで、残りの1箇所に点を追加する」という操作を繰り返す。 この操作回数の最大値を求めよ。 制約 1 1 与え…

ABC148 F. Playing Tag on Tree

問題 N頂点の木が与えられる。 最初、高橋くんは頂点u、青木くんは頂点vにいる。2人は以下の手順で鬼ごっこをする。 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、高橋くんは隣接頂点のどれかに移動 高橋くんと青木くんが同じ位置にいるな…

ABC148 E. Double Factorial

問題 0以上の整数nに対し、関数f(n)を以下のように定める。 f(n) = 1 (n f(n) = n*f(n-2) (n>=2) 整数Nが与えられる時、f(N)の10進数表記の末尾の0の個数を求めよ。 制約 0 解法 偶数と奇数をそれぞれ考えてみる。奇数は1*3*5*...と奇数の掛け算なので、答え…

ABC129 F. Takahashi's Basics in Education and Learning

問題 長さLの等差数列があり、初項はA、公差はBで与えられる。 この数列の項を順につなげてできる整数を考える。 例えば、3,7,11,15,19という数列の場合は、37111519という整数になる。 この整数をMで割ったあまりを答えよ。 制約 1 2 数列の要素はすべて10^…

三井住友信託銀行プログラミングコンテスト2019 F. Interval Running

問題 高橋くんと青木くんは、直線上を同じスタート地点から走り出す。 同じ方向に向かって、 高橋くんは、T1分を分速A1メートル、次のT2分を分速A2メートル、これを交互に繰り返す 青木くんは、T1分を分速B1メートル、次のT2分を分速B2メートル、これを交互…

三井住友信託銀行プログラミングコンテスト2019 E. Colorful Hats 2

問題 N人が一列に並んでおり、各人は赤、青、緑いずれかの帽子をかぶっている。 そして、左からi番目の人は「自分より左で、自分と同じ色の帽子をかぶっている人はAi人いる」と言っている情報が与えられる。この情報に基づいた場合、帽子の色の組み合わせと…

ABC127 F. Absolute Minima

問題 関数f(x)があり、はじめはf(x)=0として与えられる。 Q個のクエリが与えられ、 更新クエリの場合は、f(x) 求値クエリの場合は、f(x)の最小値とその時のxを出力 を行え。 制約 1 -10^9 1番目のクエリは更新クエリ 解法 与えられた問題は、「min Σ |x-a_i|…

ABC146. E. Rem of Sum is Num

問題 長さNの正整数列A_iと正の整数Kが与えられる。 このとき、Aの空でない連続する部分列で、「要素の和のmod Kと要素数が等しくなるものの数」を求めよ。 ただし、位置が異なる場合は区別する。 制約 1 1 1 解法 問題を式で表現すると、(Σ_{i=l}^{r} Ai) m…

第一回日本最強プログラマー学生選手権決勝 A. Equal Weight

問題 N個のシャリAとM個のネタBがあり、シャリiの重さはAi、ネタjの重さはBjで与えられる。 ここで、寿司の握りはシャリとネタ1つずつの組み合わせで作ることができ、同じ重さの寿司を2つ作りたい。 これが可能かどうか判定し、可能な場合は組み合わせのイン…

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が対…