問題 個のスポーツに対して人がそれぞれ1つだけに参加する。番目の人の参加優先順位がで表されるとき、実施するスポーツを適切に選択して最も多くの人が参加するスポーツの参加人数を最小化せよ。 解法 全てのスポーツを実施する状況から考える。このとき選…

問題 個のマスが一列に並んでおり、一番左には整数、一番右にはが書き込まれているとする。どの隣接マスについても書かれている整数の差が以上以下であるように残りのマスを埋めることができるかどうか判定せよ。 解法 から]または]のような操作を回行ったと…

問題 頂点の木が与えられ、最初は全ての辺にが書き込まれている。頂点を結ぶパス上の全ての辺に対して書かれている数をするクエリ個あり、最終的に書かれた数が全て偶数になったとする。このような木が存在するかどうかを判定せよ。 解法 (0-originとして)頂…

A問題 2倍していきながら範囲内に被る数を数えていけば十分間に合う。 #include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { ll C, D; cin >> C >> D; ll ans = 0; for (ll i = 0;; i++) { ll low = 140 * pow(2, i); ll high = …

問題 頂点辺の連結な単純無向グラフについて、 2個以上の頂点を通る 同じ頂点を2度以上通らない パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる という条件を満たすパスを1つ見つけて出力せよ。 解法 1時間半ほど考えてもさっぱ…

開発中の将棋ソフトについて、評価関数部分以外の性能を強豪ソフトと比較するため、評価関数パラメータを読み込む機能を実装した。 AperyとはBonaPieceにおいて持ち駒0枚に数字を割り振っているかどうかや、盤上の駒を示す順番が角→馬→飛車→竜か角→飛車→馬→…

問題 からまでの番号がついた個の頂点と本の辺からなる単純無向グラフが与えられる。全ての頂点ははじめ色で塗られているとし、次のような色を塗る操作を回行う。回目の操作では頂点から距離以内にあるような頂点たち全ての色を色で上書きする。回の操作後に…

問題 匹の生き物がそれぞれ大きさを持っており、自分の2倍以下であるような他の生き物を吸収できるとする。吸収したとき生き物の大きさは吸収元と吸収先の大きさの和となる。吸収を繰り返して最終的に1匹になるとするとき、残った生き物としてあり得る種類の…

問題 個の箱が円環状に並んでおり、番目の箱には個の石が入っている。「を一つ定めからまでの各に対して番目の箱から石をちょうど個取り除く」という操作を繰り返したとき全ての石を取り除くことは可能か判定せよ。 解答 1時間考えてもわからなかったので解…

問題 人でトーナメントを行い1番目の人が優勝した。2から番目の人が誰に負けたかを与えるのでトーナメントの深さとして最小の値を求めよ。 解法 番目の人がの人に勝ったとして、それぞれの対戦カードの下に位置する部分トーナメント木の深さをとすると、これ…

問題 整数が書かれたマスが一列に個並んでおり最初は全て白く塗られている。連続した個のマスを黒か白に上書きしていく操作を好きなだけ繰り返して、黒く塗られたマスにある数字の総和を最大化せよ。 答え 1時間かけても解けなかったので解説を読んだ。 操作…

問題 長さの順列が与えられるのでを求めよ。 解答 公式のものとほぼ同じなので省略。 思考過程 まず制約を見て、が大きいのでとかでないとダメだなというのを把握。 順列というのが気になるところで、要素の値をベースに考えるということが頭をよぎる。ある…

SRM500台を埋めていくという話らしいです。500は書くのを忘れたので501から。 問題 nA回paramA / 1000を足すのとnB回paramB / 1000をかけるのを好きな順番でやって値を最大化する。 考察 サンプルをパッと見た感じで全部足してからかけるか、全部かけてから…

チーム紹介 ICPC2018国内予選に、CatKOderというチームの一員として参加しました。メンバーは次の通りです。 今年のICPC、@Cmer_pro @AlbicillaT @kaitei_shogiの3人でチームCatKOderとして参加します！— albicilla(あるびん) (@AlbicillaT) 2018年7月6日 Ca…