2019-01-01から1年間の記事一覧
問題はこちら atcoder.jp マス に二つの数 が書かれている．一回の移動で または に移動する．マス から に移動しながら，数の片方を選び に．もう片方を に追加する．移動する経路を とする時，以下の値を偏りと呼ぶ． 数を自由に選びながら移動した時の，…
問題はこちら atcoder.jp 長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。 以下は0-indexで話を進める。 考え方 要素の和の余りに関する問題なので、とりあえ…
問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…
問題はこちら 考え方 解答 別解 問題はこちら atcoder.jp までの箱がある。 個目の鍵のコストは であり、 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は を出力せよ。 考え方 まず、これは割と複雑な遷…
はじめに 勝ち続ける意志力 (小学館101新書)作者: 梅原大吾出版社/メーカー: 小学館発売日: 2012/04/02メディア: 新書購入: 24人 クリック: 449回この商品を含むブログ (75件) を見る この本は、世界一賞金を稼いだことでギネスブックにも載ったり、奇跡の大…
問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…
問題はこちら atcoder.jp 長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。 操作: となる を選び、 ] 内にある文字列を左…
問題はこちら codeforces.com 頂点数 の木が与えられる（木なので辺の数は ）。 以下のような 個のクエリ が投げられるので、それぞれに対する答えを出力せよ。 求めるものは以下を満たす頂点 , , のペアの個数。 頂点 と を結ぶパスの中で、辺の最大の重み…
問題はこちら codeforces.com 長さ の 配列 が与えられる。一回の操作によって任意の要素一つ、 を2で割って切り捨てることを行う。 （つまり、 ） 個の等しい要素を 中で得るには、何回操作を行えばいいか、その最小値を求めよ。 考え方 全ての を、0になる…
問題はこちら 考え方 解答1 - 解の候補を絞る 解答2 - 貪欲とpriority_queueを使う 解答3 - K個以上になる境目の値を二分探索 問題はこちら atcoder.jp 美味しさは以下のように表される。 種類のケーキ 種類のケーキ 種類のケーキ この時、それぞれのケーキ…
問題はこちら atcoder.jp から となる を選び、 とする。この時、 以下の操作回数で の最大公約数として考えられるもののうち、最大のものを求めよ。 考え方 step1 - 解の候補 まず、 に+1して、 に-1するという操作は、 の値を一つ に移動する操作と考える…
問題はこちら atcoder.jp 今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。 考え方 JSC2019予選 - D 「Classified」 (600) - Mister雑記 [AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP 奇閉路が存在しないようにグラフを分割できれば良…
問題はこちら atcoder.jp 考え方 なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。 misteer.hatenablog.com Cで僕が考えたこと・累積的な何かを考えるとよさそう・[L, R]…
Sequence Decomposing 問題はこちら atcoder.jp 問題文は次のように言い換えることができる。すなわち、「数列 が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。 考え方 sample1について…
この記事は僕の就活体験記です。新卒の就活体験記をいくつか参考にさせていただいたので、僕も誰かの役に立てばいいなと思い書きました。
道路の老朽化対策について タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。 問題はこちら。 atcoder.jp 都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。 Unionfindを使ってクエリごと…
Cell Distance 問題はこちら atcoder.jp 数式があるので、それを文章にする。 「 行 列のマス目のうち、 マスに駒をおく。このコストは全ての駒のペアのx座標の差 + y座標の差の和で計算される。これを全ての配置について和を取りなさい。」 考え方 愚直にや…
Must Be Rectangular! 問題はこちら atcoder.jp 考え方 解説放送が一番わかりやすいと思うので、そちらを見ると良い。 https://www.youtube.com/watch?v=XI8exXVxZ-Qwww.youtube.com 座標を二部グラフで捉えるという考え方は典型らしい。 下記の座標を、x座…
Roadwork 問題はこちら atcoder.jp 考え方 まずは、 に出発した人がどのような条件を満たした時に の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。 これを愚…
Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …
Beautiful Array 問題はこちら codeforces.com 自分が気づいたところ まず最初に，xが負の時は最小区間和を選んできてそれをx倍する．xが正の時は最大区間和を選んできてそれをx倍する．とすれば最大値が求まると考えた．ここでセグ木とかをググり始める... …
Stones 問題はこちら atcoder.jp 自分が気づいたところ 全ての石が黒 or 白になると勘違いをし， WA 左端から ... と白が続いている時は無視し，そのさきは全て黒 or 白になると勘違いし，WA 右端から ### と黒が続いている時も無視できることに気づくが，黒…
Two Teams 問題はこちら codeforces.com 自分が気づいたところ 愚直解は，毎回使っていない最大値を検索→幅 を探索し，使っていないものをk個チームに属させるというもの． 計算量としては， なのでそのまま実装すると になるので間に合わない． そこで，一…
Serval and Parenthesis Sequence 問題はこちら 問題文難しくないですか... codeforces.com 自分が気づいたところ 括弧を扱う問題では，stackを用いると綺麗に書けるなと思い実装．しかしコンテスト時間内に問題文を解読できなかった... 解説を読んで このブ…
日本沈没 問題はこちら atcoder.jp 自分が気づいたところ 小課題1に関しては，愚直にシミュレーションしていけば求まるが，満点をもらうことはできない． のように，谷になっているものに注目した．すると，問題は「谷となっているところのうち，一番低いと…
すぬけ君の塗り絵 問題はこちら atcoder.jp 自分が気づいたところ なので，全てのマス目を調べていくのは間に合わなさそう．そこで，黒く塗られているマス目だけに注目することにした． 一つの黒いマス目が影響を及ぼすマス目は，周囲の9マスだけである．こ…
Static Sushi 問題はこちら atcoder.jp 自分が気づいたところ 最大でも反対方向に向きを変える動きは一回だけなので，反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた． これだと，計算量は反転する場所が ，反転後の最大値探索が…
2019/12/23追記: ※このブログはABCがABCDの4問だった頃の記事になりますので，現在では当てはまらないことも多いですがご承知ください． 2019/03/24のABC122で水色になりました． 自分が割と苦労して水色になったのと，同じようなブログがかなり参考になった…
アクセス修飾子 コンストラクタ 引数が1つの場合 移譲コンストラクタ ヘッダとソースを分離する アクセス修飾子 まずは書き方．順番やその個数は任意で，何度現れても良い． class Hoge { public: int a; private: int b; public: int c; }; デフォルトのメ…
はじめに テンプレート機能 デバッグ ファイル単位での実行 ファイルのリフォーマット 最後に はじめに 僕は競技プログラミングやるときのIDEとしてCLionを使っています．周りにCLionを使っている人が多くないので，今回はCLionってこんなに便利だよ！という…
