ぱーぽーの競プロ記

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

ARC

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

ARC #028 C 高橋王国の分割統治

概要 問題文はこちら http://arc028.contest.atcoder.jp/tasks/arc028_3N個の頂点からなる木がある。 各頂点に対して、その頂点を取り除いたときに残った木のうち最大の要素数となるものを求めよ。解法 DFSしていくと子の頂点数を求めることができるので、取…

ARC #028 B 特別賞

ARC

概要 問題文はこちら http://arc028.contest.atcoder.jp/tasks/arc028_2x[0], ... x[i]まであるときのK番目に小さな値を求めよーっていう問題。解法 毎回ソートさせているとTLEになるので、もっと高速な処理を考える。K番目に小さな値より大きな値は必要ない…

ARC #027 C 最高のトッピングにしような

ARC

概要 問題文はこちら http://arc027.contest.atcoder.jp/tasks/arc027_3解法 動的計画法+ちょっと貪欲で解くことができる。問題自体はナップサック問題っぽいやつだが、チケットが2種類あるので少し工夫しないといけない。チケットの使い方に関してだが、 …

ARC #027 B 大事な数なのでZ回書きまLた。

ARC

概要 問題文はこちら http://arc027.contest.atcoder.jp/tasks/arc027_2解法 Union Find Treeで集合管理してやればよい。 (Twitterを見ている感じだと、ゴリ押しで書いて通してる人もいるっぽい。)同集合に数字が混じっているならその数字に固定だし、アルフ…

ARC #027 A 門限

ARC

概要 問題文はこちら http://arc027.contest.atcoder.jp/tasks/arc027_1解法 注意すべき点は特にないので、単純に差を求めてやればよい。ソースコード #include <bits/stdc++.h> #define REP(i, x, n) for(int i = x; i < (int)(n); i++) #define rep(i, n) REP(i, 0, n) #d</bits/stdc++.h>…

ARC #026 C 蛍光灯

ARC

概要 問題文はこちら http://arc026.contest.atcoder.jp/tasks/arc026_3解法 セグメントツリーを用いてほげほげする解法とダイクストラを用いる解法がある。・セグメントツリーを用いた解法この方法ではまだ解いてないので後日・ダイクストラを用いる解法l …

ARC #026 B 完全数

ARC

概要 問題文はこちら http://arc026.contest.atcoder.jp/tasks/arc026_2ちなみにAOJにも同じような問題があったと思う。解法 Nの上限が10^10なのでO(N)で全部試すのはよろしくない。ある自然数 i に対して、 N % i == 0 が成り立つなら i と N / i は両方約…

ARC #025 C ウサギとカメ

ARC

概要 問題文はこちら http://arc025.contest.atcoder.jp/tasks/arc025_3解法 ダイクストラ+二分探索で解くことができる。まず目的地Aからウサギとカメの候補となる全ての中間地点に対してダイクストラで最短経路を求めておく。その後にB,Cの位置を決めてい…

ARC #025 B チョコレート

ARC

概要 問題文はこちら http://arc025.contest.atcoder.jp/tasks/arc025_2解法 あらかじめHxWの長方形に対して累積和を計算させておく。それをもとにチョコレートの濃度判定をさせることでO((HW)^2)で解くことができる。チョコレートの白黒のどちらかの符号を…

ARC #025 A ゴールドラッシュ

ARC

概要 問題文はこちら http://arc025.contest.atcoder.jp/tasks/arc025_1解法 2^7通りしかないので全探索してもよいし、貪欲に大きいほうをとってもよい。ソースコード #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #in</map></stack></queue></vector></algorithm></string></iomanip></iostream>…

ARC #024 B 赤と黒の木

ARC

概要 問題文はこちら http://arc024.contest.atcoder.jp/tasks/arc024_2解法 まず入力された状態が全て0or1の場合は色の変化が止まることはないので、それ以外の状態について考える。連続した色の個数がk個の場合、色の変化が止まるのは (k - 1) / 2 日後に…

ARC #024 A くつがくっつく

ARC

概要 問題文はこちら http://arc024.contest.atcoder.jp/tasks/arc024_1解法 各サイズの靴が何個あるかを左右別でカウントすればよい。ソースコード #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <sstream> </sstream></set></map></stack></queue></vector></algorithm></string></iomanip></iostream>…

ARC #024 C だれじゃ

ARC

概要 問題文はこちら http://arc024.contest.atcoder.jp/tasks/arc024_3解法 「k文字のアナグラムができる」ことと「k文字に含まれるアルファベットの数が等しい」は同値なのでアルファベットの数を数えといて、それをソートさせて、隣り合う要素を比較して…

ARC #023 C タコヤ木

