なんだか参加記録書くのも、参加するのも久しぶりな気がするSRM. あと2〜3ヶ月でRating 2200超えたいなあと思いつつ問題演習をしていく所存。 今回はDarseinさんと同部屋。 赤のいない平和な部屋だった。 Result 245.20 / Opened / Unopened 1撃墜1ミス 126…

問題 自然数a,b,kが与えられる。 区間[a,b]に、最小の約数がkであるような整数はいくつあるか答えよ。 制約条件 a,b,k≦2*10^9

問題 正の整数nに対して、約数をちょうどn個だけ持つような最小の整数を求めよ。 制約条件 n≦1000 答えは10^18以下であることが保証されている。

問題 3*n人が3人チームをn個作った。 それぞれの人には成績があり、同じ成績の人はいない。チームの決め方は以下のようである。 まだチームに所属していない人のうち、成績が最も良い人が新しいチームのリーダーになる。 その人は、その人のつけている3*n-1…

問題 無向グラフの頂点に自然数が書かれている。 無向グラフのいくつかの頂点間のGCDおよびLCMが与えられる。 このとき、無向グラフの頂点に書かれた自然数の組を、一つ出力せよ。 存在しない場合はNOを出力せよ。 制約条件 頂点≦100 頂点に書かれている数≦1…

問題 整数Nに対してΣ[i=1,N]gcd(i,N)を求めよ。 制約条件 N＜2^31

問題 nPmの、末尾の0を全て取り除いた時の下1桁を求めよ。 制約条件 n,m≦20000000

問題 nxmの方眼紙に、各頂点が格子点であるような長方形をk個書く。 i番目の長方形はi-1番目の長方形の真に内部になければならない。長方形の書き方は何通りあるか、mod 10^9+7で求めよ。 制約条件 n,m,k≦1000

問題 8x8のマスの左下にMがいて、右上のマスにAがいる。 Mを動かしてAの居るマスに辿り着けたら勝ちである。 グリッドの中にはSがあり、Sは、Mが動いた後に、一マス下におちる。 MのいるマスにSが落ちてきたら負けである。 Mは上下左右斜めに隣接するマスに…

久々にCodeforces参加したらボロボロだった。 問題 文字列が与えられる。 与えられる文字列の空でない部分文字列を辞書順に並べ替えたとき、 k番目に来るものを求めよ。 制約条件 文字列の長さ≦100000 k≦100000

問題 1〜nを並べ替えた数列のうち、 転置がちょうどm個あるもので、辞書順最小のものを求めよ。 制約条件 n≦50000 m≦n(n-1)/2

問題 d個の金融商品があり、それぞれの値段および年間の利益が与えられる。 それぞれの商品の金額は固定であるが、同じ種類の商品をいくつも買うことができる。 capの資産を持っている人がn年資産運用するとき、 最大でいくらまで資産を増やせるか求めよ。 …

問題 二人のプレイヤーがk枚のカードを一列に向かい合うようにして並べる。 向かい合ったそれぞれのカードについて、大きいほうに1点が入る。 相手のカードとその並べ方がわかっているとき、獲得できる点数の最大値を求めよ。 制約条件 k≦26

問題 n個の上り下りの記録が与えられる。 それぞれの数字は上り下りの距離であるが、その方向はわからない。 最初は0mの高さにいて、全ての上り下りを終えた時点でも0mの高さにいる。 上り下りの途中で高さが0mを下回ることはない。 この条件を満たす上で、…

問題 何人からアンケートを取って、 それぞれの項目の割合を、小数点k桁未満を四捨五入して算出した。 アンケートの元の人数としてありえるもののうち、最小のものを答えよ。 1以上9999以下に答えがない場合errorを出力せよ。 制約条件 小数点は最大5桁まで

問題 無向グラフが与えられる。 グラフがキャタピラであるかを判定せよ。 ただしグラフがキャタピラであるとは、 グラフ上にあるパスが存在し、グラフの任意の点からのそのパスへの最短距離が1以下であることを言う。 制約条件 グラフの頂点数≦100 グラフの…

問題 n+1頂点からなるグラフが、距離行列の形で与えられる。 0番の頂点を出発し、全ての頂点を一度以上通り、0番の頂点へ戻ってくるのに必要な移動距離の最小値を求めよ。 制約条件 n≦10

問題 n人の人をk人ずつチームにわける。 各チームにおいて、 「チームの全員の名前の長さの平均」と任意の人の名前の長さの差が2を超えてはいけない。 このとき、チーム分けが可能であるかどうか、判定せよ。 制約条件 n≦1000 kはnの約数 各人の名前は80文字…

問題 宇宙人は、1人の子に対して親が最大d人までいる。 親子関係がツリーとして与えられるが、一部が欠けていて、親がd人より多くなっている宇宙人がいる。ツリーに適当に宇宙人を挿入し、1人の子の親がd人以下にしたい。 挿入しなければならない宇宙人の最…

問題 hxwのグリッドがあり、各マスはアンテナ'*'および何もない'o'のいずれかである。 縦または横に隣り合う二つ（一つだけでもかまわない）のアンテナを丸で囲む。 全てのアンテナを囲むのに必要な丸の数を求めよ。 制約条件 h≦40 w≦10

問題 単調非減少な数列A[i]が与えられる。 m個のクエリが与えられるのでそれに答えよ。クエリ： 二つの整数l,rが与えられる。Aのl番目〜r番目の項のうち、最も出現回数が多い数字の出現回数はいくつか。 制約条件 -100000≦A[i]≦100000 m≦100000 数列の項≦100…

問題 アルファベットの小文字であらわされる数値および、アルファベットの大文字であらわされる演算子からなる式が与えられる。ただし式は後置記法になっていて、 abOは、 スタックにaを積む スタックにbを積む スタックからa,bを取り出し、スタックにb O a…

写経してただけなのにWAが出続けてイミフだった。 自分の2部グラフの最大マッチングがバグっているのだろうか。 問題 XxYマスの部屋がある。 それぞれのマスは、床'.',壁'X',ドア'D'のいずれかであり、 ドアは部屋の内部にはない。 最初それぞれの床には一人…

問題 文字列が与えられる。 文字列の順列のうち、与えられた文字列の次の10個および前の10個に対して、 隣り合う文字間の距離の最小値が最大のもの、およびその値を求めよ。 ただし文字aと文字b間の距離とはabs((int)a-(int)b)を意味する。

問題 無向グラフが与えられるので、その最小全域木を求めよ。 同じコストの最小全域木が複数あるときは、 アルファベット順で最も最初にくるものを求めよ。 制約条件 頂点数≦26

問題 hxwの長方形のケーキに対して、n個の長方形の切れ目を入れる。 それぞれの切れ目はx1,y1,x2,y2によって指定される。 全ての切れ目を入れ終えた後、ケーキはいくつの部分に分割されているか求めよ。 制約条件 h,w≦20 n≦50 座標およびh,wは全て整数

問題 変数a〜zおよび+, -からなる式が与えられる。 変数は式中で（一つの変数に対して最大1個の）--または++が前置、または後置されることがある。 変数に++が前置された場合は、式の値を求める前にその変数の値を+1し、 が後置された場合は式の値を求めた後…