読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Codeforces Round #166 (Div. 2) oo--- 1612->1532

競技プログラミング codeforces

ABだけ正解。
レートが1500から1600の間で単振動している(´・ω・`)

A問題

与えられた整数以上ですべての桁の数字が異なる数を答える。
全探索。

B問題

行列の要素に任意の回数1をたせる時、どれか1つの行か列がすべて素数になるまでに必要な最小の回数。

あらかじめ素数を求めておけば行列の各要素について二分探索で素数を調べて素数までの距離を計算することができる。
そうしたらそれを行と列について足しあわせて比べるだけ。

C問題

与えられたnまでの数値をk個の集合に等差数列にならないように分割する。

難しい問題なのかと思ったら診断人さんのニコ生をみたらすごく簡単な内容でした……。
たとえば3つに分割するときは112233123****とすればいいらしい

D問題

与えられた文字列の全部分文字列について、特定の文字がk回までしか含まれない場合の数を求める。
診断人さんのニコ生によると、O(n^2)で部分文字列を列挙して、重複をローリングハッシュで調べればいいとのこと。

個人的にはTrieを作ってやろうと思ったんですが、実装が悪かったのかそもそも間に合わないのかTLEでした

-->