yukicoder.me のもとで、 時間で解きます。 解法 [1] 解法 を、 回のイベントの直後に退場となった選手の人数がちょうど 人であるような確率とします。 回のイベントの直後に退場となった選手の人数がちょうど 人であるとき、今までの 回のイエローカードの…

解法 [1] グリッドの問題への言い換え 各 について、商品 を購入できる一般人の人数を、商品 を購入できる MMA 部員の人数を とします。また、一般人の人数に を加えた値を 、MMA 部員の人数に を加えた値を とおくと、以下のような問題に帰着されます。 の…

atcoder.jp 解法 [1] 条件の言い換え 対称性により、不等号の向きをすべて反転させても求める確率は変わりません。後の計算がやりやすくなるので、不等号の向きをすべて反転させて考えます。長さ の実数列 が以下の条件を満たすとき、 は 上の列であると呼ぶ…

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 22 日目の記事です。 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2154 解法 与えられた多角形の内部を 、頂点を反時計回りに とします。また、 であるとします。 辺 からのマンハッタ…

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 8 日目の記事です。 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2394 問題概要 頂点の凸と限らない多角形が与えられる。この多角形の内部または周上に完全に含まれる線分の長さの最大…

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 1 日目の記事です。 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1394 問題概要 頂点の凸多角形が与えられる。この多角形の辺上に端点があり、多角形の面積を 等分する線分の長さとして…

https://codeforces.com/contest/1761/problem/D 問題概要 非負整数 に対し 進数で を計算したときの繰り上がりの回数を とおく。 整数の組 であって、 であるようなものの個数を で割った余りを求めよ。 解法 を以下のように定義します。 整数 であって、 …

yukicoder.me 解法 木の辺に値が書かれていて、最初はすべて が書かれているとします。 について、 パスに含まれている辺にすべて を加算すると、 以上の数が書かれた辺の重みの合計が答えです。 が書かれた辺の重みの合計を求め、全体から引くことで求めら…

Nachia さんの考えたアルゴリズムを実装しました。 www.mathenachia.blog 注意 簡単なランダムチェッカーを通しています。 時間計算量については確認していませんが、ACPC 2021 Day2 J を AC することはできました。 下のコードはグラフが入力された場合に答…

日時 出来事 2038/01/09 12:14 practice contest が終了する。 2728/05/29 22:44 AtCoder Library Practice Contest の順位表が凍結される。 3020/02/29 21:00 AGC042 が開始する。 3020/03/01 01:00 AGC042 が終了する。 3020/09/27 22:31 AtCoder Library …

jコンテストページ official.contest.yandex.ru 問題概要 問題 A: A Hero Named Magnus 実行時間制限: 1 秒 / メモリ制限: 512 Mb ( は奇数) 回試合を行うことを考える。 試合目から 試合目までは の確率で試合に勝ち、 試合目以降は必ず試合に勝てるとき、 …

コンテストページ official.contest.yandex.ru 問題概要 問題 1: Polesov and Work 実行時間制限: 3 秒 / メモリ制限: 256 Mb 整数 と正の整数 が与えられる。円 内の格子点 に対し、 の最大値を求めよ。ただし、 個のテストケースが与えられるので、すべて…

atcoder.jp 公式解説とは異なる解法で解きました。 解法 荷物の重さの合計が体力の合計より大きいとき答えは明らかに No なので、以後、荷物の重さの合計は体力の合計以下であるとします。このとき、重さ 以上の荷物をすべて割り当てることができれば、重さ …

のいみさんが言っていたので 誰か参加記まとめて— のいみ (@noimi_kyopro) 2021年11月6日 https://twitter.com/season1618/status/1456599426705682437 https://twitter.com/mugen_1337/status/1456609488832655366 https://twitter.com/noimi_kyopro/status…

