問題概要 N*5(N 考えたこと (初めて通したMedium。当時は高校数学っぽくO(1)解で通した) 前回通したときは組み合わせっぽく解いたので今回はDPで解くことにする。 識別できる状態がそんなに多くないのでvectorをキーにしたメモ化再帰で書くのが楽そう。 状態…

問題概要 L( 考えたこと (当時は全く手が出なかった問題) 約数の個数が奇数=平方数。 なので候補の上限10^Lのうち調べるのは10^(L/2)だけでよい。 後は変換するだけ。0でパディングするのが面倒なので両方桁数13に増やそう。 サンプル通った。投げる。WA。 …

問題概要 1~N( 考えたこと 何で有理数？面倒くさい…。 とりあえず20!を計算すると64ビットに収まる。 ということは確率は見せかけで場合の数を求める問題か。 どうも置換の問題っぽい？数学のことばに直すと、M個以下の巡回置換で表せる置換の数？ Mは大した…

問題概要 文字列がN( 考えたこと 色々やり方がありそう。 数字に変換して比較するか。 一番愚直な方法で書く。余計なことはしない。 問題なく通った。

本当に色んな方面に対して申し訳なさでいっぱいです。 まず持っていった日本語キーボードが当然のように認識されない。OKこれくらいは想定内。 Ubuntuを起動。今日はここに閉じこもるつもり。 vimが入ってないことを確認。まあ、これも想定はしていた。 Make…

問題概要 砲台がC( 考えたこと (当時は問題を勘違いしていたことが今判明した) グラフっぽい。しかも最小費用流っぽい気がする。 でもどうキャパシティを定義すればいいんだ？ そもそも基地狙いかプラント狙いかで流量が変わってしまうんだから最小費用流で…

問題概要 点がN( 考えたこと (本番はsqrtを使って浮動小数点使ったためEPS入れてないとかどうのこうので余計な不安を感じてしまった。一応通ってはいたけど) 基本はいつでも全探索。2点を固定して、もう一方の長さも固定すると後は簡単に計算できる。 なるべ…

バグの出にくいコードを書きましょう。 大雑把に考えましょう。 バグの出にくいコードを書きましょう。 最適化は最後の最後で。 バグの出にくいコードを書きましょう。 .PHONY: all all: tester tester: main.o HOGE.o util.o g++ -g -pg -O2 -Wall main.o H…

問題概要 板がN(区間を割り振って一斉に仕事を始めてもらう。塗るのにかかる最小の時間を求める問題。 考えたこと 15とかビットDP臭。 連続する区間の問題なので、区間DP？ それだと状態数がN^2 * 2^Pで多すぎる。 左から見ていけばいいのか。これだと状態数…

問題概要 整数N( 考えたこと 問題文短くていいなあ。 MOD K。やるだけっぽい。一応オーバーフローに注意。 何か合わないと思ったら更新の仕方がcur = (cur * d + cur) % Kになってた。+ curではなくて + Nだ。 訂正。無事通った。

問題概要 (xa[i], ya[i])か(xb[i], yb[i])を中心とする互いに交わらないような正方形の大きさの最小値を最大化する問題。N 考えたこと (当時は全然分からなかったけど2-SATという単語が終了後Twitterなどで飛び交っていてなんじゃそりゃと思った記憶がある) …

問題概要 任意の部分列を取り出してきて、部分列の中に出てくる数字の積をとる。全ての部分列に対する積が互いに異なるときその数字をColorfulStringという。n( 考えたこと (この問題でnext_permutationを知った。当時は場合分けで解いて落ちていた) 1、0が…

問題概要 1.5 考えたこと (本番中は、ソートしてある区間の端っこ同士を足していくことまでは気付いたけど、どこまでの区間で足し算するかを全探索する発想がでなかった) はじめてSystem Test Failedした問題なので記憶に残っている。 今見返すと、入力がdou…

問題概要 ウサギがN( 考えたこと (これは本番でも簡単に通せた) 番号の小さいやつほど制約が強いので、番号の小さいやつから割り振っていく。 重要なのは区間に関して包含関係が成り立つような順序が入れられること。

問題概要 N( 考えたこと 問題文がよく分からない…。 やっと理解した。このままじゃよく分からんので抽象化する。 グラフの問題に落としたら支配集合のことだと気付いた。 つまり交わらない支配集合を最大いくつ作ることができるか、ということか。 サイズ15…

問題概要 xの最大の素因数がkを越えないとき、xをk-smooth numberと呼ぶ。N( 考えたこと 基本的には書くだけに見える。全探索で普通に素因数分解してO(N^(3/2))。 だが1はどうなんだ？1に素因数なんてないんですけど…。サンプル見ても不明。 k=1のとき1はsmo…

問題概要 N( 考えたこと (当時は問題の意味くらいは分かったけど解き方は全然思い浮かばなかった) Cとかscoreが小さいしDP？ 1個無作為に選んだときの期待値じゃなくて、S回スワップした後の箱の中のアメのスコアの総和を計算するようにしよう。 ある箱のス…

問題概要 ビット列が与えられる。これをa進数(aは0より大きい実数)として解釈したとき、age( 考えたこと (これは当時落とした記憶がある。コーナーケースの厳しい問題で、大撃墜祭りになったことを覚えている。初撃墜を決めたのもこの回だったような) 二分探…

問題概要 [start, finish](0 考えたこと 解き方とかはまだ全然分かってないけど、とりあえず半開区間にデータ構造を変換しよう。ユニークもしなくちゃいけないし。 極大と言うのが面倒くさそう。それが無ければDPで行けそうだし。区間の上限100とかもそれっ…

問題概要 N( 考えたこと とりあえずJokerをどれにするか全探索する方針が見える。 Jokerを固定したときの移動回数をどうやって求める？ 1種類しか無いときは基本的に動かさなくてよくて、それ以外の時は全部Jokerに放り込む。 ただし1種類しかないときも、そ…

問題概要 2次元平面上にN( 考えたこと (当時は問題文読んだけど問題の意味が分からなかったような記憶がある) 方針がすぐには見えない。 とりあえず到達不可能な判定は直接つないでみて大丈夫かどうかで判定できる。 置く数を固定して考えたら行ける？ 新し…

問題概要 H*W(H,W 考えたこと (はじめて参加したDiv 1のSRM。Div 1ではじめて通したのはこの問題) 問題読むの2回目で問題の内容大体覚えてた。 円盤は大きいものからつかうのが最善な気がする。 赤からはじめるか青からはじめるかの2通りあるけど、両方シミ…

問題概要 凸多角形(頂点数N 考えたこと サイズからしてビットDP？ 多角形で覆うとか言ってるけど三角形に分割できるので三角形だと思っていい。 更新するのは三角形全部作ればいい。 三角形の数の大さがちょっと気になる。電卓でcombination(15,3) * 2^15を…

問題概要 DBの表がある。各列の組み合わせを抽出したものが各行に対してユニークに定まるのであれば、その組み合わせを主キーと呼ぶことにする。極小な主キーの組み合わせとして、最大の数と最小の数を求める問題。行数Rは50以下、列数Cは10以下。 考えたこ…

問題概要 JohnとBrusは、それぞれN( 考えたこと JohnとBrus別々に考えて最後にまとめる方針が見えるけど、SRMの問題としてはそういうのは珍しい気がする。 しかしSRM的云々は置いておくとしてもこれ完全に問題分離できそう。 状態を(何番目の街か、既にいく…

問題概要 質問がQ( 考えたこと 解けそうで解けない。制限が小さいから全探索っぽいことをするんだろうけど。 yesと答えた質問がいくつあるか、を固定すれば場合の数に落ちそう。 でもこれは何度も考えてその度に解けなかったやつだ。 具体的には、N個のボー…

問題概要 W*H(W,H 考えたこと 最初は行も入れ替わることに気付かずに、状態数が減らせなくて困った せめて今いるマスも一緒に入れ替わるなら簡単なのに…とか思っていた 行と列がともに入れ替わるなら今いるマスが入れ替わらないというのは非常に自然だ。これ…

問題概要 単語が複数与えられる。単語の間にアンダースコアを入れて連結した長さをある値ぴったりにしたい。各単語間にはさまれるアンダースコアの長さの差が高々1になるようにするとき、辞書順最小のものを求める問題。 考えたこと 辞書順最小と言えばgreed…

問題概要 整数列(長さN 考えたこと 前2つを覚えてDP？でも前2つのとりうる値の範囲が広すぎてアレだ。 実は特徴点が全部列挙できたりしないんだろうか。無理っぽいなあ。 最小値をどれにするか全探索して増加列と減少列に分離する？ 最小値はdecする必要が無…

問題概要 長さL( 考えたこと 問題文短くて良い…。 とりあえず辞書順と言えばgreedy。珍しく最小ではないけど考え方は変わらない。 とにかくでかいやつを選ぶ。で、後は探索範囲をそれより後方に狭めていく。 max_elementは確か最大値複数のときは一番前方の…