問題 N頂点の木が与えられる。 最初、高橋くんは頂点u、青木くんは頂点vにいる。2人は以下の手順で鬼ごっこをする。 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、高橋くんは隣接頂点のどれかに移動 高橋くんと青木くんが同じ位置にいるな…
問題 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*...と奇数の掛け算なので、答え…
問題 長さLの等差数列があり、初項はA、公差はBで与えられる。 この数列の項を順につなげてできる整数を考える。 例えば、3,7,11,15,19という数列の場合は、37111519という整数になる。 この整数をMで割ったあまりを答えよ。 制約 1 2 数列の要素はすべて10^…
問題 高橋くんと青木くんは、直線上を同じスタート地点から走り出す。 同じ方向に向かって、 高橋くんは、T1分を分速A1メートル、次のT2分を分速A2メートル、これを交互に繰り返す 青木くんは、T1分を分速B1メートル、次のT2分を分速B2メートル、これを交互…
問題 N人が一列に並んでおり、各人は赤、青、緑いずれかの帽子をかぶっている。 そして、左からi番目の人は「自分より左で、自分と同じ色の帽子をかぶっている人はAi人いる」と言っている情報が与えられる。この情報に基づいた場合、帽子の色の組み合わせと…
問題 関数f(x)があり、はじめはf(x)=0として与えられる。 Q個のクエリが与えられ、 更新クエリの場合は、f(x) 求値クエリの場合は、f(x)の最小値とその時のxを出力 を行え。 制約 1 -10^9 1番目のクエリは更新クエリ 解法 与えられた問題は、「min Σ |x-a_i|…
問題 長さNの正整数列A_iと正の整数Kが与えられる。 このとき、Aの空でない連続する部分列で、「要素の和のmod Kと要素数が等しくなるものの数」を求めよ。 ただし、位置が異なる場合は区別する。 制約 1 1 1 解法 問題を式で表現すると、(Σ_{i=l}^{r} Ai) m…
問題 N個のシャリAとM個のネタBがあり、シャリiの重さはAi、ネタjの重さはBjで与えられる。 ここで、寿司の握りはシャリとネタ1つずつの組み合わせで作ることができ、同じ重さの寿司を2つ作りたい。 これが可能かどうか判定し、可能な場合は組み合わせのイン…
問題 N個の非負整数A_iが与えられる。 これを1個以上が属する2つのグループにわける。 各グループ内の整数のすべてのxorを取ったものの和を最大化するような選び方をした場合、その最大値を返せ。 制約 2 0 解法 すべての与えられた整数のxorを取ったものをs…
問題 N個の2次元ベクトルが与えられる。 ここからいくつか選んだ和のベクトルの大きさの最大値を求めよ。 制約 1 -1,000,000 解法 答えとなるベクトルの向きを固定して考える。 このとき、この向きに寄与するベクトルは、その向きの成分が正となるベクトル(±…
問題 1からNまで番号がついたN頂点M辺の有向グラフが与えられる。 頂点1から頂点Nまで辺を辿っていくことを考える。 辺iは通過するのに1分かかり、通るたびにコインがCi枚もらえる。 頂点Nにたどり着いておいてあるボタンを押すと「それまで回収したコインの…
問題 整数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)とする。…
問題 1からNまでの順列pの「奇妙さ」を「Σ_{i=1}^N |i - p_i|」と定義する。 奇妙さがkであるような順列の個数の10^9+7で割った余りを求めよ。 制約 1 0 解法 「1からNを並べたもの」と「順列p」のペアを考える。 順列pでの数字を線でつないで表現すると以下…
問題 N個の町がM本の道でつながっており、道の移動にかかる時間が与えられる。 今、2人が町1にいるが、T分以内に町Pと町Qを回って町1に戻ってきていなければならない。 町Pと町Qは2人のうちどちらか1人でも回ればよい。 ただし、道の途中で引き返すような行…
問題 高橋くんと青木くんが、どちらかが合計N回勝つまでゲームを繰り返す。 1回のゲームでは、高橋くんが勝つ確率はA%、青木くんが勝つ確率はB%、引き分けになる確率はC%である。ゲームが行われる回数の期待値を出力せよ。 ただし、期待値は小数ではなく、互…
問題 N個の蓮が一列に並んでおり、0～N-1まで番号がついている。 最初、0の蓮におり、以下の手順に従ってゲームを行う。1. 正の整数A, Bを決める。得点は最初は0。 2. 現在の位置xとして、y=x+Aとする。xの蓮を消してyに移動する このとき、y=N-1ならゲーム…
問題 東西に無限に続く1本の大通りがあり、数直線とみなせる。 大通りでN回の工事が行われ、i番目の道路工事はSi-0.5からTi-0.5の時刻にXi地点を通行止めにする。 Q人の人が座標0におり、i番目の人は時刻Diで出発し、速度1で進む。 しかし、工事中の通行止め…
問題 整数のペアがN組あり、i番目の整数のペアは(Ai, Bi)で与えられる。 すぬけくんは各ペアからちょうど1つずつ整数を選んで、選んだN個の整数の最大公約数として考えられる最大値が何になるか知りたい。 制約 1 1 解法 最初にA1かB1の約数の集合を考えると…
問題 N種類の食べ物があり、食べ物iの体力がAi、攻撃力がBiで与えられる。 この食べ物同士を戦わせ、最強の食べ物を決めたい。最強の食べ物は、以下のような対戦を行ったとき、どの他の食べ物と戦っても勝利できるような食べ物とする。食べ物iと食べ物jが対…
問題 N*Mのマス目のKマスに1つずつ駒を置くことを考える。 ここで、K個の駒が(x1,y1), ...., (xK,yK)と置かれるときの配置コストを Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|) とする。 駒のすべての配置の仕方のコストを考えたとき、その配置コストの…
問題 以下の条件を満たす長さ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…
0完だった。。。(点数分布的にAのlargeは通さないとACDのsmallだけでは無理そうだったので時間をかけてたけどsmallすら通せなかった・・・) 問題 CodiumとJamariumという新しい元素を研究しており、これらの原子量に関する統計を調べたいと思っている。 過去…
問題 N種類の異なる武器が2つずつ並べてある。 あなたは審判で、まず(L,R)の範囲を指定する。 対戦者のCharlesとDelilaは、その範囲内の武器の一つを選んで対戦を行う。 また、それぞれ人の武器の熟練度がCiおよびDiで与えられ、それぞれ範囲内で一番熟練度…
問題 「X-day ring」というものがあり、これは、X日ごとに分裂し、2倍の個数になるリングである。 最初は、1-day ringから6-day ringまでの6種類のリングがそれぞれ何個か(0個以上100個以下)ある。今、1日目から500日目までのいずれかの日でのリングの合計数…
問題 グリッドがあり、各交差点は0からQまでの番号の組で表現できる。 今、P人の人が交差点に立っており、それぞれ、東西南北のいずれか一方を向いている。 各人は、向いている向きの方向に1交差点進んだ領域のどこかの交差点に用事があることがわかっている…
問題 N個の整数aiが与えられる。 この整数に赤、緑、青のいずれかの色を塗る。 このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。 「それぞれの色で塗った整数の和をR,G,Bとするとき、三辺の長さがそれぞれR,G,Bであ…
問題 N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。 ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。 マスの外側に移動させられたゴーレムは消滅する。 Q回の呪文…
概要 1週間マラソンはきつい。 最終順位は、20位(58人参加)で、結構良かった。 問題 W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。 このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場…
概要 第3回RCO日本橋ハーフマラソン予選に参加してみた。 atcoder.jp結果は、A問題が102位、B問題が45位の総合67位でした。(結構善戦できたと思う) 問題 A. ツーリストXの旅行計画 N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考…
問題 数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。 このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後…
