2019-01-01から1年間の記事一覧
最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…
操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…
復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…
こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…
ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…
これと似てる！！！ これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […
こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…
bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…
超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…
何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…
混ぜてソートは賢すぎる！！！惚れた！！！ 問題へのリンク 問題概要 枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。 カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ …
条件反射でいもす法をしたけれど、もっと楽にできた 問題へのリンク そして手前味噌ながら類題 atcoder.jp 問題概要 個の区間 があたえられる。 を満たしている。 この区間が 重に交わっている部分の長さを求めよ。 制約 解法 1：区間の交差 区間 と の交差…
重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…
まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…
これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …
頑張った 問題概要 個の文字列が与えられて そのうちの指定された 個についてについては、その prefix となっている 指定されていない 個については prefix にはなっていない ような最短の文字列を求めよ。存在しない場合は -1 とせよ。 制約 個の文字列の長…
区間分割系問題 問題へのリンク 問題概要 文字列が与えられる。文字列を最小個数の連続区間に分割して、各区間の先頭文字がその区間内の他の任意の文字よりも辞書順で小さくなるようにせよ。 考えたこと Greedy に区間を分割していけば OK。 区間を分割して…
最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…
楽しかったので。 問題概要 1 から 13 までの数字が書かれたカードが 1 枚ずつある。これをよくシャッフルして山札として並べて、1 枚ずつ引く。 このとき、引いたカードが「手札カードの数値の最大値」よりも小さかったらそのカードを捨て、そうでなかった…
この問題が解けた勝因は、「実験しよう」と思えたことな気がする。 問題へのリンク 問題概要 高橋君は，ある特殊な装置をたくさん持っています． この装置は筒状で，左右からボールを入れることができます． また，この装置には 2 種類の状態 A, B がありま…
面白かった 問題へのリンク 問題概要 個の長方形がある。各辺の長さは整数値である。 この長方形から何個か選んでマトリョーシカを作りたい。最大で何重にできるか？ 長方形の縦と横をひっくり返してもよい。 制約 考えたこと もし長方形が縦横ひっくり返す…
これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…
「探索候補は実はそう多くない」という教育的問題！！！ 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…
面白かった 問題へのリンク 問題概要 個ある食べ物から最強の食べ物を決めたい。各食べ物は AP (攻撃力)： HP (体力)： からなる。食べ物 は を満たすとき、 は より強いという。これらの値が等しい場合は引き分けである。 種類の食べ物のうち最強のもの (他…
発想一発ゲー！！！楽しい 問題へのリンク 問題概要 個の以下の問題に答えてください。 整数 を割った余りと整数 を割った余りが等しくなるような正整数のうち最大のものを求めよ 制約 考えたこと だったら、任意の整数が条件を満たすので、-1。それはそう …
大変だった ^^; 問題へのリンク 問題概要 全部で 色の色がある。 下図のような 枚の正方形があって、それぞれ のラベルがついていて、各正方形の四隅にはいずれかの色が塗られている。 枚の中から 6 枚を選んで立方体を作る。ただしどの頂点についても、そこ…
ちょっとした構築系問題という感じかな... 問題へのリンク 問題概要 二次元平面上の二点 が与えられる。 はすべて整数である。 今、 から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら に行き、またそこから出発して に戻り、さらに…
すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …
600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…
