解けてよかった。 問題: B - Tree Burning 考察 まず，高橋君はどういう動きをすべきかを考えよう。直感的に，を中心として，左右に振れるような動きをしたくなる。つまり 最初は本分右に進んで，それ以降は左→右→...と進む。(1) 最初は本分左に進んで，それ…

Pythonで解いた記念。 問題 レベルバーガーを以下のように定義する。 のとき，パティ1枚。 のとき，パン1枚，レベルバーガー，パティ1枚，レベルバーガー，パン1枚 を下から重ねたもの。 レベルバーガーの下から枚目までに，パティは何枚あるか。 考察 レベ…

オープン位だったので記念に投稿。本選の人と合わせると位かな？ (:億点が出たので追記しました) 問題 A - モンスターテイマー モンスターの高橋君(?)を育てながら，野良モンスターを討伐し，所持金を増やすという問題。初期状態の高橋君 正の得点を得る こ…

終了46秒前に通ってアツかった。 問題 C - k-DMC 解法 dpがちらついたが，順番に並んでいる3つ組を数えるときは，中央を固定するのが定石なので，とりあえずそれに従って考えてみる。ここで，もしという条件がなければ，これは単にに現れる「DMCという部分列…

はじめてのマラソン参加記。 結果は60位と，なんとも言えない成績だが，2桁順位とれるかどうかが実力相応かなと思っていたので，善戦したと思う。上位の方々も何人か記事を上げているので，これがどの程度参考になるものとなるかわからないが，記念に残して…

フィボナッチ数列が登場しがち。 問題 D - Number of Amidakuji 解法 こういうのはdpが有効である。を位置まででに行くようなあみだくじの数とおく。の遷移先はのいずれかである。あとはそれぞれの遷移先について，そこに遷移するような位置での横線の置き方…

最近よく見るやつ。 問題概要 長さの数列が与えられる。その数列の連続する部分列であって，総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき，あり得るたぴさの最小値を求めよ。 E - Treeone 解法 「数列の連続する…

きれいに解けるので好き。 問題 D - Novelist 考察過程 王都から都市へ移動する依頼をタイプM，都市から王都へ移動する依頼をタイプLとする。 最初は各依頼を頂点として，ある依頼を終えた後，実行可能な依頼について有向辺を張って，最長パスを調べるという…

慣れているとなんてことない問題だが，ちゃんと書いてみる。 問題:C - Ito Campus 解説 @から距離以内のマスは安全でないなので，そのようなマスを調べて安全でないマークをつけてから，安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを…

数え上げ力の不足。 問題概要 1からまでの番号がついたブロックが横にならんでおり，ブロックには重さがある。ここから回ブロックを取り除くのだが，ブロックを取り除くコストはブロックと連結な(自身も含む)ブロックの重みの総和である。取り除く順番は通り…

初AGC2完記念(今更？)＆初900AC記念＆初黄パフォ記念。 問題概要 頂点辺のグラフがある(単純とも連結とも限らない)。各頂点にはAまたはBと書かれている。好きな頂点を始点とし，好きな回数隣接する頂点の移動をしたときに，訪れた頂点に書いてある文字を訪問…

勉強になったのと，解説があまり丁寧でないのでまとめのため。 問題概要:からまでの目が出るサイコロを個振る。このとき，をみたす各について，次の問題に答えよ。・どの異なる2つの出目の和もにならないような出目の組の場合の数はいくつか？ただし，サイコ…

背景が面白い問題だったのでつい投稿。嘘を書いていたら教えてください。 問題要約 長さのpermutationのうち，最長増加部分列(LIS)の長さと最長減少部分列(LDS)の長さの和が最小になるものを1つ出力せよ。 https://codeforces.com/contest/1017/problem/C本…