c問題、D問題共に自力で解けた。
https://atcoder.jp/contests/abc096/tasks
C問題
方針
これは簡単で方針としては、左上から順に#の場所に対し、dfsで上下左右の#を探して、見つけたらカウントを増やし、またdfsするという風にする。ここで、カウントが0のまま、つまり上下左右に一つも#がないとき"No"とし、それ以外だと"Yes"にする。これは別にdfsをしなくても#の上下左右に#がないもの(孤立した"#")を探すだけでも同じ解が得られる。
D問題
方針
まずどうなったら合成数になるか考えると、はじめに考えられるのは、偶数1つと奇数4つの場合である。このとき題意を満たすことができるが、「N個の素数のうちから好きな5個を選んで」という条件があり、偶数の素数は2しかないためできない。また、全探索しようにも素数の数が5000個ほどあるため不可能である。よって、どの5つの奇数を選んでも合成数になるようなものを考えてみる。すると、素数のうち1のくらいが1のものを選べばどの素数を選んでも1のくらいは、「1+1+1+1+1 = 5」となり確実に5で割れる。つまり合成数になる。なので、素数のうち、1のくらいが1のものを選び、listなどに保存し、その中からN個選べば答えになる。