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

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

ARC-like

ACL Contest 1 E - Shuffle Window (橙色, 900 点)

コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…

ACL Contest 1 D - Keep Distances (橙色, 800 点)

これは天才!!! 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …

ACL Contest 1 C - Moving Pieces (青色, 600 点)

フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある! 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

CADDi 2018 F - Square (橙色, 900 点)

面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…

CADDi 2018 E - Negative Doubling (黄色, 800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

キーエンス プログラミング コンテスト 2020 F - Monochromization (銅色, 1100 点)

「操作によって出来上がるものが何通りあるか?」という問題では、まず判定問題を考える!(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (赤色, 1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

DISCO ディスカバリーチャンネル 2020 予選 D - Digit Sum Replace (青色, 500 点)

すごく面白かった! 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …

キーエンス プログラミング コンテスト 2020 E - Bichromization (黄色, 900 点)

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip (青色, 700 点)

隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる!!! drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…

キーエンス プログラミング コンテスト 2020 C - Subarray Sum (茶色, 400 点)

結構ギャグ要素強めな問題だった 問題へのリンク 問題概要 3 つの整数 が与えられる。 長さ の整数列 であって、以下の条件を満たすものを構築せよ: を満たすような の組がちょうど 個ある 制約 考えたこと とりあえず一つ思うこととして、 は全部 1 以上な…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (緑色, 200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (青色, 600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (橙色, 800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (橙色, 800 点)

今回は惨敗したけど次回また頑張りたい!!! 問題へのリンク 問題概要 の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。 の右隣の値は ではない 制約 考えたこと 色々手を動かしてみると、条件…

第5回 ドワンゴからの挑戦状 予選 2018 E - Cyclic GCDs (赤色, 1000 点)

バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…

第5回 ドワンゴからの挑戦状 予選 2018 D - Square Rotation (赤色, 800 点)

すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…

第5回 ドワンゴからの挑戦状 予選 2018 C - k-DMC (青色, 600 点)

差分更新系の代表的問題。でも頭がごっちゃになって大変だった。 問題へのリンク 問題概要 'D', 'M', 'C' からなる長さ の文字列 と正の整数 が与えられる。 の添字 であって S[ ] = 'D' S[ ] = 'M' S[ ] = 'C' を満たすものの個数を求めよ (というクエリに …

第5回 ドワンゴからの挑戦状 予選 2018 B - Sum AND Subarrays (水色, 400 点)

最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…

第一回日本最強プログラマー学生選手権-予選- F - Candy Retribution (銅色, 1000 点)

てんぷらたんのこれを思い出した!!! yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (青色, 500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

第一回日本最強プログラマー学生選手権-予選- D - Classified (青色, 600 点)

初見時は証明なしに再帰的にやった... 問題へのリンク 問題概要 頂点の完全グラフがあたえられる。 このグラフの辺に、非負整数値を付けていく方法のうち 整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない という条件を満たす範囲内で、…

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (橙色, 800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

diverta 2019_2 F - Diverta City (銅色, 900 点)

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

diverta 2019_2 E - Balanced Piles (橙色, 800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

diverta 2019_2 D - Squirrel Merchant (青色, 600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…

diverta 2019_2 C - Successive Subtraction (水色, 500 点)

復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…

diverta 2019_2 B - Picking Up (緑色, 300 点)

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…

みんなのプロコン 2019 C - When I hit my pocket... (茶色, 400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…