問題 D - Snuke Numbers 「S(n) := 10 進数表記での n の桁和」としたとき、m > n である任意の正の整数 m に対して n / S(n) <= m / S(m) が成り立つような n を「すぬけ数」と呼ぶとき、「すぬけ数」を小さい方から順に K 個求めよ、という問題。 解説 コ…

結果 C の１完、957 位中 351 位、レート 1523 (+34) (Highest)。C 問題を落ち着いてノー WA で通すことができたのはよかった。しかし、D 問題で実験しかしてなかったのは悲しかった。 C 問題 問題 数列の中で長さ K の連続した部分列をとり、その中の最小値…

問題 E - Range Minimum Queries 長さ N の数列 A から「長さ K の連続する部分列を１つ選び、その中の最小値を数列から取り除く」動作を Q 回行う。Q 回で取り除いた Q 個の数値の最大値と最小値の差の最小値を求める問題。 解法 最小値を固定させると、ま…

問題 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip N 個の駅と M 個の路線があり、各路線には運営会社が決められている。同じ運営会社で連結の路線はどれだけ乗ってもコストはかからないが、運営会社をまたいで載る場合はコストがそれごとに１かかる。こ…

問題 D - An Ordinary Game 端っこと左右が同じ文字の位置にある文字以外を２人が最適に取り除いていくときの勝敗を求める問題。 解法 S の両端が同じならば、終わった時の文字列の長さは奇数になる。一方、S の両端が異なれば、終わった時の文字列の長さは…

問題 D - 桁和 / Digit Sum 10 進法で N を b 進法に直したとき、その桁和が S になるような最小の b を求める問題。 解法 b をとりあえず 1~√N まで試す。b が √N を超えると、N の b 進法での桁数は２桁になるので、以下のような式が成り立つ。 N = αb + β…

実装したこと ランキングに表示させる名前を入力できるように ステージごとのランキング切り替えでのバグを修正（範囲外アクセスの恐れがあったので） メニュー画面と相互切り替えが可能に 名前入力画面は Siv3D のリファレンスにあったお手本をがっつり真似…

問題 D - Score Attack 重み付き有向グラフが与えられ、頂点1 ~ N に移動する時の最大コストを求め、かつ、そのパス中に閉路があり無限にコストを高められる場合はそれを検出しなければならない。 解法 Bellman–Ford 法以外に何かあるのか？ 解答 Submission…

問題 D - Maximum Average Sets N 個のそれぞれ価値が決まった品物があり、そこから A 以上 B 以下個選ぶ。ここで、選んだ品物の価値の平均の最大値を求め、また、その最大値になるような品物の選び方の通り数を求める。 解法 品物を価値でソートし、とりあ…

問題 D - Mixing Experiment ２つのタイプの成分が (a_i,b_i) だけ含まれ、値段が c_i の薬品が N 個あるとき、２つのタイプの成分の比を Ma : Mb にするときの値段の最小値を求める問題。 解法 「dp(i, j, k) := i 番目の薬品まで見たとき、２つの成分を (j…

問題 D - Candidates of No Shortest Paths 無向連結グラフが与えられ、全頂点間の最短パスに使われていない辺の数を求める問題。 解法 頂点の数が <= 100 なので、ワーシャルフロイド法で全頂点間の最短距離を求める。その後、各辺について、全頂点から両端…

問題 D - Patisserie ABC N 個の「綺麗さ」「おいしさ」「人気度」の３つの要素があるケーキを M 個選んで食べる（重複なしで）。この時、綺麗さの合計の絶対値 + おいしさの合計の絶対値 + 人気度の合計の絶対値の最大値を求める問題。３つの要素の値は負数…

結果 ３完２WA。2356 位中 1129 位。本当に水色コーダーなのか？という成績。ホントに競プロに向いていない。 A 問題 問題 A - Happy Birthday! 解法 落ち着けばノーミスで AC できるので（激冷え） 解答 Submission #2683196 - AtCoder Beginner Contest 10…

結果 AtCoder Virtual Contest 全完（18:39）。意外と簡単目な問題だったのですんなり解けた。前に問題を少し見たことがあったのも影響していると思う。 A 問題 問題 A - Day of Takahashi a 月 b 日までの月数と日数が等しくなる日の数を求める問題。 解法 …

水色（Specialist）になりました 緑のままずっといるっていうのもなんかなーと思っていたのでよかった。 非競プロerですが、水色になりました！！！Wow! Coder Bwambocos competed in Educational Codeforces Round 45 (Rated for Div. 2) and gained 106 ra…

問題 C - Strange Bank 6 と 9 の累乗の数で N をぴったり作りたい。最小で何個必要か、という問題。 1 <= N <= 100000。 解法 コンテスト中、累乗の数の中から一番 N に近い数を引いていくという解法しか考えていなかったが、それが最適ではないケースがあ…

結果 A,B,D の３完（49:10）。D 問題を始めに通した後、C 問題を考えたが入出力例３が一向に合わず。諦めて A,B 問題を通し終わった。今回の C 問題は D 問題より圧倒的に難しいと思った。 D 問題 問題 D - Good Grid N*N のマス目のうち、それぞれのマスの …

結果 ２問完答。A,B 問題を早く通せたのはよかったけど、C 問題が通らないのが納得いかない。 AtCoder Virtual Contest A 問題 A - Digits Sum N の桁和が 1 ならば 10 でそうでなければそのまま桁和が答えになる。 Submission #2642206 - AtCoder Grand Con…

実装したこと SceneMgr にランキング画面を追加 ゲーム画面からランキング画面に飛べるようにした ステージ・難易度ごとにランキングをファイルに保存・読み込み ステージ・難易度ごとにランキングを表示 ランキングのスクロール表示 当たり前の内容。数時間…

問題 D - Equals 1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。 解法 順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能…

問題 C - K-th Substring 文字列 s の部分文字列の重複を除いたうち、K 番目に小さいものを答える問題。 解法 全ての部分文字列を列挙していては O(|s|^3) となり間に合わないので、工夫する。s の各文字から長さ 1~K のものが答えの候補となるので、O(|s|) …

問題 C - Kill/Death A, B 両チームのそれぞれのプレーヤー（それぞれ N, M 人）の Kill 数が分かっているとき、各プレーヤーの Death 数の通り数を求める問題。 解法 両チームの中で同じ Kill 数のプレーヤーごとに区切り、何人グループかを調べる。A チー…

問題 D - ハンコ HW のマスに NM のハンコをひたすらおし、押されたマスの合計を求めよ、という問題。 解法 H,W <= 10^9 であるため、HW の二次元配列は用意できない。しかし、N,M <= 10^3 であるため、なんかできそうだなあと思った。考えると、 ハンコのマ…

問題文 C - XORパズル / Solving XOR-Puzzles beta 版だと表示が崩れている。 数列 a の中から任意の個数を取り出して、それらの XOR が K になる数列の個数を求めよ、という問題。bit 系の問題は発狂。 解法 「dp(i, j, k) := 数列 a の i - 1 個目までで j…

ゲーム部分を 75% ほど完成させたので develop にマージした。 develop へのマージは INF 年ぶり（もっと進捗を出せ）。 まだまだクソゲーを極めすぎているので改良していく予定。 コミット： github.com ゲーム画面スクショ：

はじめまして。 このブログには競プロで解いた問題、開発しているゲーム・ソフトの進捗などを記録できたらなあと思っています。 ほとんど自分の独り言・記録ですが、どうぞよろしくお願いします。 （学校で新しく採用された Classi のポートフォリオが使い物…