けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

構築

AtCoder ABC 131 E - Friendships (500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…

diverta 2019_2 F - Diverta City (900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…

AtCoder ABC 051 C - Back and Forth (300 点)

ちょっとした構築系問題という感じかな... 問題へのリンク 問題概要 二次元平面上の二点 が与えられる。 はすべて整数である。 今、 から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら に行き、またそこから出発して に戻り、さらに…

AtCoder ABC F - XOR Matching (600 点)

600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…

AtCoder AGC 001 D - Arrays and Palindrome (1000 点)

楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…

GCJ 2019 Round 1A A - Pylons

こどふぉにありそうな雰囲気の問題かな 問題へのリンク 問題概要 × のグリッドの各マスをちょうど一回ずつ訪れたい。ただし スタートとゴールは異なるマスでよい 毎回の移動は、上下左右斜めの 8 方向への移動は禁止 (飛車の移動も角の移動も禁止) を満たす…

GCJ 2019 Qual A - Foregone Solution

面白かった 問題へのリンク 問題概要 100 桁以下の整数 が与えられる (文字列型で受け取るのがよさそう)。 も も十進法表記で '4' が登場しない を満たすような整数 の組を 1 つ求めよ。 制約 < < 考えたこと 繰り上がりを考えると面倒なので、繰り上がりが…

GCJ 2019 Qual B - You Can Go Your Own Way

ちょっと考えればできる 問題へのリンク 問題概要 × のグリッドグラフの左上から右下への最短路が 1 つ与えられる。この最短路と辺を共有しない最短路を一つ求めよ (頂点で重なるのは OK) 制約 考えたこと 対角線に沿って反転すれば OK #include <iostream> #include <sstream> </sstream></iostream>…

AtCoder AGC 032 B - Balanced Neighbors (700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!! 問題へのリンク 問題概要 頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ: どの頂点についても、その頂点に隣接している頂点の番号の和が等しい 制…

AtCoder AGC 031 C - Differ by 1 Bit (800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

AOJ 2940 場所当てゲーム (RUPC 2019 day1-D)

発想はすごくシンプルで、実装頑張る 問題へのリンク 問題概要 整数 が与えられる。 ラウンドのインタラクティブゲームを行う。 まずあなたは 頂点の無向単純グラフを 1 つ作成して出力する。 相手はそのグラフを受け取り、各ラウンドのはじめに、いずれか 1…

みんなのプロコン 2018 決勝 B - 経路が色々 (800 点)

解説は三進法でやってたけど、二進法でもできた 問題へのリンク 問題概要 次をすべて満たすようなマス目を構成せよ。 マス目の各マスは白か黒で塗られている マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である 一番左上のマスから…

Tenka1 2018 D - Crossing (500 点)

C 問題もそうだったけど、C も D も証明した状態で提出していた。 ノーペナで行けたのはよかったけど、でもスピード的には、証明できていなくてもえいやっと提出した方が早いのかもしれない。 問題へのリンク また類題として以下の問題がある: CODE FESTIVAL…

AtCoder ARC 103 E - Tr/ee (700 点)

取り急ぎ... 問題へのリンク 問題概要 N 頂点からなるツリーがあって、各辺で切ってできる連結成分のサイズとしてありうるものすべて集めたものが指定される。そのようなツリーを 1 つ構築せよ。存在しない場合は -1 とせよ 解法 とりあえず、 サイズ 1 は絶…

AtCoder ARC 103 D - Robot Arms (600 点)

くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…

AtCoder AGC 008 D - K-th K (800 点)

実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…

AtCoder ARC 091 E - LISDL (700 点)

問題へのリンク 問題概要 1, 2, ..., N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成せよ: 最長増加部分列の長さは A 最長減少部分列の長さは B 制約 1 <= N, A, B <= 3 × 105 解法 LIS and LDS と…

AtCoder AGC 027 D - Modulo Matrix (1100 点)

悔しい... 問題へのリンク 問題概要 (AGC 027 D) 整数 が与えらる。以下の条件を満たすような 行列 a を 1 つ構築せよ: 各要素の値は 以上 以下 ある正の整数 が存在して、行列の上下左右に隣接する 2 数 をどこから取り出しても、max() を min() で割ったあ…

AtCoder ARC 102 D - All Your Paths are Different Lengths (700 点)

好きだけど細かいところで時間とられるやつなん 問題へのリンク 問題概要 (ARC 102 D / ABC 108 D) 整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって N <= 20 M <= 60 任意の辺 (u, v) について u < v でなければ…

Codeforces 502 C - The Phone Number

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

AtCoder AGC 025 D - Choosing Points (800 点)

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。 d1=2^k * u (u は奇数) とす…