問題 問題概要 期待値の線形性を使う問題。 期待値の線形性を使う類題 No.144 エラトステネスのざる - yukicoder 解法 この問題のよくわからないところは、縦、横、斜めが独立でないので、どうやれば?て感じになる。ただ、どこか１列だけがビンゴする期待値…

問題 問題概要 省略。 解法 tmpに0からn-1まで入れて、それらを条件を満たすまで、シャッフルし続ける感じで解いた。WAだろうなと思ってひとまず書いてみたが、通った。条件を満たす場合が多いらしい。 ２部マッチとかで解けるみたいなので解きます。 ミス …

問題 問題概要 省略。 解法 幅優先探索。qに座標を入れて、numに何回目の動きなのかを入れてやった。 ミス 特になし。 コード #include <iostream> #include <vector> #include <queue> #include <cstdio> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int dx[8] </algorithm></cstdio></queue></vector></iostream>…

問題 問題概要 省略。 解法 動的計画法でやった。 dp[y座標][x座標][1つ飛ばしジャンプの回数] := (y, xに行くまでの最小の危険度)というdpを考えた。y座標が常に大きくなるので、DAGと考えるので、このようなやり方でやった。また、うまいやり方が思いつか…

問題 問題概要 nが与えられた時、1からn2まで使いn x nのますを縦横斜め全ての和が奇数になるように、埋めていく。 解法 縦横斜めの和が奇数になるのは、それらの一列に、奇数が奇数個ある時。この条件を満たすには、真ん中に十字形に奇数と配置し、４隅に階…

問題 問題概要 x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。 解法 中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とか…

問題 問題概要 チェスのキングのコマの位置が与えられる。次の手で何通りの進み方があるか。 解法 キングは周囲8方向に1マスずつ進めるので、周りがマスに囲まれていれば、8通りの進み方がある。ただし、隅っこの場合などは変わる。8方向に動かして、範囲内…