問題 問題概要 省略 解法 まず、マークが同じで数字が異なる組み合わせをいくつあるか求める。方法はそれぞれのマークごとにいくつの数字が手札にあるかを調べることで求められる。 次に、数字が同じでマークが異なる組み合わせがいくつあるかを求める。方法…

問題 問題概要 省略 解法 ハッシュて書いてあるけど、特に知識などはいらず、ハッシュ生成の作業を実装するだけ。素数判定の部分にエラトステネスを使ってる。 またハッシュ生成後は1ケタの数字となるので、生成後の数字は多くても0~9の10通りに絞られるん。…

問題 問題概要 省略。 解法 dp[i番目までのおもりを見た時][左側の重さj] := (trueならある)というbool型の配列を用意して、i番目のおもりの時に、左側の重さがjが存在するかをdpで探索していく。単純におもりが左の天秤なのか右の天秤なのかでやってしまう…

問題 問題概要 省略。 解法 エラトステネスをイメージしてやった。アルゴリズムは幅優先探索を利用している。queueにスタート時点の1をいれて、そのあとは、2進数にした時の1の数によって、両側に動いた場所を調べている。幅優先探索で調べると、移動が少な…

問題 問題概要 複数山の石取りゲーム 解法 まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するの…

問題 問題概要 省略 解法 この問題は町どおしを有向グラフでつないでおり、現在の町の番号は増える方向に必ず増えるように条件が与えられている。そして、残り残金も減る方向に行くので、この問題はDAGグラフで考えることができ、dpで解くことが出来る。 dp[…

問題 問題概要 門松列をぶち壊す。 解法 何回でも並び替えていいので、昇順または降順に並び替えてしまえば、大丈夫。バブルソートで実装した。 ミス なし。 コード #include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; typedef long long ll; ty</cstdio></vector></algorithm></iostream>…

問題 問題概要 省略 解法 2m個で循環するので、mod(2m)で計算してる。modを取った後の値がmより大きいか、小さいかで場合分けして、数字が昇順に並ぶ部分なのか、昇順に並ぶ部分なのかで考えて、何組なのかを考えている。 ミス 1オリジンでやっていてばぐら…

問題 問題概要 省略 解法 ソートしてやるだけ。ソートして１番目のものと最後のものを除いた和をだし、それを４で割って平均を出している。 ミス 小数点第２位まで。。 コード #include <iostream> #include <algorithm> #include <vector>> #include <cstdio> using namespace std; #define all(v</cstdio></vector></algorithm></iostream>…

問題 問題概要 完全２分木上をどのようにたどれば、ルートから指定された場所に移動できるかを求める問題。 解法 完全２分木問題は1オリジンにで考えると、配列を使い親と左子、右子を簡単にたどれる。 今回はそこまで考える必要はない。単に奇数なのか偶数…

問題 問題概要 省略 解法 星1だし単純な規則性がありそう。少し実験したら、2回目にキャラクターを利用した時が最大になりそうなことが分かった。数学で証明できると思いますが、わかりません。 ミス なし コード #include <iostream> #include <cstdio> #include <algorithm> using names</algorithm></cstdio></iostream>…

問題 問題概要 カップ麺を買う。買っていく途中で所持金が素数になるとはじめの所持金に戻ることができる。ただし、1つの素数につき、1度だけしか戻ることはできない。最大でいくつのカップ麺を買うことができるかを求める。 解法 まず、所持金以下の数字の…

問題 問題概要 二本の竹がある。二本の竹から任意に注文された竹の長さを切る。多くの注文に答えられるように切るとき、最大いくつの注文に答えられるかを求める問題。 解法 まず注文された竹の長さを昇順にする。竹が短いものから注文に答えていくのは貪欲…

問題 問題概要 回転ずしで美味しさが最大になるように寿司を取る。ただし２回連続ですしを取ることはできない。 解法 1をすしを取る、0をとらない、とすると、 1010 1001 0101 0010 のようなパターンが続くことになる。それを漸化式で表すと、 dp[i][0] = ma…

問題 問題概要 X * Y = Z2を満たすような最小のYを見つける問題。 解法 小さい約数から順番に割っていく。その時に同じ約数で何回割ったかで場合分けする。もし同じ数字で割った割った回数が偶数回のときはその数をYにかける(Yの約数として入れる)。それを繰…

問題 問題概要 計算問題。 解法 やるだけ。 ミス なし。 コード #include <iostream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <bitset> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> typedef long long ll; using namespace std; #define rep(i,n) for(int i=0;i<(n…</cmath></cstring></cstdlib></cstdio></bitset></vector></functional></algorithm></string></iostream>

問題 問題概要 縦横のどちらか一列すべてを消すゲーム。指定された番号の人が負けるかどうかを判定する問題。 解法 この問題はプレイヤーが負けないように選べはゲームをする回数はh + w - 1に必ずなるので、あとはmodで計算。ただし与えられる数字は0オリジ…

問題 問題概要 レーテイングを表記する 解法 場合分けしてやるだけ ミス 特になし コード #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; int main(void){ int a, b; cin >> a >> b; if(a > b) printf("-%d\n", a - b); if(a == b) printf("</cstdlib></cstdio></algorithm></iostream>…