ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

yukicoder No.53 : 悪の漸化式

概要以下の漸化式が与えられるので、第N項ANを求めよ。 A0 = 4 A1 = 3 4Ak = 19Ak-1 - 12Ak-2 (k > 1) N≦100http://yukicoder.me/problems/80

yukicoder No.25 : 有限小数

概要自然数N,Mが与えられ、NをMで割った商について考える。この商が有限小数で表すことができるならば0以外の最後に現れる数を、表すことができないならば-1を出力せよ。例えば、n=10,m=3ならば-1を、n=100,m=5ならば2を、n=7,m=5ならば4を出力する。N,M≦2^6…

yukicoder No.23 : 技の選択

概要体力Hの敵にダメージを与えて倒すことを考える。こちらには2種類の攻撃方法がある。 通常攻撃: 1回の攻撃でAダメージ与える。必中技。 必殺技: 1回の攻撃でDダメージ与える。2/3の確率で命中。1/3の確率で攻撃を外す。 この2種類の攻撃を使って敵…

ABC #020 D : LCM Rush

概要2つの正整数a,bの最小公倍数をLCM(a,b)とする。2つの正整数N,Kが与えられるので、を10^9+7で割った余りを求めよ。 100点解法:1≦N≦10^9, 1≦K≦100 101点解法:1≦N,K≦10^9 http://abc020.contest.atcoder.jp/tasks/abc020_d

yukicoder No.167 : N^M mod 10

概要N^M mod 10を求めよ。N,Mは非常に大きな値http://yukicoder.me/problems/373

yukicoder No.164 : ちっちゃくないよ!!

概要1以上の整数がN個与えられる。それぞれの整数は2〜36進数の範囲で与えられ、正当に解釈できる表記であればどのように解釈してもよい。例えば、11という整数が与えられ、この値を10進数に変換するとき、 2進数と解釈すれば3 10進数と解釈すれば11 36進数…

yukicoder No.163 : cAPSlOCK

概要大文字・小文字のアルファベットからなる文字列が与えられる。大文字は小文字に、小文字は大文字に変換した文字列を出力せよ。http://yukicoder.me/problems/339

yukicoder No.13 : 囲みたい!

概要HxWのグリッドがあり、各マスに数字が書かれている。各マスについて、上下左右に隣接するマスと同じ数字が書かれていれば、その2つのマスを結ぶことができる。グリッド内で閉路ができるかどうか判定せよ。1<=N,M<=100http://yukicoder.me/problems/37

yukicoder No.160 : 最短経路のうち辞書順最小

概要0~N-1のN個の駅があり、駅と駅は路線で結ばれ、それぞれ移動距離が決められている。ある駅Sからある駅Gまでの最短経路を求めよ。 最短経路が複数存在する場合は、その中で辞書順最小のものを出力せよ。N<=200http://yukicoder.me/problems/417

ARC #034 C : 約数かつ倍数

概要正整数A、Bが与えられる。A!の約数かつB!の倍数であるような正整数の個数を1,000,000,007で割った余りを求めよ。1<=B<=A<=10^9 A-B<=100http://arc034.contest.atcoder.jp/tasks/arc034_3

CODE THANKS FESTIVAL 2014 A日程 G : 通勤電車と気分

概要電車には1~Kの番号が付けられたK個の座席が一列に並んでおり、N人がこれらの座席に座ることを考える。人は以下の2種類の座席の選び方のどちらかによって座る座席を選ぶ。 「とにかく座りたい気分」:空席の中で最も番号が小さいものを選ぶ。 「余裕があ…

Valentine's Day Round (BestCoder #030) C : The Experience of Love

概要N個の町とN-1本の道がある。町には1~Nまで番号がつけられており、道は2つの町a,bを距離cでつないでいる。ある町から別の町に行くときに通る道のうち、最大の距離を持つ道と最小の距離を持つ道の距離の差を計算する。例えば町1,2,3があり、町1,2間の距離…

Valentine's Day Round (BestCoder #030) B : Misaki's Kiss again

概要自然数Nが与えられる。gcd(N, M) == (N xor M)を満たす自然数Mを全て列挙せよ。0&ltN<=10^10 1<=M<=Nhttp://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=568

BestCoder #029 B : GTY's birthday gift

概要集合Sがあり、その中にn個の要素が含まれている。「集合Sに属する2値を選び、その和を集合Sに加える」という動作をk回行った後に集合Sに含まれる要素の和の最大値を求めよ。2<=n<=100000 1<=k<=1000000000http://bestcoder.hdu.edu.cn/contests/contest_…

CODE FESTIVAL 2014 予選B D 登山家

概要ある山脈にN個の山小屋が東西に一直線に並んでいる。それぞれの山小屋は標高H[i]に建てられている。それぞれの山小屋から東西を見渡したときに、何個の山小屋が見えるか求めたい。山小屋が見える条件は以下の通り。 現在の山小屋をi、見たい山小屋をjと…

Donutsプロコンチャレンジ2015 C 行列のできるドーナツ屋

概要N人が一列に並んでいて、それぞれの身長H[i]である。自分より前に何人見えるのかを知りたい。”見える”とは、以下の条件を満たす場合のことをいう。 自分がi番目に並んでいてj番目の人が見えるとき、j&lti 自分とj番目の人(身長H[j])の間にj番目の人より…

