ferinの競プロ帳

競プロについてのメモ

ukuku09コンテスト 001-photography

Hamako Online Judge区間と言われたので累積和を取りたくなる。累積和をSで書くことにするとl番目の要素を区間の左端とするとき P+S[l-1] 以上のもっとも右にある要素の位置が分かればl番目が区間の左端のときの最適な区間が求まる。右端がO(1)かO(logn)くら…

SRM716 div2 hard

概要 最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。 解法 条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個…

SRM 716 div2 med

概要 文字列sと文字列tが与えられる。sの各文字をtの文字で置き換えることができる。tの文字はそれぞれ1回ずつしか使用できない。書き換えた後の辞書順最大となるsを出力する。 解法 先に現れる文字を大きいものにしたほうが辞書順としては後のものになる。…

SRM 717 div2 easy

概要 要素が0か1の2次元配列tが与えられる。x[i] xor y[j] == t[i][j] となる要素が0か1の配列x、yを構成することが可能か判定する。与えられる配列のサイズは5×5以下。 解法 1行目(y[0])を0か1で固定すれば残りの列の数字(x[i])は一意に定まる。残りの行に…

経験した罠

自分がやらかした実装ミス(罠踏んだら追加する) #define int ll 区間l, rに対してmodを取るときにl > rとなっているときを考慮しない 負の数にMODをとって正の値がほしいところに負の値をつっこむ int -> double へのキャストをしない 配列サイズ足りない …

codeforces 415 div2 C

Problem - C - Codeforces入力列をソートしておいても関係ないため、あらかじめソートされた入力列について考える。 また、関数F(a)は頂点の集合の最大値・最小値にのみ依存する。例として数列8, 6, 5, 3, 2, 1が入力されたときを考える。 このときの答えは …

TDPD I イウィ

tdpc.contest.atcoder.jp区間DPの問題。AOJ 1161ダルマ落としと似てる。dp[l][r] = {lからrまでの区間で操作をできる回数}としてDPする。 区間lからrで間の区間(l+1からr-2orl+2からr-1)が全て削除でき、削除したあとに残る文字列がiwiならばその区間は全て…

AOJ 1161 ダルマ落とし

Daruma Otoshi | Aizu Online Judgedp[l][r] = {lからrまでの区間の状態}と持ってDPする、区間DPの問題。 この問題ではdp[l][r] = {lからrまでの区間で叩ける最大のブロック数}とする。 dp[l+1][r-1]の区間が全てのブロックを叩き出すことができ、l番目とr番…

AGC014 A,B,C,D

agc014.contest.atcoder.jp公式解説(pdf) Editorial - AtCoder Grand Contest 014 | AtCoder公式動画解説 www.youtube.com A問題 問題の得点からそんな難しい問題ではないだろうと決め打ちしてlog_2(max(a, b, c))回でシミュレーションが実行できそうだと考…

AOJ2254 Fastest Route

Fastest Route | Aizu Online JudgeまずNdp[S] = (集合Sをクリアするのにかかる最短時間)とする。 dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので…

競プロ関係のサイト

コンテスト・オンラインジャッジ AtCoder Codeforces TopCoder AOJ yukicoder 埋めに便利 AtCoder Problems 修行 AOJ/Atcoder-JOI AOJ-ICPC AOJカテゴリー別問題集 情報収集 TopCoder部のカレンダー - TopCoder部 Twitter

AOJ 0043-Puzzle

パズル | Aizu Online JudgeDFSで面子と雀頭の取り方を全て試す。

DPL_4 B Coin Combination Problem II

Coin Combination Problem II | Aizu Online JudgeN

DPL_1 E Edit Distance (Levenshtein Distance)

dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。 各文字列に対する操作についてDPの遷移を考えると 挿入 dp[i][j] = dp[i][j-1] + 1 削除 dp[i][j] = dp[i-1][j] + 1 置換 dp[i][j] = dp[i-1][j-1] + 1 となります。さらに…

SRM 710 div2

Easy 問題概要 解法 Med 問題概要 解法 Hard 問題概要 解法 Writerの方の解説 codeforces.com Easy 問題概要 n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる…

AGC011 A, B, C, D