コンテストページ official.contest.yandex.ru 問題概要 A 問題: Automatic Sprayer 2 実行時間制限: 2 秒 / メモリ制限: 1 GB の各成分が非負整数の行列 がある。 から、 の行列 を以下のように作った。 が与えられるので、 としてありうるものを つ出力せ…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja 解法 ネットワークはマシンを頂点としケーブルの太さを各辺の重みとする木と考えます。 add クエリが扱いにくいので、各頂点 に対し整数 を辺 の重みが常に となるようにすると、ad…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2733 公式解説とは異なる解法で解きました。 問題概要 個の同じ大きさの立方体で構成された幅 、高さ 、奥行き の立方体がある。 を満たす各 について、左から 番目・下から 番目・前から 番目の…

コンテストページ ac.nowcoder.com 問題概要 A 問題: Away from College (問題文を読んでいません 原文を読んでください) B 問題: Boxes 実行時間制限: 1 秒 / メモリ制限: 262144 KB 個の箱があり、それぞれの箱には黒いボールまたは白いボールがそれぞれ …

コンテストページ ac.nowcoder.com 問題概要 A 問題: Course 実行時間制限: 3 秒 / メモリ制限: 262144 KB 頂点の根付き木と長さ の数列 と が与えられる。 個のクエリに答えよ。 番目のクエリでは整数 が与えられるので、長さ の非負整数の列 で、以下の条…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1198&lang=ja 解法 のうち一方のみが含まれる円が 1 つ以上存在する場合、 と をその円と交差しないように結ぶことはできないので、答えは明らかに NO となります。 がともに 1 個以上の円に含ま…

APIO2021 に参加しました。 競技 Hexagonal Territory を読む。六角グリッドでやばそう。とりあえず Territory (難易度 11) を思い出すがよくわからない。9 点の部分点は数学で簡単に取れそうなので取る。Rainforest Jumps を読む。4 点が自明なので取る。8 …

atcoder.jp 公式解説とは異なる方法で解きました。 解法 操作を一回もしないときの の値を求めておき、 とします。 または のときの見栄えの悪さの値は、 との差分を考えることで合計 で求めることができます。よって、 のときの見栄えの悪さの最小値を計算…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1352 問題概要 座標平面上に半径 の円形のロボットがあり、その中心を原点からある点に移動させたい。ただし、ロボットと重なってはならない点が 個指定される。ロボットの最短移動距離を求めよ…

codeforces.com 想定解とは異なると思われる解法で解きました。 問題概要 (インタラクティブ問題) の順列 がある。この順列を質問をして当てたい。質問では、整数 を質問し、 ならば の値を、 ならば の値を知ることができる。 質問を 回以下行い、順列 を答…

poj.org 問題概要 10 階建ての建物があり、各階には 10 個の部屋があります。各部屋には部屋番号が定められており、x 階の y 番目の部屋 (ただし x, y は 1-indexed) の部屋番号は xxyy (x または y が一桁の場合は前に 0 を付ける) です。 この建物に何人か…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp 解法 2 台のロボットの距離が 未満になったり 以上になったりすることが発生する時刻をすべて列挙することを考えます。 ロボットの組を全探索します。ロボットが 2 台とも動いてい…

poj.org 問題概要 座標平面上があり、原点にはランプが置かれています。 また、 頂点の多角形があり、その各辺に沿って高さ のフェンスが個置かれています。多角形の 番目の頂点の座標は点 です。フェンスはランプの光を反射させたり通過させたりすることは…

poj.org 問題概要 縦 マス、横 マスの二次元グリッドがある。グリッドの左から 列目、下から 行目のマスをマス と呼ぶ。 マス から始めて隣接したマスに移動することを何度か繰り返した。移動の経路が文字列 として与えられる。 の 文字目が U, D, L, R であ…

codeforces.com 公式解説と異なる方法で解きました。 問題概要 数列 を漸化式 で定めます。 整数 が与えられるので、 を で割った余りを出力してください。 (元の問題文から文字を大文字にしています) 制約 解法 制約から、 などの行列についての行列累乗に…

UTPC 2020 - AtCoder UTPC 2020 に Nachia さんとチームを組んで参加しました。 A 問題 序盤は A 問題は任せて B 以降の問題文をすべて読むと決めたので、読みませんでした。Nachia さんが通してくれました。 H 問題 何人かが通しているので、少し考えるとう…