AOJ
二乗の木 DP の例題として、すごくいい感じ！！！ 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…
今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com
楽しい！！！好き！！！ 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…
完全グラフはどのように向きづけしてもハミルトンパスが存在するというね！！！ その証明はすごく楽しいと思う！！！ 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …
グラフに行列は付き物！！！ 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…
ライツアウト系のいい感じの問題。そして bitset を用いたビットベクター高速化による高速化が求められる。 問題へのリンク 問題概要 × のグリッドがあって、各マスは白か黒に塗られている。今、何個かのマスを選んで 選んだマスから四方八方に伸ばして届く…
ライツアウト系の典型題 問題へのリンク 問題概要 × のグリッドと正の整数 が与えられる。各マスは 0 か 1 の値が振られている。今、以下の操作を好きな回数だけ行うことで、すべてのマスの値を 1 にしたい。それが可能かどうか判定せよ。 マスを 1 つ選んで…
連立方程式の練習。多項式補間でも解ける。誤差がきつい。 問題へのリンク 問題概要 次多項式 がある (係数はわからない)。 個の点 の値がわかっている...はずだったが、そのうちの 1 個については間違った値が出力された状態で入力が与えられる。どれが間違…
ランダムウォークな問題！ 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…
ロリハそのものな問題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…
この問題の原案やってました！高校の頃、時刻表同好会の友達から 「f(n) = n15 を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない？」 というメールを受け取って、あれこれ考えたことがキッカケにな…
ロリハの練習！！！ 問題へのリンク 問題概要 長さ の文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ: S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の 文字が と一致す…
B 問題が結構大変なのに比べて C 問題は毎度穏やかな感じ 問題へのリンク 問題概要 整数 が与えられる。これを使ってゲームをする。 の真の約数の中から整数を 1 つ宣言する、ただしこのとき既に宣言したことのある整数の約数になるものは宣言できない 宣言…
こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい！！！！！！ ということで教育的な楽しい問題！！！ 問題へのリンク 問題概要 整合するカッコ列 があって、 から以下のように定義される長さ の順列 が与えれる: i …
有理数ライブラリ整備とか大げさなことせずに全探索頑張るのが本筋であろうが、ここでは有理数ライブラリの足し算の verify としてやってみた。 問題へのリンク 問題概要 有理数 p/q を n 個以下の 1/r な形の有理数の和として 分母 r の積が a 以下となるよ…
有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた！！！ あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…
燃やして埋めます。後日ちゃんと詳しくまとめて解説書こうと思う。取り急ぎ。。。 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列は 'L' と 'R' で構成されている。文字列の "恐怖度" を以下のように定義する。 個の index ペア ui, vi (ui < …
与えられた操作を「わかりやすいものに読み替える」というのが本質な問題だと思う。AtCoder でもよく見られるタイプの 問題へのリンク 問題概要 の書かれた 枚のカードを順に並べたものに対し 左から偶数番目のみを順に取り出して並べたものを A 右から偶数…
こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい！ olphe たん、ナンさんとチームを組んでいて、olphe たんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…
本当に悔しい。BFGS に無限にこだわってしまった。なぜ方針転換を図れなかったのか。。。 そしてこの問題、本当に本当に整数論の魅力がたっぷり詰まった楽しい問題だった。作問してくれた会津大チームにすごく感謝！！！！！！！！！！ 問題へのリンク 問題…
面白かった 問題へのリンク 問題概要 Nim の「石が 個しかとれないバージョン」を考える。 ただし勝敗の決まり方が、「先に石を取れなくなった方が負け」ではなく「先にいずれかの山の石の個数を 0 にした方が負け」である。 制約 考えたこと 一瞬逆形かと思…
離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…
計算量的な詰めが甘かった。二分探索要らなかった。 問題へのリンク 問題概要 凸な 角形が与えられる。この 角形を完全に含むような正三角形の一辺の長さの最小値を求めよ。 制約 考えたこと 座標系として くらいの大きさまであるので、EPS は くらいがいい…
一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。 問題へのリンク 問題概要 "31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。 今、 137 456 …
難しかった 問題へのリンク 問題概要 ちょうど 本の牛乳の空き瓶を持っていくと新たに 本の牛乳の入った瓶と交換できる。 最初に 本の牛乳の入った瓶を持っているとき、最大で何本分の牛乳を飲めるかを 1000000007 で割ったあまりを求めよ。 制約 < 考えたこ…
燃やす埋めるを本気で整理する！！！ すごく面白い問題だった！！！ 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... .......... は下のよ…
めちゃ面白い！ 問題へのリンク 問題概要 オセロにおいて、黒石が 1 個だけない状態からスタートする。 ........ ........ ........ ...ox... ....o... ........ ........ ........ ここから通常のオセロルールでプレイする。今、 個のクエリが投げられ、各…
発想はすごくシンプルで、実装頑張る 問題へのリンク 問題概要 整数 が与えられる。 ラウンドのインタラクティブゲームを行う。 まずあなたは 頂点の無向単純グラフを 1 つ作成して出力する。 相手はそのグラフを受け取り、各ラウンドのはじめに、いずれか 1…
燃やす埋めるは今度こそちゃんとマスターする！！！ 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…
最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…