A問題 B問題 C問題 D問題 agc011.contest.atcoder.jp A問題 早い時間に到着する乗客をバスに乗せずに待たせて置くほうがいいパターンは存在しません。したがって到着時間をあらかじめソートしておくと、条件を満たすぎりぎりの乗客まで乗せて出発するを繰り…

codeforces #393 div2 A, B, C

問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 codeforces.com 問題A 問題概要 月とその月が何曜日から開始するかが与えられる。この月で1週間ごとに列が切り替わるカレンダーを作成する際、カレンダーは何列になるか。 解法 1, 3, 5, 7, 8,…

codeforces #403 Div2 A, B, C

A問題 問題概要 解法 B問題 問題概要 解法 C問題 問題概要 解法 codeforces.com A問題 問題概要 n組の靴下が袋の中に入っておりそれぞれペアごとに揃えたんすにしまいたい。袋の中から1つずつ取り出して机に並べる。そして、靴下が組になった時点でたんすに…

codeforces #402 div2 A, B, C, D

問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 問題D 問題概要 解法 codeforces.com 問題A 問題概要 n人の生徒が属する2つのグループA, Bがある。各生徒は1から5の5段階の成績がつけられている。グループ間で生徒を交換することでそれぞれの…

Codeforces #401 A, B, C, D

A問題 問題概要 3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位…

ARC023 B問題-謎の人物X

arc023.contest.atcoder.jpD回移動した後にたどり着ける点はD回移動の範囲内に収まり偶奇が一致する点です。したがってたどり着ける点についての全探索でO(RC)で解けます。

ARC022 B問題-細長いお菓子

arc022.contest.atcoder.jp重複した数が存在しない最大の領域を求める問題です。重複した数が存在するかどうかの判定ををunordered_setで行いました。unordered系のデータ構造はじめて使ったんですが衝突さえしなければO(1)でできるの便利ですね… 解いている…

XOR

排他的論理和(XOR)についての性質のメモ A^B = (A&!B)|(!A&B) = (A|B)&(!A|!B) = (A|B)&(!(A&B)) A^B = B^A(交換則) (A^B)^C = A^(B^C) (結合則) A^A = 0 A^B = 0 ならば A = B a, b, c…が0か1のとき、 a^b^…^c = 1 (1が奇数個) 0 (1が偶数個)

TopCoderの設定

登録方法 applet ダウンロード Javaの更新 セキュリティ例外 設定 プラグインの導入 practice(過去問) TopCoderについての設定や問題の解き方についてのメモです。OSはWindows10です。 登録方法 TopCoderにアクセスし右上の「LOG IN」をクリック、「COMMUN…

yukicoder No.58 イカサマなサイコロ

No.58 イカサマなサイコロ - yukicoderモンテカルロ法をはじめて使ったのでその記録です。 モンテカルロ法とは乱数を用いてシミュレーションを行う方法です。この問題では次郎君の試行として1から6までの範囲の乱数をN回求め、太郎君の試行として4から6まで…

トポロジカルソート

トポロジカルソートについて調べた内容のメモです。 トポロジカルソートとは 閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えれば…

ABC015-D問題

abc015.contest.atcoder.jpナップザック問題でk個のみつかえるという制約を加えたような問題です。ナップザック問題で持つ状態に加えて今までに使用したスクリーンショットの枚数を状態として持つことで解けます。まずメモ化再帰で実装しました。次に動的計…

ABC008-D問題

abc008.contest.atcoder.jp 蟻本で似た問題(P121, Bribe the Prisoners)を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたと…

ABC037-D問題

abc037.contest.atcoder.jp解説通りf(y, x) を再帰的に求めて全てのf(y, x)を足す感じで実装しました。定番のメモ化再帰という印象の問題でした。

ABC038-D問題

abc038.contest.atcoder.jp解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ!ってのとソートの方法を指定する方法についてのメモ。 BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである…

ABC040D

abc040.contest.atcoder.jpUnionFindをある程度理解したあとだったので解法が何をやっているのかは割と早く理解できましたが、実装に手間取ってしまいました… 年をキーとして2つの値をもつ組を降順にソートする必要があります。最終的にvectorvector > を使…

ABC041D

abc041.contest.atcoder.jp解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。 まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになり…

Atomで使ってるパッケージについて

