全体的な反省 考えていた解法はサンプルできちんと試そう A,B問題 今回は特になし。あっさり解けたと思う。 C問題 閉路検出の問題。Cに配置されていることを考えると再帰無しでも解けそうだが、あんまり書いたこと再帰で解いた。 サイクルの部分だけ出力する…
問題 を求めよ。 ただし、 である 考えてたこと ・二重和なので、一度全体の和を求めて、いい感じに調整して回計算するのだろうなという予測を立てる ・否定論理積の性質から、の値は0または1のどちらかである。 ・ここで、 は、先程の式から一つ前の値と文…
はじめに 私生活があまりに忙しくなりましたが、なんとか生きてます。 最近またABCに出始めたのですが、ボコボコにされているのでクイック反省会をブログでやりたいと思います 全体的な反省 問題文をちゃんと読もう Cぐらいまで速解き失敗するとゴタゴタにな…
2023年苦手なジャンルを克服しよう数え上げ編です。 問題 頂点の完全グラフが与えられる。このうち、本の辺は使えない。 個のパスのうち、始点と終点が1で終わるパスの数を答えよ。atcoder.jp 解法/ 考えてたこと 解説ACしたが思いつけそうな問題だった。反…
2023年苦手ジャンルがんばって埋めようシリーズ期待値編です。 問題 atcoder.jp 考えてたこと サンプル2を導出するのに時間がかかって困った。ゲームも組み合わさってる用に見えてかなり時間がかかってしまった。 まずは容易に導出することができる。次のの…
問題 頂点辺の単純無向グラフが与えられる。頂点1から頂点に、頂点からにそれぞれコマを移動する時の最短ステップ数を答えよ。atcoder.jp 解法 すんなりと解けた。一回の動作で2つの頂点が移動するという点が厄介かもしれないが、拡張グラフ上でのDijkstraの…
2023年は数え上げとか期待値とか苦手分野をやっていきます。 問題 以下の条件を満たしながら個のブロックを個の色での塗り方が何通り有るか求めよ。 隣り合うブロックの組であって同じ色で塗られている組は、 組以下である。 atcoder.jp 解法 条件の部分を言…
一応このブログは雑記を書く場所なんだけど、ほとんど競プロの自己満足解説記事になっているので、たまには箸休めとしてこういうのもいいかなと思って。年末だし、後になって読み返すと面白い気もしますしね。ネタバレは書いてません。 それでは行きましょう…
はじめに この記事はNAIST Advent Calendar 2022 の 18日目 AtCoder problemsで300日ストリークを続けてみた の記事です。 みなさんプログラムを書いてますか？ 毎日なにかしらプログラムを書いていたいタイプなんですが、実際のところは調べる時間が必要だ…
これは好きなタイプの問題でした。かなり。 問題 頂点の木が与えられる。以下のクエリを処理したのち、各頂点の情報を出力せよ。 のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。 のとき : 頂点 から…
問題 個のボールが与えられる。ボールは、座標軸上に位置し、その色はである。 座標軸を移動しながらボールの色が広義単調増加となるように回収する時、移動するコストを最小化せよ。 atcoder.jp 考察 色ごとにDPしたくなるが、各色と次の色の間ですべての推…
11月一度もブログ投稿してないけど、問題自他はこまめに解いてました。 思い出すシリーズです。 問題 長さの2つの数列が与えられる。 個のクエリに答えよ。 : の先頭個の値の集合との先頭個の値の集合が等しいかどうかを答えよ atcoder.jp 解法 クエリにオン…
問題 個の数列が与えられる. を求めよ.atcoder.jp 解法 問題文から上記の言い換えは比較的容易.後はこれを埋めて行けば良い. これが茶diffと聞いてインフレもここまで来たか…と思ったが、実際は通るらしい.これでは面白く無いので、解法を考えてみよう.区間…
問題 頂点辺の連結な単純無効グラフが与えられる。グラフ上の頂点に向かう単純パスが一意に定まるか判定せよatcoder.jp 解法 頂点辺というのがポイント。辺の数がだった場合、任意の二つの頂点を結ぶ単純パスは一意に定まる。言い換えると、この場合は木にな…
問題 長さの整数列が与えられる． を満たすすべての整数について，を求め，その最小値を答えよ atcoder.jp 解法 解法1 なので，個の数字をstd::setで管理すれば解けるSubmission #33224842 - AtCoder Beginner Contest 194 解法2 上記の解法では，更新部分は…
問題 個の区間が与えられる。個の区間が重複していた数を答えよ。 atcoder.jp 解法 まず最も簡単な愚直な解法を考えてみる。 の区間をすべて全探索してしまい、かぶっている区間の数を数え上げて、最後にそれを答えとしてしまえば良い。 この解法はTLEとなる…
問題 長さ の数列が与えられる。以下の操作を回繰り返す。 ・ 最初の数をとする。 に を追加する。 を答えよ 解法 愚直にシミュレーションするのは自明にTLEとなる。 よく考えると、追加されるのはで割ったあまりを添え字とする数列である。この数は、たかだ…
注意事項 はじめに NAISTの環境（物理） アクセスといろいろな環境とか 食堂・コンビニ 図書館 NAISTでの環境（研究とか） 学校での生活 授業 チューター 中間発表 研究室 研究室の環境（物理） 研究室の環境(not 物理) 私生活 コロナウイルスによる諸々 就…
問題 atcoder.jp 解法の前のお勉強 辺のコストの持ち方以外は難しくない。制約的に、Dijkstra法を用いることで解ける。さて、問題はコストが負になりうるという点である。 Dijkstraのアルゴリズムは、負の辺があると動作しない。ならば、負の辺を消してしま…
問題 大事なところだけ抜粋すると、 を個の2つの組に分ける通り数答えよ。atcoder.jp 解法 2つの組というところがミソで、うまく数え上げることができなかった。 例えば、{ (1,2), (3,4) } と{ (2,1), (3,4)} は同じになる。 これを回避するには、各要素の右…
問題 長さの数列が与えられる。 の連続する部分列を一つ選び、これを一度flipする。 スコアをに含まれる1の個数とするとき、の取りうる値が何通りあるか求めよ。atcoder.jp 考えたこと ・答えの候補はたかだか程度なので、全部試せる ・最大値さえわかれば良…
問題 atcoder.jp 解説 尺取法で解ける．いつもサボるのでちゃんと書いておこうともう． 半開区間( )で区間を管理しながら行う． 尺取法は，ある条件を満たす区間をできるだけ伸ばして，条件が合わなくなったら左の区間を縮めていく． 更新のタイミングが（個…
問題 atcoder.jp 考えたこと おそらく貪欲で構築していくんだろうと思ったが、深さ であり、何も考えずに葉の数を最大化はできない。 また、根から適当に貪欲していくのも良くない。なぜなら、増やしすぎると、それ以降の葉の数と辻褄が合わなくなる。 解法 …
題名のまんまです。 1,3,3,7 から (1 + 7 / 3) * 3 みたいなパターンを導き出して計算します。 解法 再帰をぶん回す。全探索です。 括弧さえつかなければ、適当に演算子を全探索してevalすればいいが、問題は括弧の場所がめんどくさい。 全探索する手法も考…
問題 個の頂点の頂点を持つグラフが与えられる。このグラフには、とをコスト1で結ぶ辺と、個のをコストで結ぶ辺がある。 からまでの最短距離を求めよ。 解法 であるから、グラフを陽に持つことはできない。 したがって、一部の頂点のみを利用して問題を解く…
問題 頂点の木が与えられる。木上の頂点に2つコマを置き、これらについて、次のゲームを行う. ・各ターンごとに、をこの順序に従って隣接する頂点に移動させる.ただし、一つの頂点に2つ以上のコマが存在するとき、ゲームを終了する ・はできるだけゲームを長…
問題 atcoder.jp整数が与えられる。総和がとなる数列の個数を求めよ. ただし、すべての項は3以上の整数である. 解法 ・であるから、数え上げる数列の最大の長さはを超えない. ・また、ある項を使うとすると、までの長さが求まっていれば良い. ・動的計画法. …
はじめに Day 0 コンテスト当日 コンテスト参加 A問題 B問題 C問題 その他の問題 最後に はじめに ICPC 国内予選に@sugar_sentan さんとチームを組んで参加しました。*1 結果は3完109位で、予選敗退です。 競技プログラミングを続ける上で、最も強い動機であ…
問題 ゲームバランス これD問題らしい。まじ？ 考察 最終的には、最大値のパラメータを求めれば良い。・ある,について、レベルの増加値 : が最大となる敵を倒しても回以上戦闘しなければならない。ただし、倒せる敵はという条件を満たす。・レベルの増減値を…
問題文 C - Sugar Water 解説 ・2種類の水・砂糖しか使えないため、これらを用いて構成できる水・砂糖の組み合わせを考えないと行けない → 動的計画法 ・次に、ある水の量 について考える。このとき、に溶ける砂糖の最大値が求まれば良い。この砂糖の最大値…
