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

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

重実装問題

JOI 二次予選 2020 A - ポスター (AOJ 0672) (4Q, 難易度 4)

ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…

AtCoder ABC 045 D - すぬけ君の塗り絵 (ARC 061 D) (2Q, 青色, 400 点)

グリッドが幅広いが、黒色マスの周辺でしか「3 x 3 内部に黒色マスがある」という状況が発生しないことを活用する! 問題へのリンク 問題概要 グリッドの各マスは白色または黒色である。 個のマスが黒色である(座標が与えられる)。 このグリッド内部の各 3…

AtCoder ABC 366 B - Vertical Writing (5Q, 灰色, 200 点)

問題文がやたら難読すぎる!!! 問題へのリンク 問題概要(意訳) 個の文字列 が与えられる。これに対して、次のように縦横をひっくり返して、隙間を文字 * で埋めたようなものを出力せよ。 before red orang blue yellow green gray skyblue black after b…

JOI 二次予選 2023 C - 塗りつぶし (AOJ 0749) (1D, 難易度 7)

ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色(整数値)がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…

JOI 予選 2009 E - シャッフル (AOJ 0536) (2D, 難易度 8)

シミュレーションと呼ばれるジャンルの中では、最も重たい部類の問題 問題へのリンク 問題概要 1 から までの整数の書かれたカードがこの順に並んでいる。このカード列に以下の 回の操作を行う。 回目の操作は、整数 ()によって表される。操作前のカードの…

JOI 予選 2008 C - カードゲーム (AOJ 0523) (5Q, 難易度 4)

ちょっと実装が大変なので、頑張って実装しよう! 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…

JOI 一次予選 2020 (第 1 回) C - マージ (5Q, 難易度 3)

マージソートのマージの部分を実装する問題ですね。 添字を順に進めていくような処理を実装します! この実装は、のちにしゃくとり法を学ぶ際の参考にもなります。 問題へのリンク 問題概要 制約 解法 問題文が複雑で、何をすればいいのかを理解するのが大変…

AtCoder ABC 355 C - Bingo 2 (3Q, 灰色, 300 点)

ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…

AtCoder ABC 241 C - Connect 6 (2Q, 茶色, 300 点)

実装問題! 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…

AtCoder ABC 359 C - Tile Distance 2 (1Q, 緑色, 350 点)

とても重たくて大変な問題。いろんな整理の仕方があると思う。 問題へのリンク 問題概要 下図のように、座標平面が 1 x 2 の長方形に区切られている。 座標 から座標 へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。 制約 考えたこ…

AtCoder ABC 307 C - Ideal Sheet (1Q, 水色, 300 点)

とても面倒な全探索問題 問題へのリンク 問題概要 サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。 ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッ…

AtCoder ABC 354 D - AtCoder Wallpaper (1D, 水色, 450 点)

周期性をうまいこと活用してなんとかする問題! 問題へのリンク 問題概要 座標平面上で下の図のような白黒模様が与えられる (問題文より)。 左下の頂点が 、右上の頂点が であるような長方形領域内部の黒色部分の面積 (の 2 倍) を求めよ。 制約 考えたこと …

AtCoder ABC 338 G - evall (4D, 橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

AtCoder ABC 327 C - Number Place (5Q, 灰色, 250 点)

9 × 9 に並んだ数字が「数独」の解になっているかを判定する問題 問題へのリンク 問題概要 下のような 9 × 9 グリッドが与えられる。各マスの値は 1 から 9 までの整数値である。 このグリッドが数独の要件を満たすかを判定せよ。 1 2 3 4 5 6 7 8 9 4 5 6 7…

AtCoder ABC 323 C - World Tour Finals (灰色, 250 点)

1 つ 1 つの要素は難しくないが、実装がとにかく重たい!落ち着いて整理して考えたい問題。 問題へのリンク 問題概要 プレイヤー が、配点が である 個の問題からなるコンテストに挑んでいる。なお、 は 以上 以下の の倍数である。 プレイヤー には最初から…

AtCoder ABC 322 D - Polyomino (水色, 400 点)

最近、実装重たい全探索問題多いね! 問題へのリンク 問題概要 下図のようなポリオミノが 3 個与えられる。いずれも 4 × 4 グリッドにおさまるサイズであり、入力は 4 × 4 グリッドで与えられる。文字 '#' に対応する部分が与えられるポリオミノに対応する。…

JOI 予選 2007 D - カードの並び替え (AOJ 0513) (5Q, 難易度 3)

難しくはないけど、やることが複雑だし、問題文を読み解くのがハードな問題! この手の問題は、解けないと思ったら、実際のコードを見てしまう方が早いと思う。 問題へのリンク editorial 問題概要 正の整数 が与えられる。 1 から までの数値が書かれたカー…

AtCoder ABC 112 C - Pyramid (緑色, 300 点)

AtCoder ではとても珍しい、注意して考えることの多い、重めの全探索な問題 問題へのリンク 問題概要 ピラミッドの高さを当てたい。 ピラミッドには 中心座標 (Cx, Cy) と 高さ H が定まっており, 座標 (X, Y) の高度は max(H−|X−CX|−|Y−CY|, 0) である。 ま…