Package atom-beautify autocomplete-clang linter, linter-gcc file-icons highlight-line japanese-menu minimap minimap-autohide Design font Theme style.less Package あとで忘れて困る未来が浮かんだので忘備録として書いておくことにしました。C++用…

ABC049D

abc049.contest.atcoder.jp自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。 youtu.be https://youtu.be/jvAX9Z7beLgグラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。 道路で…

ABC030を解いてみた

abc030.contest.atcoder.jp A問題 if文で比較しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { double a, b, c, d; cin >> a >> b >> c >> d; i</bits/stdc++.h>…

ABC029を解いてみた

abc029.contest.atcoder.jp A問題 文字列の最後にsを連結しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { string s; cin >> s; cout << s + 's</bits/stdc++.h>…

ABC028を解いてみた

abc028.contest.atcoder.jp A問題 条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.141592653</bits/stdc++.h>…

ABC027を解いてみた

abc027.contest.atcoder.jp A問題 長方形は向かい合っている辺の長さが等しいです。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int a, b, c; cin >></bits/stdc++.h>…

ABC025を解いてみた

abc025.contest.atcoder.jp A問題 入力をソートして(n-1)/5文字目、(n-1)%5文字目が答えの文字列になります。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { vector<char> str; string ans = "", temp; int n; c</char></bits/stdc++.h>…

ABC026を解いてみた

abc026.contest.atcoder.jp A問題 x=1からx=a-1まで全探索で実装しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, ret = 0, maxret = -1; cin >> a; for(int x=1; x</bits/stdc++.h>

ABC024を解いてみた

abc024.contest.atcoder.jp A問題 条件に沿って実装しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, b, c, k, s, t, ans = 0; cin >> a >> b >> c >> k; cin >> s >> t; if(s+t >= k) ans</bits/stdc++.h>…

ABC049を解いてみた

abc049.contest.atcoder.jp A問題 入力がa, i, u, e, oならvowel、そうでなければconsonantを出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { string str; cin >> str; if(str == "a" || str</bits/stdc++.h>…

ABC023を解いてみた

abc023.contest.atcoder.jp A問題 string型で入力を受けとり1桁ずつに区分けし加算していきました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int x, ans = 0; string str; cin >> str; for(int i=0;</bits/stdc++.h>…

ABC040を解いてみた

abc040.contest.atcoder.jp A問題 n-1とx-nのうち小さい方を出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int n = 0, x = 0; cin >> n >> x; if(x-1 >= n-x) cout << n-x << endl; else c</bits/stdc++.h>…

ABC022を解いてみた

abc022.contest.atcoder.jp A問題 N日目のとき、適正体重かどうかを判定しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int n=0, s=0, t=0, w=0, a[1000], ans=0; cin >> n >> s >> t; cin >> w</bits/stdc++.h>…

ABC041を解いてみた

A問題 入力をString型で受けとりS[i-1]を出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { string S; int i; cin >> S; cin >> i; cout << S[i-1] << endl; return 0; } B問題 直方体の体積の</bits/stdc++.h>…

ABC042を解いてみた

abc042.contest.atcoder.jp A問題 入力をソートして5, 5, 7になっていればYES, なっていなければNOを出力しました。 a = [int(i) for i in input().split()] a.sort() if a[0] == 5 and a[1] == 5 and a[2] == 7: print("YES") else: print("NO") B問題 ソー…

ABC048に参加してみた

abc048.contest.atcoder.jp A問題 スライスを使って先頭の文字だけを取得して連結しました。 s = [i for i in input().split()] ans = s[0][0:1] + s[1][0:1] + s[2][0:1] print(ans) B問題 ans = b/x - a/x で求まります。aがxの倍数の時だけans++とすれば…

ABC043を解いてみた

abc043.contest.atcoder.jp A問題 1からNまでの和をn(n+1)/2で求めます。 n = int(input()) print(int(n*(n+1)/2)) B問題 sの長さは10以下と非常に短いため、条件に従って答えとなる文字列を操作していけばよさそうです。この方針で実装しました。 s = list(…

ABC044を解いてみた

abc044.contest.atcoder.jp A問題 k k >= n のとき ans = n*x と場合分けできるのでそれに従って実装するだけです。 n = int(input()) k = int(input()) x = int(input()) y = int(input()) if k < n: ans = k*x+(n-k)*y else: ans = n*x print(ans) B問題 …