問題概要 vector parent が与えられる。parent[i] とは i 番目のノードの親が parent[i] であることを示す。deletedCell で削除するノードが与えられたとき、残ったノードのうち葉のノードの数をカウントせよ。解法 子を参照する形の木を、与えられた vector…

概要 入力された文字列Sの、長さL分の部分文字列を任意回数ソートできる。ソートした際にはソートされた部分文字列以降にある文字列は全て削除される。このとき辞書順で最小の文字列は何を生成できるか。解法 部分文字列Lの区間を、右端から一文字ずつ左端に…

問題概要 アルファベットの大文字で構成された vector が与えられる。この要素の順列から生成される文字列Sのうち、Sを1文字ずつシフトするように回転させたときちょうど K 回転となるものの数を答えよ。制約 vector の要素は 1 〜 8 各文字列は 20 文字まで…

解法 ポイントは以下 はじめの状態で同じ配置の行は何度列をフリップしても同じ配置の行のまま 同じ列を2回フリップすると Kが2回分消費できる よって、各行について '0' の数をカウントし '0' の数が K "以下" で、'0' の数と K との偶奇が一致すればその行…

大意 プレイヤーのいる座標(u, v) から、X, Y軸平行に絶対値距離d だけ離れてつくられる正方形の領域が、プレイヤーの勢力域であるとする。敵の座標(x, y)が与えられるので、敵を勢力域に入れるためにプレイヤーが初期位置 (0, 0) から移動すべきユークリッ…

問題概要 ある有向グラフが与えられる。このグラフをたどるとき、そのパスの数が多項式の距離で表されるかどうか判定せよ。一度通ったノードでもパスがあれば何度でも通ることが出来る。解法 i から到達できる j を全て探す。中継点kを決めるN^3の方式で、判…

問題概要 テーブルに有るコインを４方向にずらして枠外に振り落とせる。テーブル上に残るコインの数が、与えられた数Kに一致するための最小のテーブルの移動回数を求めよ。解法 制約が小さく、テーブルが 30*30 なので単なる6重ループで求まるはずだが、二次…

解法 除外する二点を考えた上で、一回り大きい領域を二重ループから算出するだけ。反省 問題文の誤読の連続だった。 正方形なのに長方形だと勘違いしたり、N-2個は完全に内部だが、残りの２個は境界上にあるか内部かのどちらかだと勘違いしていてライターさ…

問題 どの隣も同じ文字にならない文字列をLuckyStringと呼ぶ。 入力の文字列sを並び替えたとき、LuckyStringはいくつ生成できるか。 ただし文字列が10文字以下である。解法 階乗を含むオーダー計算が正しく出来ますかという問題。 10! = 3628800 #include<bits/stdc++.h> us</bits/stdc++.h>…

解法 二つの文字列を選んで、そのうち一つの区切る位置を決めて反転させる。これと他方の文字列が一致したらカウントする。 #include<bits/stdc++.h> using namespace std; // rep #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) class FoxAndWord { public: int howManyPairs(vector <string> words) { int result = 0; rep(i, words.size()-1) { REP</b;i++)></bits/stdc++.h>…

解法 Xが負であることが保証されるので、正の数×負の数のペアでなければ必ず解に含まれる。また与えられた数列は必ず偶数個の要素であるので、正の数×負の数のペアが現れる場合は、正の数と負の数がそれぞれ奇数個の場合で、この一個だけが解に関わる。解く…

問題概要 'L','O','V','E'の頻度を調べて、与えられた式によって得点を最大化せよ。解法 概要の通りの実装。 class LoveCalculator { public: int calc(int l, int o, int v, int e) { return ((l+o)*(l+v)*(l+e)*(o+v)*(o+e)*(v+e))%100; } string findBoy(…

以下のコードで通る問題。 class DesignCalendar { public: int gcd(int a, int b) { if(b==0) return a; return gcd(b, a%b); } int shortestPeriod(int d, int y) { return d/gcd(d, y); } };

問題概要 会社でX人運べるシャトルバスを数台雇いたい。このシャトルバスを雇う費用は一台 baseCost + X * seatCost で計算される。各地点に住む従業員数が vector cnt で与えられるので、すべての従業員を運ぶようにしたとき会社の負担する費用の合計を最小…

問題概要 数直線上にいる複数の猫が、それぞれの与えられた初期位置から絶対値Xだけ移動する。猫が最適な動き方をしたとき、猫のいる区間の中で最も端にいる２匹の距離を最小化せよ。解法 どの２匹が区間の端になるかを二重ループで決める。このときすべての…

問題概要 与えられた文字列から同種の文字を全てを削除することを任意回数繰り返す。残った文字列から "CAT" を作れるなら "Possible" 作れないなら "Impossible" を出力せよ。解法 与えらた文字列Sの中の文字を初めから見ていき、'C', 'A', 'T' のときだけ…

問題概要 トーナメント戦で自分とライバルが当たるのは何ラウンド目か求めよ。ライバルと当たるまでの試合は互いに全て勝つものとする。解法 自分とライバルの位置だけtrueにしたvectorを用意し、vectorの隣同士で比較し、論理和を取りながらtrue同士が衝突…

問題概要 単位あたりのXY移動量が与えられるので、初期位置から進んで辿りつけない場所があるならそれを判定せよ。そのような場所がない場合はゴールの位置として最も遠くなるもののコストを算出せよ。解法 指定の初期座標からBFSをし尽くしたときに、まだ訪…

問題概要 正の整数 n の "proper factor" とは、1 と n を含まない n の因数として定義づけられる。ある正の整数 n の全ての "proper factor" が int[] で入力されるので、ここから n を導け。解法 入力の最小の要素と最大の要素の積が答えとなる。以下 edit…

問題概要 ランダムウォークするロボットがある。４方向に遷移確率が与えられるので、同じ場所を踏まずにN回ウォーキングを続けられる確率を求めよ。解法 訪れた場所を **used で記録して遷移確率をかけながら状態を持って dfs するだけ。 EPSについての記述…