概要 問題文はこちら http://arc023.contest.atcoder.jp/tasks/arc023_3解法 (他の記事を参考にしながら解いた。説明に間違いがあるかもしれない)例えば入力で 1 -1 -1 3 が与えられた場合、単調増加な数列になるのは ・1 1 1 3 ・1 1 2 3 ・1 1 3 3 ・1 2…

ARC #023 B 謎の人物X

ARC

概要 問題文はこちら http://arc023.contest.atcoder.jp/tasks/arc023_2解法 それぞれのマスに到達することができる条件は、 ・左上のマスと目標マスのマンハッタン距離がD以内 ・左上のマスと目標マスのマンハッタン距離とDの奇偶が一致する の上記2つを満…

ARC #023 A 経過日数

ARC

概要 問題文はこちら http://arc023.contest.atcoder.jp/tasks/arc023_1解法 問題文に記載されている公式を間違えずに書くことができれば解けるソースコード #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #i</set></map></stack></queue></vector></algorithm></string></iomanip></iostream>…

ARC #022 C ロミオとジュリエット

概要 問題文はこちら http://arc022.contest.atcoder.jp/tasks/arc022_3コンテスト中に満点解法で解くことが出来なかった。解法 木の直径を求めることでこの問題を解くことができます。やり方はとても簡単でDFSを2回やればよいです。具体的なやり方は以下の…

ARC #022 B 細長いお菓子

ARC

概要 問題文はこちら http://arc022.contest.atcoder.jp/tasks/arc022_2解法 尺取法を用いる。ソースコード #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <sstream> #include <complex> #include <cstdio> #include…</cstdio></complex></sstream></set></map></stack></queue></vector></algorithm></string></iomanip></iostream>

ARC #022 A スーパーICT高校生

ARC

概要 問題文はこちら http://arc022.contest.atcoder.jp/tasks/arc022_1解法 貪欲に解いていく。大文字と小文字が混じっているので以下のように先に大文字、または小文字にのどちらかに統一する方法もある。 rep(i, str.size()) { str[i] = toupper(str[i]);…

ARC #011 C ダブレット

ARC

概要 問題文はこちら http://arc011.contest.atcoder.jp/tasks/arc011_3 解法 幅優先探索+経路復元で解くことができます。単語をノードとし、一文字違いの単語同士を繋ぎます。 キューには現在見てる単語のインデックスを入れてやればよいです。経路復元に…

ARC #011 B ルイス・キャロルの記憶術

ARC

概要 問題文はこちら http://arc011.contest.atcoder.jp/tasks/arc011_2 解法 やるだけ問題です。 しかし文字列処理を注意してやらないとバグの原因になってしまいます。 ソースコード #include <iostream> #include <string> #include <vector> #include <cctype> #include <cstring> using namespace s</cstring></cctype></vector></string></iostream>…

ARC #011 A 鉛筆リサイクルの新技術

ARC

概要 問題文はこちら http://arc011.contest.atcoder.jp/tasks/arc011_1 解法 やるだけ問題です。ソースコード #include <iostream> using namespace std; int main(){ int m,n,N; cin >> m >> n >> N; int ans = 0; int small = 0; while(N){ ans += N; N += small; s</iostream>…

ARC #010 C 積み上げパズル

概要 問題文はこちら http://arc010.contest.atcoder.jp/tasks/arc010_31次元のパズル的なやつがあって高得点狙いましょう!みたいな問題です。 (問題文が読みやすいのでそちらを参考にしてください) 解法 動的計画法(DP)で解くことができます。まずこの…

ARC #010 B 超大型連休

ARC

概要 問題文はこちら http://arc010.contest.atcoder.jp/tasks/arc010_2最長の連休日数を求める問題です。 制約等は問題文に詳しく書いてあります。 解法 カレンダー問題です。日付問題が苦手な人はわりと多いのではないでしょうか(※私も得意ではありません…

ARC #010 A 名刺交換

ARC

概要 問題文はこちら http://arc010.contest.atcoder.jp/tasks/arc010_1名刺を交換していくお話。 解法 やるだけ問題です。(Javaで書きたい衝動に駆られたのでJavaで…) ソースコード import java.util.*; import java.lang.*; import java.math.*; public …

ARC #004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

ARC

・概要 平面上に N+1 個の点があり、それぞれ 0 から N までの番号が付けられています。 それぞれの点の位置はわかりませんが、0 以上 N 未満の整数 i について、i 番の点と i+1 番の点の距離 di はわかっています。 0 番の点と N 番の点の距離とし…

ARC #004 A - 2点間距離の最大値 ( The longest distance )

ARC

・概要 複数の座標(x,y)が与えられ、その中から2つの座標を結んでできる線分の長さの最大値を求める問題です。 座標の数Nは100以下です。 ・解法 座標の数が多くないので、全部調べれば求めることができます。 ・ソースコード #include<iostream> #include<algorithm> #inc</algorithm></iostream>…