コーナーケース
これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…
方針立ってからも、ちょっと実装辛い ^^; 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 正数列の連続する部分列であって、その積が、和の 倍となっているものが何通りあるかを求めよ。 制約 考えたこと パッと思うことは、積の中…
面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…
こういう問題を求めてた！！ 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れ…
微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか？ ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…
面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…
な場合に注意。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の操作を 回まで行うことができる: 整数を 1 つ選んで、0 にする 操作を行った後の、整数の総和として考えられる最小値を求めよ。 制約 考えたこと 素朴に考えれば、 が大きい順…
一瞬激ヤバに見えるし、コーナーケースの数もえげつないけど、とりあえず最小の初項はすぐにわかると... 問題へのリンク 問題概要 等差数列があった。 等差数列を concat して得られる文字列から、先頭から何文字かと、末尾から何文字かを削除して得られた文…
その 2 と雰囲気は似ているけど、一気に考えづらくなった！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…
ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した！！！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…
とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…
またしても、in-place DP のいい練習になった！！！ 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
意外と罠にはまりやすい問題かもしれない！！！ この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…
面白かったけど場合分けが怖かった 問題へのリンク 問題概要 "...X......XX..X..X.XXX...X..." のような '.' と 'X' からなる長さ の文字列が与えられる。 先手は連続する 個の '.' をすべて 'X' に置き換える 後手は連続する 個の '.' をすべて 'X' に置き…
あるあるあるある。 問題へのリンク 問題概要 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。 今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在す…
確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。 問題へのリンク 問題概要 個の整数であって、最小が 、最大が であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。 制約 考えたこと この手の問題で重要…
ちょっと注意。ABC なら 300 点かな。 問題へのリンク 問題概要 人がいて、キャンディ 個を余らさずに 人に分配する。 人目の人はちょうど 個のキャンディを受け取ると喜ぶ。喜ぶ人数の最大値を求めよ。 制約 考えたこと 基本的には が小さい方から配ってい…
600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…
ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…
うまくシミュレーションする系 問題へのリンク 問題概要 N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2～N 番目の箱には白いボールが 1 個ずつ入っています。 高橋君は M 回…
今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com
見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…
ちょっと注意が必要な Bellman-Ford 法の典型題。昔の AtCoder はこういうのもあったのか... 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。頂点 1 から頂点 N への最長路の長さを求めよ。無限に大きくできる場合は "inf" と出力せよ。…
グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…
あの激熱展開を繰り広げた会津合宿北大セットの E 問題。 「橋以外を壊した方がいいケースもある」ということに終盤間際で気づいてからの、残り 14 秒で通せたのは感動した！！！！！！！ こたつがめさん・シンヤカトーありがとーーー コンテストでは、「二…
ごめんなさい！！！！！ コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)！！！ 嘘解法 ：https://beta.atcoder.jp/contests/abc110/submissions/3251109 S と T の各文字の個数をカウントして、それぞれ個数ベクトル…
「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。
ARC 099 C - Minimization 問題概要 (ARC 099 D / ABC 101 C) 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <=…
