2018-12-01から1ヶ月間の記事一覧
NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…
またしても、最後の最後がよく詰めきれず... (でもその最後のところの詰めの大変さが、この難易度帯の特徴なんだよね) 問題へのリンク 問題概要 頂点のツリーが与えられる。根ノードの番号を 1 とする。各ノード について、以下のクエリに答えよ: 初期状態を…
僕の以前書いた記事、共円がちょっと関係ある問題だ！！！！！！！！！！！！！ ガウス整数！！！！！！！！！！！！！！！！！！！ 問題へのリンク 問題概要 二次元平面に関する以下の 3 種類のクエリ ( 個) に答えよ 格子点 に石をおく 格子点 においてあ…
あまり良くない方針でゴリ押してしまった。でもゴリ押しで通せることの証左になるかと思って記録してみることに 問題へのリンク 問題概要 下図のような「円の列」の内部だけを通る折れ線 (最初の円の中心と、最後の円の中心とを結ぶ) の長さの最小値を求めよ…
こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…
一瞬 Nim に見えそうなのは確かにそんな気もするようなしないような... 問題へのリンク 問題概要 一本のりんごの木があり、 色のりんごが実っています。これらのりんごの 種類の色には 1 から までの番号が振られており、i 番の色のりんごは 個あります。 あ…
好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…
結構好き！ソートすることが本質の問題としていい感じな気がする。 問題へのリンク 問題概要 下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は 人いる。各乗客は 1 秒かけて 1 マス移動できる。…
面白かった 問題へのリンク 問題概要 個の整数 が与えられる。この中から最大個数の整数を選んで、それを小さい順に並べたときに等差数列となるようにせよ。 制約 考えたこと すごく DP っぽい雰囲気の問題。イメージとしては dp[ i ] := i 番目の要素が最後…
ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン！ 問題へのリンク 問題概要 2 つの '0' と '1' で構成された文字列 S, T が与えられる。 S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…
面白い！！！！！！！ 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる (連結とは限らない)。 このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺…
「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。 問題へのリンク 問題概要 人対 人の対戦割当を決めたい。敵が 1 回戦、2 回…
これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…
区間についてどうのこうのする問題、大抵は DP！ 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …
挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…
グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…
これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…
弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…
「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思う。 問題へのリンク 問題概要 個の正の整数 がある。 これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。 このグラフの最大マッチングを求めよ…
一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…
この記事は Competitive Programming (1) Advent Calendar 2018 の 14 日目の記事として書きました。 いやーーーーーーー、それにしてもこんなに大変で充実感のあるものだとは思わなかったのん！！！！！！ 今年 8 月 25〜26 日、参加者 32 人のキャンプの幹…