ABC #018 C 菱型カウント

概要※問題文の内容を少し変更しています。RxCのグリッドがあり、各マスにはoまたはxの印がついている。そこに、「あるマスからユークリッド距離でK-1以内のマスの印を全て変えることのできるスタンプ」を1回押すことができる。例えばK=2のときは、 □■□ ■■■ …

TopCoder SRM 646 Div1 Easy : TheConsecutiveIntegersDivOne

概要N個の整数が与えられる。(N 整数の中から一つ選び1増減させる操作を複数回行うことができるとき、K個以上の連続した整数列になるためには最低何回その操作をする必要があるか求めよ。解法次のような処理で解いた。 ・N個の整数をソートさせる。 ・N個の…

TopCoder SRM 648 Div1 Easy : AB

概要以下の条件を満たす文字列が存在するか求めよ。・N文字 ・文字列sは'A'と'B'の2種類からなる ・s[i]=='A'かつs[j]=='B'となるペア(i,j)がK組ある (0 解法[2015/2/3:別解(動的計画法)を追加]== 貪欲 == 'A'と'B'のそれぞれの個数の積がK以上になるもの…

TopCoder SRM 647 Div1 Easy : BuildingTowersEasy

概要1~Nの建物を横一列に以下の条件で建てたい。(N・1番目の建物の高さは0 ・隣り合う建物の高さの差は1以内にする ・一部の建物について、x[i]番目の建物の高さはt[i]以下にするこのとき建物の高さの最大値を求めよ。解法建設条件の1,2つ目から、i番目の建…

Facebook Hacker Cup 2014 Round 1 : Labelmaker

概要L種類のアルファベットを用いて文字列を作る。(各アルファベットは複数回使うことができる。)そのアルファベットを用いて作ることのできる文字列をある方法で並べたとき、N番目にくる文字列を求めよ。ある方法で並べるとは、1文字からなる文字列を昇順…

【TopCoder】1つ上の色のコーダーになるために

初めにこの記事はCompetitive Programming Advent Calendar 2014の19日目の記事です。どうも、ぱーぽーです。 この記事では「TopCoderのアルゴリズム部門であるSRM(Single Round Match)で1つ上の色コーダーになるためにはどのようにすれば良いのか」につい…

ABC #015 D 高橋くんの苦悩

概要幅がA[i]で重要度がB[i]のスクリーンショットがN枚ある。幅の合計がW以内に収まるようにK枚まで選ぶことができる。 そのときの重要度の合計を最大化する問題。http://abc015.contest.atcoder.jp/tasks/abc015_4解法動的計画法で解くことができる。DPは以…

TopCoder SRM 636 Div2 Hard : ChocolateDividingHard

概要 NxMの二次元グリッドがあり、縦横にそれぞれ3本ずつ線を引き16個に分割する。(N, M 各グリッドには0~9の数字が書いてあり、分割した領域内に書かれた数の和がその領域の得点になる。そしてその16個に分割された領域の中で最も得点が低いものが選ばれる…

TopCoder SRM 635 Div1 Easy : SimilarRatingGraph

概要 (問題文が個人的に読みづらいと感じた)日付とレートを軸とした折れ線グラフがあり、N個の点がプロットされている。 ある2つの区間にある折れ線を比較すると相似な関係になっている場合がある。そのような相似な関係にある折れ線のの中で最長の折れ線の…

TopCoder SRM 634 Div1 Easy : ShoppingSurveyDiv1

概要 N人がM種類の商品の中から買い物をする。 ・何種類でも買ってもいいし、買わなくてもよい。 ・ただし各商品はお一人様1つまでとなっていて同じ商品を複数買うことはできない。 ・K種類以上の商品を買った人はbig shopperと呼ばれる。M種類の商品をそれ…

AOJ 1327 : One-Dimensional Cellular Automaton

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1327N個のセルからなるセルオートマトンS(i, t)があり、以下の更新則を持つ。S(i, t + 1) = (A × S(i − 1, t) + B × S(i, t) + C × S(i + 1, t)) mod M初期状態S(i, 0)が与え…

TopCoder SRM 631 Div2 Medium : CatsOnTheLineDiv2

概要 ある直線上のN箇所にネコがいて、それぞれ座標position[i]にcount[i]匹ずついる。ネコは時間が1進むごとに以下の行動をとる。 ・その場にとどまる ・左に1進む ・右に1進む上記の行動をネコ達がtime回行ったときに同じ座標に2匹以上のネコがいない…

TopCoder SRM 629 Div1 Easy : RectangleCovering

概要 長方形の穴が開いていて、それを長方形の板で隙間なく埋める。 そのときに使う板の枚数の最小値を求めよ。各板の四隅は穴の外側にないとダメ。板同士は重なってもよい。解法 板を十字にして埋めていくのは意味がないので、板を縦または横向きに揃えて並…

TopCoder SRM 629 Div2 Medium : CandyMaking

概要 容積がcontainerVolume[i]である箱がN個あり、それぞれの箱にdesiredWeight[i]の重さの飴を入れたい。しかし飴の密度は1種類しか選ぶことができないので、全ての箱に希望通りの重さの飴が入れられるかどうか分からない。希望の重さと実際の重さの差の…