tookunn’s diary

主に競技プログラミング関係

Codeforces #352 Div2 C

問題文 codeforces.com 考察 ・,tx,ty)]を番目のbottleからまでの距離とする。 ・・よく考えるととそれぞれ最初に拾うbottleと最後に拾うbottle以外はとを往復するのでとなる。・あとはから最初に到達する最短のbottleを選んで,から最初に到達する残りbottle…

Codeforces #355 Div2 C

問題 codeforces.com 考察 今回は解説見ないで出来た。・試しに自分での数列を考えて、考察したら思いついた。(というか本当によくよく考えたらそう)・実は数列の部分列のように1ずつ増加している最大長の部分列(ここでは最大長の)について問題文にある操作(…

Codeforces #358 Div2 C

問題文 codeforces.com 考察 ・頂点をrootとして,頂点は頂点に,頂点は頂点に,..., 頂点は頂点につながっているとする。・以上から を頂点から頂点までの間のedgeのcostの合計の最大値として, が成り立つ。・あとはrootから辺を辿ってそれぞれの葉まで探索し…

Codeforces #349 Div2 A~C

codeforces.com 全体的に問題文の量が比較的多くて辛かった...。誤読も多かったし。 A 問題 codeforces.com 考察 ・まず、半径をr,円周率(3.14...)をpiとすると1秒間に増加する量はr * r * pi * eとなり、v(1秒間に減少する量)より多ければ、容器の中の水は…

Codeforces #366 Div2 A~C

codeforces.com A 問題 codeforces.com 考察 ・回ループを回して、ループ回数の偶数、奇数の場合分けをすれば良い。 ・最終的に出力される文字列をうまいことループで表現できないかを考える。 ソースコード import java.io.IOException; import java.io.Inp…

Codeforces #341 Div2 C

問題 codeforces.com 考察 ・が素数Pで割り切れる場合はとで1000ドルずつ、合わせて2000ドル発生する。・が素数Pで割り切れるときは、または最低でも一方がPで割り切れなければならない。・つまり、とがどちらもPで割り切れないのならば、2000ドルは発生しな…

Codeforces Educational Round 10 C

問題 codeforces.com 考察 ・区間にFoePairsが含まれている場合、区間にはForPairsが含まれているので、カウントしない。・つまり,区間の始点からFoePairsが含まれているような最小の終点を分かれば良さそう。・尺取り法を使うっぽい。・問題ページのサンプ…

AtCoder Grand Contest 001 C Shorten Diameter

AGC

問題 agc001.contest.atcoder.jp 考察 ・直径がとなる木を考えた時の、中心となる木の頂点を中心点と呼ぶ。・中心点から距離が以下となる頂点の数を最大になるような中心点を選べば、削除する点が少なくて済む。・が奇数の時は、中心点の隣接する頂点一つを…

Sparse Tableを知ったので、忘れないように。

codeforces.com この問題の想定解法がSparse Tableを使ったもので、ちゃんと理解したいなと思ったので忘備録的な感じで書きます。 色々調べながら書いているので、間違っているところがあったら指摘して頂けるとありがたいです。 Sparse Tableとは まず、Spa…

yukicoder No390 最長の数列

問題 No.390 最長の数列 - yukicoder やったこと まず最初に考えたのは「よい数列」というのはa[i] 再帰をしましたが、 計算量はO(N^2)であるので、TLEでした。 N = int(input()) x = sorted([int(i) for i in input().split()]) dp = [[-1 for j in range(N…

Codeforces #360 Div2 C

問題 codeforces.comいろいろ誤読や勘違いが多くてAC出来なかった 解法 この問題で出てくる頂点被覆は問題文に書いてある通りで、「あるグラフのすべての各辺について、その辺につながっている2つの頂点どちらかまたは両方の頂点を選択した頂点の集合」がグ…

AtCoder Beginner Contest 014 D 閉路

ABC

問題 abc014.contest.atcoder.jp 考察 追加辺を(a,b)間につなげた場合に出来る閉路の長さ(辺の長さ)を求めるということなので、aのノードとbのノードから追加辺以外の辺を辿って最も早く合流できるノードcが分かれば、 cとaの間の長さ + cとbの間の長さ = (a…

AtCoder Beginner Contest 017 D サプリメント

ABC

問題 abc017.contest.atcoder.jp 考察 部分点まで自力で行けたけど、満点解法は解説を見ながら、AC。解法としてはしゃくとり法をしつつ、DPをしていく。dp[i] = i番目のサプリメントまでを見た時の摂取方法の組み合わせdp[i] := dp[i - 1] + dp[i - 2] + ...…

Codeforces #356 Div2 C

問題文 codeforces.comリアクティブ方式。 考察 最初は素数を使って割り切れるかどうか試していこうと思いましたが、[2,100]での素数の数が25個なので、97,89などの素数がhidden numberだと20クエリ以内に収まらない。よく考えると,エストラネスのふるい等を…

AtCoder Beginner Contest 023 D 射撃王

ABC

問題 abc023.contest.atcoder.jp 考察 まず解法として最初に思い浮かんだのは、その時点の高さが最大の風船を割っていく貪欲だが、 風船iと風船jがあり、H[i] S[j]であると、ある時点では風船jの方が割られる風船だが、 最終的な高さは風船iの方が高くなる可…

AtCoder Regular Contest 055 B せんべい

ARC

問題 arc055.contest.atcoder.jp 考え 本番中は全く分からなくて、解説放送をみてもあんまり理解できなかったので、 下記の解説を参考させていただきました。とてもわかりやすいです。ソースコード中に考えをまとめながらコーディングしたのでそちらを参照し…

yukicoder No375 立方体のN等分 (1)

問題 No.375 立方体のN等分 (1) - yukicoder 考え 同じ方向からN - 1枚の平面で切断するのが最大なので、TMaxはN - 1下図のA方向からの平面の切断数をa、B方向はb、C方向はc、とすると TMinはa + b + cの最小の値となる。 なので、aの値を全探索をして、残…

AtCoder Beginner Contest 038 D プレゼント

ABC

問題 abc038.contest.atcoder.jp 考え 部分点までは自力で行けたけど、満点解法は分からずで、解説などを見て通しました。主に2通りの解き方があるらしい。1つ目は公式解説であるようなセグメントツリーというデータ構造を使う方法。セグメントツリーは蟻本…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 B DDPC特別ビュッフェⅡ

本戦で部分点取ってから何も手を付けてなかったので、解説見ながらやってみた。 問題 discovery2016-final.contest.atcoder.jp 考え 求める最小の時刻を二分探索を使って、貪欲に求めていく。 ある時刻xに選択することができる最大の美味しさを持つ料理を取…

AtCoderBeginnerContest 005 D おいしいたこ焼きの焼き方

ABC

問題文 abc005.contest.atcoder.jp 考え 一度に焼ける個数Pが、ある区画内( 最左上(y , x)で最右下(y + H,x + W)である範囲 )の焼ける場所の個数(H * W個)以上であれば、その区画内の場所をすべて使ってたこ焼きを焼くことが出来る。 まず、たこ焼きの美味し…

AtCoderBeginnerContest003 D AtCoder社の冬 (メモ用)

問題 abc003.contest.atcoder.jp 考え 部分点解法はX * Y = D + Lなので、X * Yの範囲内でD個のデスクを置く組み合わせ(X * Y)C(D)と残ったX * Y - Dの範囲内でL個のラックを置く組み合わせ (X * Y - D)C(L)を掛け、それを(R - X + 1) * (C - Y + 1)回掛けつ…

CODE FESTIVAL 2014 予選B C 錬金術師

問題 code-festival-2014-qualb.contest.atcoder.jp 解法 まずS1,S2,S3のそれぞれのアルファベットの出現回数を数えておく。 その出現回数をそれぞれA1,A2,A3とする。S3を作れる場合は、S3に出現するアルファベットは必ずS1またはS2から使われるので、 S1か…

RUPC2016に参加してきました

3月6日から3日間立命館大学の方で立命館大学競技プログラミング合宿(RUPC)があったので参加してきた体験を記憶を頼りに書き記していきたいと思います。 0日目 前泊しました。 立命館大学が滋賀県にあるので、新潟から上越新幹線で東京駅まで行き、乗り換えて…

Indeedなう(オープンコンテストB) B - How are you?

問題 indeednow-finalb-open.contest.atcoder.jp 解法 N(1≦N≦10^5)人ごとに、出社時刻時点直後と退社時刻直前のオフィスにいる社員の増加量を求めることで、 オフィスにいる間に出社してきた人数を導くことが出来る。社員i(1≦i≦N)がオフィスにいる間に出社し…

AtCoderBeginnerContest030 D へんてこ辞書 (メモ用)

問題 abc030.contest.atcoder.jp 考え 単語を調べるステップ数kが(1 ≦ k ≦ 10^100000)の範囲なので、long型でも収まらない。だけど今回は公式の解説でもあるように多倍長を使わずに解ける。 参考:AtCoder Beginner Contest 030 解説 一度調べた単語をもう一…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016に参加してきた

本選の問題全然解けてないんで書こうか迷ったんですけど、楽しかったので記憶を頼りにあっさりとですが書きます。 はじめに 予選で233位だったんですが、2017年度卒業の枠が繰り上がって運よく参加することが出来ました。 前日 新潟から東京まで新幹線だと始…

Codeforces #341 Div2 B

問題 codeforces.com 1000×1000のマスにN個のビショップが置かれている。 2つのビショップ同士が互いに斜め方向に位置する場合、お互いを攻撃し合う。 この互いに攻撃し合う組み合わせを数える。 ここで、マスの列は左から右へ、行は上から下に、1から1000ま…

2015年の反省(ほとんど競プロの話)

僕はだいたい今年の1月ぐらいに競技プログラミングを始めました。 つまり1年ぐらい競技プログラミングをやってきたということなので、年末っぽくその振り返り的なことを書こうかなと思います。 1. いろんなオンラインコンテストへの参加 AtCoderBeginnerCont…

AOJ 2311 Dessert Witch

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311 なんかオセロっぽいやつで、問題文で指定された手順でオセロの最終盤面を出力する 実装問題です。 普通に面倒でした。デバッグしまくってやっと通しました。 解法 問題文で指定されてい…

Codeforces Educational Round2 B

問題 codeforces.com 配列aと配列bの長さnとmが与えられ、整数型の配列aとbが与えられる。 0 解法 配列aをソートして、各b[i]ごとに配列aに対して二分探索を行って、b[i]と同じ値がある場合は b[i]と同じ値の中で一番要素番号が大きいもの + 1、無い場合はb[…

Codeforces Educational Round2 A

問題 codeforces.com aからzまでの文字(大文字も含む)と1から9までの数字と「,」(カンマ)「.」(コロン)「;」(セミコロン)を含む文字列が与えられる。 与えられた文字列をカンマまたはセミコロンで区切り、数字として表されるものと それ以外のものに分けてカ…

Codeforces #333 Div2 A

問題 codeforces.combx進数で表された値Xとby進数で表された値Yが与えられるので、 値としてXとYは等しいか等しくないかを求める。等しくない場合はXとYがどちらが大きいか小さいかを求める。 XとYが等しい場合は "=" Xの方が大きい場合は ">" Yの方が大きい…

Codeforces #320 Div2 D

問題 http://codeforces.com/contest/579/problem/D 整数N,K,XそしてN個の整数Aが与えられる。 N個の整数Aのうち、一つの整数A[i](1 そして残りのN-1個の整数とA[i]をOR演算した場合の最大値を求める。 解法 全探索だと間に合わなかったので、A[0]からA[N - …

AOJ 1232 Calling Extraterrestrial Intelligence Again

AOJ

問題 4より大きく10^5未満の値mと1以上1000以下の整数a,bが与えられる。 素数の組p,qを考える。 pq 解法 あらかじめ素数を用意して置く。 pとqを固定して二重ループ。 与えられた条件に当てはまるp,qの組の中のpqが最大の組を選ぶ。 ソースコード #include<iostream> #</iostream>…

AOJ 1241 Lagrange's Four-Square Theorem

AOJ

問題 与えられたNの値を4個以下の正の整数の二乗で表せる組み合わせの数を考える。 解法 全探索で全通り試した。(計算量考えるの苦手です) とりあえず全探索で通って良かった。 ソースコード #include<iostream> using namespace std; int main() { int n; while (cin </iostream>…

C++ scanf() scanf_s() 自分メモ

#include <iostream> using namespace std; int main() { int N; cin >> N; } みたいな感じでcin>>を使う。 競技プログラミングなどで実行速度を速くしたい時は、cinではなくscanf()を使った方が良い。 int main() { int N; scanf("%d", &N); printf("%d\n", N); } し</iostream>…

Java テキストを読み込み、書き込むサンプルプログラム

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; public class ReadWriteFile { File to…