2019-08-01から1ヶ月間の記事一覧
https://yukicoder.me/problems/no/858 解説 https://yukicoder.me/submissions/368837 A/Bをしていって商をこたえていく。 余りを10倍して小数点以下の答えを求めていく。 Bで割って、あまりを残して、10倍して…というのを繰り返す。 ll A, B; //----------…
https://yukicoder.me/problems/no/857 解説 https://yukicoder.me/submissions/368776 基本的にはZ回素振りをするのだが、X,YがZ以内になっていれば、そこは素振りしないので、デクリメントしよう。 ll X, Y, Z; //---------------------------------------…
https://codeforces.com/contest/1203/problem/E N要素の配列Aがある。 各要素1だけ増減することができる(自然数の範囲で)とき、作ることのできる数の最大種類数は? 1≦N≦150000 解説 https://codeforces.com/contest/1203/submission/58867373 貪欲に作る…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g 前提知識 座標圧縮 imos ダイクストラ 解説 https://atcoder.jp/contests/otemae2019/submissions/6932829 ベースはBFSな感じがする。 だが、BFSにしては盤面が広い。 そこで座標圧縮してダイク…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 前提知識 DP更新最適化 解説 https://atcoder.jp/contests/otemae2019/submissions/6931848 最小値を求める問題で制約も103くらいなので、DPかフローかという雰囲気がある。 まずはDPから考えて…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d 前提知識 桁DP 解説 https://atcoder.jp/contests/otemae2019/submissions/6931592 まずmod109+7なので、とりあえずDPを疑おう。 今回は桁数が大きく、かつ、上から決めていくので、桁DPを疑おう…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_c 解説 https://atcoder.jp/contests/otemae2019/submissions/6931000 カード列Bを使って、Ciを何個作れるかという問題であるが、カード列Bは毎回並び替えるので、特に順番は関係ない。 関係あるの…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_b 解説 https://atcoder.jp/contests/otemae2019/submissions/6930836 変数が多く、何か手を付けていいかわからないかもしれない。 こういう時は何かを固定するのがいい。 最も効果的な決め所を探…
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_a 解説 https://atcoder.jp/contests/otemae2019/submissions/6928689 B≦Aを満たすときに授業に間に合う。 そうでないなら、遅刻と答えよう。 int A, B; //--------------------------------------…
https://atcoder.jp/contests/abc137/tasks/abc137_f 前提知識 ラグランジュ補間 解説 https://atcoder.jp/contests/abc137/submissions/6896149 ラグランジュ補間ができるのでやる。 N個の頂点からO(N2)でN-1次元以下の多項式を復元できる。 https://mathtr…
https://atcoder.jp/contests/abc137/tasks/abc137_e 前提知識 ベルマンフォード 解説 https://atcoder.jp/contests/abc137/submissions/6895110 1回移動すると、辺についているコストが足されて、P分引かれるので、辺のコストをC[i]-Pに変換しておこう。 す…
https://atcoder.jp/contests/abc137/tasks/abc137_d 解説 https://atcoder.jp/contests/abc137/submissions/6894414 後ろから決めていこう。 最終日に選ぶことができるのは、A[i]=1のアルバイトだけ。 最終-1日に選ぶことができるのは、A[i]=1,2のアルバイ…
https://atcoder.jp/contests/abc137/tasks/abc137_c 解説 https://atcoder.jp/contests/abc137/submissions/6894331 s[i]がs[j]のアナグラムである ⇔ ソート済みs[i]とソート済みs[j]が等しい これを利用する。 これを考えると、s[i]をソートして、同じもの…
https://atcoder.jp/contests/abc137/tasks/abc137_b 解説 https://atcoder.jp/contests/abc137/submissions/6894293 [-106,106]の範囲で座標Xとの差がK未満であればいい。 この範囲は全探索できるので、全探索して条件を満たす数をこたえていく。 小さいほ…
https://atcoder.jp/contests/abc137/tasks/abc137_a 解説 https://atcoder.jp/contests/abc137/submissions/6894152 A+B,A-B,A*Bのうち最大の数を答えればいい。 C++のmaxだと2つの比較になるが、{}で与えてやるとリストで渡してくれるので、複数個の比較が…
https://atcoder.jp/contests/abc136/tasks/abc136_d 前提知識 ダブリング 解説 https://atcoder.jp/contests/abc136/submissions/6734473 まずは、実験する。 最終的な状態では、周期2でループすることが分かる。 これは、RLの所で行き来するので、周期2に…
https://atcoder.jp/contests/abc136/tasks/abc136_c 解説 https://atcoder.jp/contests/abc136/submissions/6734426 単調非減少なので、大きくなっていくようにすればいい。 操作ではマスの高さを下げることしかできないため、前半ほど調整が難しくなってい…
https://atcoder.jp/contests/abc136/tasks/abc136_b 解説 https://atcoder.jp/contests/abc136/submissions/6734407 N以下の正の整数は全探索可能。 桁数が奇数であるかは、色々判定方法があるが、[1,9]か[100,999]か[10000,99999]のどれかに入っているかを…
https://atcoder.jp/contests/abc136/tasks/abc136_a 解説 https://atcoder.jp/contests/abc136/submissions/6734374 実装問題。 容器2から移せる水の量はmin(A-B, C)であるため、この分だけ減らした残りを答えよう。 int A, B, C; //----------------------…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_m 解説 https://atcoder.jp/contests/tkppc4-1/submissions/12227374 今までWA解法を垂れ流していました。 ご指摘いただき、修正しました。ありがとうございます。 インタラクティブ問題への取り組み方…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6671950 制約を見ると、N,M,Kと小さめの値になっている。 自分はこれと最大値という所からDPかなと思い、DPで考えると解けた。 間がちょっと…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6667931 まず重要なこととして、最終日は必ず見せてもらう必要があるということである。 最終日でA[N]ページ見せてもらうことにした場合は、…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6665447 制約に弱点があり、2N,2Mが可能であるため、チーム分けについては全通り試せそう。 anmichi校でのチーム分けに対して、sanada校のチ…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6665112 全探索対象を探そう。 なんとなく、PQRSとなっているので、Pで全探索できないか考える。 Pの位置の人が決まればどうなるかを考える…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6664209 無向グラフで最短時間といえばダイクストラである。 実際それ以外で解くにはいろいろ尖った形にする必要があ…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_f 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6663997 ある島からある島へ行くのに、M通りの方法があるが、その中で最も早く到着できる経路で進めばいい。 これはどの移動でもそうであり…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6664457 制約に弱点がないので、なにか特殊な性質があるのだろうと考察する。 まずは実験してみよう。 ll dp[30]; void labo() { dp[0] = 0;…
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_e 前提知識 二分探索 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6663888 扱うものが多いので、固定して考えると考えやすいものを考える。 エナジードリンクをenergy本使用するとする。 …
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6637990 例を眺めると、a
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_c 解説 https://atcoder.jp/contests/tkppc4-1/submissions/6637690 制約の弱点を見ると、Mは2以上10以下なので、全探索できる。 Mを全探索して、NをM進数表記したときにXと一致するか確かめよう。 一…