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

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

小さいところで帳尻を合わせる

AtCoder ABC 088 A - Infinite Coins (灰色, 100 点)

少し気づきにくいかもしれない。 問題へのリンク 問題概要 あなたは、 円硬貨を 枚と、 円硬貨を無限枚持っている。 これらで 円をちょうど支払うことができるかどうかを判定せよ。 解法 一瞬戸惑う問題だと思う。現実の支払いの場面を思い浮かべてみるとわ…

AtCoder ABC 246 C - Coupon (灰色, 300 点)

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

AtCoder ARC 109 D - く (黄色, 600 点)

僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した... 問題へのリンク 問題概要 二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。 3 つの石が次の条件を満たしているとき、くの字に並んでいるといいま…

AtCoder ABC 184 C - Super Ryuma (茶色, 300 点)

これ難しいと思った! あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…

AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題! 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …

AtCoder AGC 036 C - GP 2 (黄色, 900 点)

こういう数え上げ、大好きすぎる!!! 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…

AtCoder AGC 005 C - Tree Restoring (青色, 700 点)

面白かった! 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう!!!!!!似た見た目の問題としては、次の問題もあった。 drken1215.h…

Codeforces Round #638 (Div. 2) E. Phoenix and Berries (R2400)

本番なんとかブザービートが決まった! 問題へのリンク 問題概要 赤いベリーと青いベリーとがある。 組のビュッフェがあり、それぞれ赤いベリーが 個、青いベリーが 個入っている。 これらをカゴに詰めていきたい。1 つのカゴにはちょうど 個のベリーを入れ…

AtCoder ABC 164 E - Two Currencies (青色, 500 点)

これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…

フォルシアゆるふわ競プロオンサイト #3 G - Digit Sum Multiple locked

12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (緑色, 400 点)

辞書順最小の教育的例題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…

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

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

MUJIN 2018 F - チーム分け (600 点)

今なら解ける!!! 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制…

AtCoder AGC 003 A - Wanna go back home (茶色, 200 点)

これも場合分けを丁寧に... 問題へのリンク 問題概要 高橋君は無限に広い 2 次元平面上に住んでいて、N 日間の旅行をします。 高橋君の旅程は長さ N の文字列 S であり、はじめは家にいます。 日目には、 S[i] = 'N' なら北へ S[i] = 'W' なら西へ S[i] = 'S…

AtCoder ABC 111 D - Robot Arms (ARC 103 D) (橙色, 600 点)

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