2020-01-01から1年間の記事一覧
これは身内のアドベントカレンダーの記事です。 始めたきっかけ 5月に徳島に帰ってから車社会に順応してしまい全然体を動かさなくなったので運動したいなあと思いました。 しかしまあまあな価格がするので諦めました。 RFAも東京はまだ品切れという話を聞き…
問題 格子状の点上に配置された飛行機が4方向のうち決められたほうに飛ぶとき、衝突するか判定する。 衝突する場合は、その中で最も早い衝突が何秒後に起こるか求める。 atcoder.jp 考察 衝突には正面衝突と直行する衝突の2種類があるので、それぞれの解の最…
問題 長さの数列に、以下の合計個のクエリを実行した結果を求める。 とをスワップ を昇順に並び替える atcoder.jp 考察 1つ目のクエリはで実行可能なので、2つ目のクエリを高速に行う方法を考える。 数列の転倒数は、1つ目のクエリでは1増減し、2つ目のクエ…
問題 atcoder.jp 考察 その他のある色についての解を、として計算する。 を通らないパスとは、色がでないノードの単純パスのうち、上に色がのノードが存在しないようなものである。 このようなノードのペアの数は色を含まない部分木のうち、色を含まないよう…
問題 人のうち、高橋くんとその他人の時刻の差（日付は気にしない）は時間である。人のうちの任意の2人の時差の最小値をの最大値を求める。 atcoder.jp 考察 より、ならばそれぞれ、その他においてである。 時差が人が2人以上（ただしのときの1人は高橋くん…
問題 長さの数列[A_1, \cdots, A__N]から個の要素を選んで部分数列を作る。 要素を選ぶときは、要素ごとに以上開ける必要がある。 辞書順で最小の数列を求める。 考察 のとき、部分列を作ることはできない。 以下、を仮定する。 同じ数字が複数あり、どちら…
問題 ある食堂では日目、日目、日目に料理が提供される。 社員それぞれについて、以下の条件で食堂に通うとき、回目に利用するまでに料理を食べる回数を求める。 初めて食堂を利用する日は日目である。 初めて食堂を利用して以降、料理が提供される日は必ず…
問題 個の敷地（番目の敷地の範囲は、コストは）がある。 座標にあるビルのコストは、その座標を含む敷地のコストの和。 軒のビルのコストを求める。 atcoder.jp 考察 考える平面が広いので、座標圧縮を行う。 以降、圧縮後の座標で考える。 あるビルのコス…
問題 王国に個の街がある。 魔王が番目の街にモンスターを匹送ると、王国にのダメージを与える。 魔王は個の拠点があり、合計のモンスターを番目の街に好きな配分で送り込める。 王国に与えられダメージの最大値を求める。 atcoder.jp 考察 次のようなdpを考…
問題 人の参加者が、個の卓でそれぞれ2人ずつ対戦する。 卓では番号と の人が対戦する。 はじめ、人の参加者は1からの番号が順番についていて、対戦が終わると番号が1増える（は1になる）。 ラウンド実施し、同じ2人が対戦するカードが存在しないような卓の…
問題 与えられた頂点の木の頂点1から頂点に、次の条件を満たすように1からの順列の番号をつける。 任意の頂点の組で、頂点と頂点の距離が3なら、かが3の倍数になる。 atcoder.jp 考察 を表す。 なら、積が3の倍数になる。なら、和が3の倍数になる。それ以外…
問題 体の所持モンスターから4匹以上、体のお助けモンスターから0匹以上選んでモンスターを合成する。 合成されたモンスターの強さは、(使用したモンスターの魔力の和)/(使用したモンスターの質量の和)で定義される。 合成できるモンスターの最大の強さを求…
問題 頂点辺の重みつき単純連結無向グラフが与えられる。 辺は頂点とを結び、重みはである。 辺からそれぞれについて、その辺を含む最小の重みの全域木を求める。 atcoder.jp 考察 与えられた連結グラフの最小の重みの全域木とその重みを求める。 この全域木…
問題 偏りのない個の6面サイコロがあり、番目のサイコロの番目の面には[A_{i,j}]が書かれている。 はじめ、好きなサイコロを1つ選んで出た目をとする。以降、次の操作を可能な限り繰り返す。 好きなサイコロを1つ選んで出た目をとする。ならとし、そうでない…
問題 グリッド上の池に葉がいくつか浮かんでいる。カエルは、同じ行/列にある葉を好きに行き来できる。葉を行き来できなくするよう、以外の除く時の最小枚数を求める。 atcoder.jp 考察 葉からたどり着ける葉の集合と、葉からたどり着ける葉の集合が互いに共…
問題 個の宝石があり、個目の宝石の価値は（負の可能性もある）である。以下の操作を0回以上したとき、残っている宝石の価値の総和の最大値を求める。 正整数を選び、の倍数の宝石を全て割る atcoder.jp 考察 各宝石を割らないグループと割るグループに分類…
問題 個のタイヤと本の木の完全マッチングの個数パターン数の偶奇を求める。 atcoder.jp 考察 完全マッチングの数え上げは、01行列のpermanent値に一致し、これはNP困難であることが知られている。行列のpermanent値は ここで、のdeterminant値を見てみると…
問題 人がいて、番目の身長はである。 「2人の番号の差の絶対値と、身長の和が等しい」ようなペアは何通りあるか。 atcoder.jp 考察 2人の番号をとする。 すると、ペアの制約は、になる。 番号を分離すると、となる。 よって各番号について、なるの数を数え…
問題 初項、公差、項数の数列がある。 十進法でを順に結合してできる数を整数で割ったあまりを求める。 atcoder.jp 考察 全ての要素が桁の整数である公差、長さの等比数列については、 とすると、 。 また、より、 で求められ、。行列の塁上は繰り返し2乗法…
問題 行列が与えられる。次の操作を行ってをに変換するとき、その途中経過であるを1つ求める。 の行ごとに好きに並び替えてにする の列ごとに好きに並び替えてにする の行ごとに好きに並び替えてにする atcoder.jp 考察 の満たすべき条件を考える。 まず、の…
問題 とがある。以下の操作を回以下行って、にできるか判定する。 を選択し、との値を入れ替える atcoder.jp 考察 が昇順であると仮定する。を昇順にソートして比較するとき、を満たさないが存在すれば、実現不可能である。以下、これは満たされていると仮定…
問題 次の条件を満たす整数行列が構築可能なら1つ求める。 行のbitwise-or/bitwise-andが 列のbitwise-or/bitwise-andが atcoder.jp 考察 bitwise-or/bitwise-andなので、桁ごとに独立して考えてよい。 桁毎に分けると、は のいずれか。 そのように考えると…
問題 段階の照明の明るさを2種類のボタンで切り替える 明るさを1つあげる。現在の明るさがなら次の明るさはになる 前もって決めた明るさにする。 最善のを決めたときに、明るさをと順に切り替えるときのボタンを押す回数の最小値を求める。 atcoder.jp 考察 …
問題 直線上を座標に並んだ体のロボットは、それぞれ次の操作が可能である。 今いる座標から、座標の空いている好きな方に移動する 座標が0以下でゴールになる。体のロボットの順位としてありえるパターンを求める。 考察 でがよりも先にゴールするとき、座…
問題 整数列が与えられ、を、 を満たすようにとる。に対し、整数列の「 の最大値」の最小値を求める。 考察 ある区間で、「[tex: C{i+1} - C_i] の最大値」の最小値を考える。また、[tex: C{i+1} - C_i]はグラフの変化率と考えることができる。 はなるべく小…
問題 十分多い金貨と枚の銀貨を持って都市1にいる。 本の線路はそれぞれ、都市間を走り、運賃は銀貨枚、時間は分かかる。 各都市の料金所で分かけて金貨1枚と銀貨枚を交換してくれる。 各都市に移動するのにかかる最小時間を求める。 atcoder.jp 考察 都市の…
問題 座標にイチゴの乗った長さのケーキに対して、回目の操作後のケーキの美しさを求める。 操作は、 * 座標にイチゴがないなら、座標にイチゴを乗せる * 座標にイチゴがあるなら、座標のイチゴを取り除く ケーキの美しさは、次の値の最大値として定義する。…
問題 頂点の有効グラフの頂点の からへ向かう辺が存在するか からへのパスが存在するか がわかっている。この条件を満たすからへ向かう辺の集合があれば求める。 atcoder.jp 考察 これらの条件を満たさないのは、 からへのパスがないが、からへの辺があり、…
問題 個の重さの異なるシャリと個の重さの異なるネタからそれぞれ2つずつ選び、重さの同じ寿司を2つ作ることができるか判定する。 atcoder.jp 考察 問題の制約から、完成する寿司の重さが高々[tex: 2\times 106]であることがわかる。重さの寿司ができるかを…
問題 人の社員をいくつかのグループに分けるときのスコアの最大値を求める。スコアはで与えられる。 atcoder.jp 考察 要素数の集合の部分集合の部分集合の列挙はでできる。 集合だけで問題を解いたときの解とする。のとき、。のとき、 で求められる。 の全て…
