問題 頂点の有効グラフの頂点の からへ向かう辺が存在するか からへのパスが存在するか がわかっている。この条件を満たすからへ向かう辺の集合があれば求める。 atcoder.jp 考察 これらの条件を満たさないのは、 からへのパスがないが、からへの辺があり、…
問題 個の重さの異なるシャリと個の重さの異なるネタからそれぞれ2つずつ選び、重さの同じ寿司を2つ作ることができるか判定する。 atcoder.jp 考察 問題の制約から、完成する寿司の重さが高々[tex: 2\times 106]であることがわかる。重さの寿司ができるかを…
問題 人の社員をいくつかのグループに分けるときのスコアの最大値を求める。スコアはで与えられる。 atcoder.jp 考察 要素数の集合の部分集合の部分集合の列挙はでできる。 集合だけで問題を解いたときの解とする。のとき、。のとき、 で求められる。 の全て…
問題 頂点のグラフのいくつかの頂点に、以下のような制約を満たすように色を塗る。 タイプ1：ある頂点に色を塗るとき、既に頂点に色が塗られてなければならない タイプ2：ある頂点に色を塗るとき、既に頂点に色が塗られていてはいけない 全ての制約を満たす…
問題 有効グラフをたどって訪れることができるノードの最大数を求める。 この操作は2回行えるが、重複したノードは一度しか数えない。 考察 強連結成分分解を行い、相互に行き来可能なノードの塊を一つのノードとみなしたDAGを考える。 DAGの各ノードのスコ…
問題 0、1でできた文字列を連結してできる長さの文字列のパターン数を求める。 同じ文字列を何度使ってもよい。 atcoder.jp 考察 NFAを用いた問題の変換 文字列の長さの最大値をとし、次のような非決定性有限オートマトンを考える。 状態 {末尾文字を示す状…
問題 aを個、bを個 、zを個使ってできる文字列のうち、同じ文字が隣合わないものの個数を求める。 atcoder.jp 考察 ここでは、同じ文字列が隣り合うことを衝突と呼ぶ。 文字目までのアルファベットを使ってできる文字列で、衝突が回発生するもののパターンを…
問題 頂点の木を書く。 木を書いている途中で、すでに書いている全ての辺が連結になるような書き方の数を求める。 atcoder.jp 考察 根付き木の根からの生やし方の数を考える。 根付き木のノード数が1のとき1通り。 根の個の子を根とする部分木のノードの数が…
問題 建物のH階部屋1から1階部屋1に移動するパターンを求める。 同じフロアでは部屋はなら隣接していて、同じ部屋は2回通れない。 フロア間は同じ番号の部屋へ一方方向に降りるだけ。 atcoder.jp 考察 フロア内の移動 任意の部屋からスタートし、同じ部屋を…
問題 円の集合のうち、を満たすような円の列の最大の長さKを求める。 ここで、とは円がstrictlyに円の内部にあることを意味する。 atcoder.jp 考察 円の左右の端の座標をとすると、条件を満たす円の列は、 を満たす。 すなわち、になるよう円の列をソートす…
問題 直線上に並んだターゲット全てにボールを当てるまでの回数の期待値を求める。 ボールを狙った座標とその両隣それぞれに1/3の確率でボールが飛んでいく。 atcoder.jp 考察 なので、dp[s] = (sが1の座標にターゲットが残っているときの期待値)とする。 に…
問題 iとwからなる文字列から、連続するiwiを抜き取れる回数の最大値を求める問題。 文字列の途中から抜き出すと、その左右の文字列が連結され、操作を続けられる。 atcoder.jp 考察 文字列の区間の部分文字列をと表記する。からiwiを取り出せる回数の最大値…
問題 与えられた文字列の空文字列を除く部分文字列のうち、辞書順でK番目のものを求める。 ただし、出現場所の異なる部分文字列でも、文字列として同一なら区別しない。 atcoder.jp 考察 辞書順に並べたK番目を求めるので、先頭から文字を決定したい。 先頭…
GWにElmの勉強をしたのでそのまとめ つくったもの ポケモンの育成時のパラメータからバトルに使うステータスを計算するアプリケーション。 ポケモンの名前で検索して育成の数値を入力すると最終的なパラメータが計算される。 https://tnyo43.github.io/Pokem…
2019年2月17日に東京ドームホテルで行われた全国統一プログラミング王決定戦の本戦イベントに参加してきました。 主催、共催は日本経済新聞社とAtCoder。 僕は201~500位での参加なのでトークセッション、表彰式、エキシビション、懇親会に参加した。 はじま…
Baby-Step Giant-Stepアルゴリズムのまとめ 概要 巡回群上の離散対数問題を高速に解くアルゴリズム。 本記事は（pは素数）を満たすxを求める方法を考える。 アルゴリズム あると決定する なるiについて、を計算する。 なるjについて、を計算する。 解xが存在…
2018.10.13 21:00~のAtCoder AGC028に参加 結果はABの2完。 A - Two Abbreviations与えられた2つの文字列を元に、条件を満たす文字列の最小の長さを出力する問題。 条件は 答えの文字列の長さはそれぞれの文字列の長さの整数倍 答えの文字列を個に区切った個…
計算モデル論の授業で学習した「原始帰納関数」を忘れないうちにメモ 初期関数初期関数は以下の3つで定義される。 ：後者関数（successorは後継者という意味の英語、次の自然数を返す） ：定数ゼロ関数（常にゼロを返す） ：射影関数（n個の引数をとり、i個…
2018.10.06 21:00~のAtCoder ABC112に参加しました。 結果はDを1WAで全完でした。47分かかってしまったのでもっと早くしたいです。 A - Programming Education 1つ目の入力が1か2かで分岐。出題形式がちょっと珍しい気がしました。 B - Time Limit Exceeded …
