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ってこんなに便利だよ！という…