AOJ
与えられた整数を平衡三進法展開してくださいという問題！ 問題へのリンク 問題概要 正の整数 が与えられる。たとえば のとき というように、 からいくつか選んで足し引きして表すことができる。これを平衡三進法展開と呼ぶ。 を平衡三進法展開せよ。出力フ…
sky さんの提唱した、代々伝わる名問題！！！ 問題へのリンク 問題概要 人の選手が箱根駅伝を走っている。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示される。 ある中継所を 番目に通過したそれぞれの選手について、前…
こどふぉでまったく同じ問題が出た！！！ 始点の入力の仕方が異なるのみ (こっちでは始点はノード 1 に固定、こどふぉでは始点 s を入力で与える) drken1215.hatenablog.com #include <iostream> #include <vector> #include <queue> using namespace std; int N, M, S = 0; vector<long long> w;</long></queue></vector></iostream>…
こういうの好き。操作によって実現できるかどうかを問う問題は全体的に好き 問題へのリンク 問題概要 文字列 "ABC" に対して以下の操作を好きな回数だけ行うことで、所望の文字列 S に変形できるかどうかを判定せよ。 A, B, C のいずれかの文字を選び、文字…
二乗の木 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 ########## ....#..... ....#..... .......... は下のよ…
