Problem Statement You are given the s n, K, and v. Consider the following modular equation with n variables: (x[0] * x[1] * x[2] * ... * x[n-1]) mod K = v. How many solutions does it have? Formally, we want to find the number of sequences …

Problem Statement Any undirected graph can be decomposed into connected components. Two vertices u and v belong to the same connected component if we can travel from u to v by following a sequence of zero or more consecutive edges. The siz…

RMQとは 数列a_0,a_1,...a_nがあるとき次の二つの処理をO(log n)で行う。 s, tが与えられたとき、a_s, a_s+1, .... , a_tの最小値を求める i, xが与えられたとき、a_iの値をxに変更する SegmentTreeとは プログラミングコンテストでのデータ構造 from Takuya…

問題 arc045.contest.atcoder.jp note まず累積和を使って、担当が1人しかいない掃除場所を探し出す。 その後、担当が1人しかいない場所を1、それよりも多い掃除場所を0として累積和をとればO(1)で任意の掃除の区間をサボれるかわかる code

問題 arc053.contest.atcoder.jp note 回文になる文字列は出現回数が奇数の文字が1回以下の場合。 したがってアルファベット26文字が偶数か奇数かを管理すればよい。

問題 abc019.contest.atcoder.jp note 木の直径を求める際には、まず適当なノードを選んで、そこから最も遠いノードを求める。 次にそのノードから最も遠いノードを求めると、その２頂点の長さが木の直径になる。

Problem Statement You are given four s: n, k, x, and y. The s n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and only if gcd(i, j) > k. Her…

問題 abc009.contest.atcoder.jp note 文字列操作を貪欲にするだけなのだが、とても手こずった。 一番左に条件を満たす限り、一番小さい文字を持ってくるようにすればよい。

問題 abc017.contest.atcoder.jp note 累積和を用いて、ある宝石を選ぶことになった際のスコアの合計を求める。すべての宝石をゲットする場合得られる総合点から、ある宝石を選ぶ場合のスコアの最小値が答え。

問題 abc020.contest.atcoder.jp note 値を固定して二分探索するよくあるやつ。2点間の最短距離を求める必要があるのでダイクストラかワーシャルフロイドを使う。

問題 abc025.contest.atcoder.jp note マップの情報をメモ化するのに手こずった。 vectorなどであればmapのキーにできるが、自作の構造体などであると、そのままではハッシュテーブルのキーに出来ない。 詳しくは下を参考 stackoverflow.com qiita.com あと…

問題 abc021.contest.atcoder.jp あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町どうしを結ぶ M 本の道路が存在し、それらは双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。 また、M 個…

問題 abc024.contest.atcoder.jp メモ 貪欲にやれば良いだけ

問題 abc006.contest.atcoder.jp note 3次の連立方程式の１つの項を固定させると、他の条件から残りの変数が確定するので計算量はO(n)

問題 abc007.contest.atcoder.jp note 普通にキューつかって幅優先するだけ

問題 abc016.contest.atcoder.jp メモ 苦手意識のある幾何の問題。外積の公式を使うと,あるベクトルに対して、任意の頂点が左側にあるか、右側にあるかをチェックすることができる。 そのため、線分の直行判定は、１つの線分からみたときに、もう一方の線分…

問題 以下略 abc001.contest.atcoder.jp note 文字列の扱いがめんどくさいだけ。雨がふっている時間を管理する配列をいもす法をつかって保持してやればいい。おしまい。 いもす法の解説は http://imoz.jp/algorithms/imos_method.html とかがわかりやすい。 …

問題文 以下のリンクを参考に http://abc021.contest.atcoder.jp/tasks/abc021_d Note 重複組み合わせを求めればよい。 重複組み合わせについては以下のリンクを 重複組み合わせ n個の数字から重複ありでkこの数字を選べば良いので nHr = n+r-1Cn-1 を解けば…

D - 画像処理高橋君 時間制限 : 2sec / メモリ制限 : 256MB 問題文 2 値画像に対して行う、収縮という処理があります。なお、2 値画像とは、画素の色が白か黒かの 2 種類しかない画像の事です。 収縮とは、それぞれの画素についてその画素と周り 8 方向の画…

D - 大ジャンプ 時間制限 : 2sec / メモリ制限 : 256MB 問題文 XY 座標上に、スタート地点とゴール地点が 1 つずつあります。 スタート地点は (0,0) にあり、ゴール地点は (X,Y) です。 あなたは、ジャンプという移動法を用いて、移動を行います。 ジャンプ…

D - 高橋君ボール1号 時間制限 : 2sec / メモリ制限 : 256MB 問題文 高橋君は野球が得意です。高橋君は、高橋君ボール 1 号という変化球を投げることが出来ます。 このボールは、投げてから t 秒後のボールの位置を f(t) とすると、 f(t)=A×t+B×sin(C×t×π) …

C - 高橋君の給料 時間制限 : 2sec / メモリ制限 : 256MB 問題文 高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。 高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はも…

D - 阿弥陀 時間制限 : 4sec / メモリ制限 : 256MB 問題文 古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？ あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2…

C - 節制 時間制限 : 2sec / メモリ制限 : 256MB 問題文 セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。 高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間…

マージソートの実装 分割統治法と再帰の練習

単方向の連結リストの実装。 Note 構造体のポインタ変数をメンバ変数に持つとき、そのままだと実体をもたないので、 head = (struct Node *)malloc( sizeof(struct Node) ); head = new Node; コンストラクタとかで上みたいな感じで実体をもたせる。 あとは…

問題文 ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 bi と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語…

C - 飛行機乗り 時間制限 : 2sec / メモリ制限 : 256MB 問題文 ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。 空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 …