皆さんこんにちは、おきもちです。2019年7月12日(金)に行われたICPC2019国内予選の参加記です。やや長いです。 結果 チームokimochiは全体4位で、無事アジア地区予選横浜大会に出場できることになった。やったね！5完内1位でした、全体的に早かった メンバー…
オイラーツアーとかはともかく、この解法が思いつけないのは悔しい...。 問題 F - Colorful Tree 解法 まず、色の変更のことは忘れて、「木上の点間の距離を求めよ。」というクエリに効率的に答えることについて確認する。このクエリに答えるには、の最小共…
クラスカル法あたりの考え方をちゃんとわかっているかを問われている気がしてよかった。 問題 G - MSTX 考察・解法 最小全域木だしクラスカル法っぽく考えたい。まずのとき、つまりの辺から優先的に使うことを考えてみる。このとき、もしの辺を使うことがあ…
やっぱりAGCの問題は綺麗で良いなあ...。 問題 D - Rotation Sort 解法 Rotation操作はややこしいので、言い換えを考える。よく眺めると、右シフトは「好きな数を今の位置より右側の好きな位置に移す」と言い換えられる。左シフトも同様なので、結局 「コス…
参加資格ありのチーム内で5位！チームとしての上限に近いパフォーマンスだったと思う。 Aをまず通す。その間にBは01bfsやるだけですと言われたので受け取り、難なく通す。少しバグらせたのでここまで15分くらいかかってしまったが、そこそこ早かったようだ。…
3時間2セット。 RUPC2017Day3 こるとんがAを通す。僕がBをやろうとするがうーんとなり、DがいつものDijkstraらしいのでBをこるとんに渡してDを受け取る。risujirohがCを通したあとDを僕が書く。問題を誤読していて(え…)焦るがまあ通る。その後Eが遅延セグ木…
こういう問題を解いていると競プロ楽しいなと思う(やはりパズルが好きなのでは？)。 問題 D - Go Home 解法 すべてのマンションが地点から見て同じ方向にあるときは自明なので、そうでない場合を考える。 初期状態から考えるとつらい気持ちになるので、終了…
方針立ってから時間かけ過ぎた...。 問題 D - Squirrel Merchant 解法 まず1つの金属について考える。例えばなら、Aでどんぐりを金にして、Bで金をどんぐりにするという行為以外ありえない。このように不等号の向きを見れば、ある程度取るべき行動が確定する…
う 問題 G - Chicks and Cages 解法 dpっぽい雰囲気はあるが、何の整理もなしにはうまくいかない。まず、ある鳥かごに振り分けられたひよこの集合をとする。この鳥かごで発生するストレスの値はである。つまりストレスの値の総和は、ひよこの大きさに、その…
コンテスト中に解き切りたかったけど、細かいところも少し要求されるので厳しかったかな...。 問題 F - Frog Jump 解法 蓮以外の点に行かないようにしないといけないので、まずという条件が得られる。この下で、を決めたときの動きを観察すると、以下のよう…
これが解けて紫になった。 問題 Problem - E - Codeforces 解法 をsortした列を考える。この列を眺めていると、区間を消去できることの必要条件は 上で述べた列について、の値が未満のところまでは昇順である」かつ「がより大きいところからは昇順である」 …
国内予選2017と2015をやった。 2017 こるとんがAを通す。僕がBを見て書こうとするが詰まり、その間にCをこるとんに通してもらう。その間にBの誤読に気づき(おい)、落ち着いて通す。申し訳なかったけど実はこれはそこそこ苦戦するチームもあったそうなのでセ…
5時間セットをheno_worldとやった。 セットはACM-ICPC 2016-2017 Asia region Daejeon(韓国セット) Aを読むがわからない。 B:こるとんが簡単とか言うのでやってもらう、なんか入力形式がめんどくさかったみたいで2ペナ踏んでたけど通る。 risujirohがCをやる…
めちゃくちゃ時間をかけてしまったけどこういうのが通せるようになったのは成長かな...。 問題 D - Modulo Operations 考察過程・解法 確率に落とすのは苦手なので総和のままやった。 まず最初に，という2つの集合の要素について，で余りをとった値に，で余…
こんにちは。2019/3/22(金) 21:20~23:20のyukicoder contest 209(yukicoder contest 209 - yukicoder) でwriterをさせていただきました。初めてのことで開始前は尋常じゃなく緊張しましたが，およそ160人の方に参加していただけました。ご参加ありがとうござ…
失敗したと思ったが(75位で，恐らくボーダーだが)予選通過したので，少し復習した。 A:ツーリストXの旅行計画 A - ツーリストXの旅行計画 コンテスト中にやったこと 山登り/焼きなましでよさそうだと思ったので，という順から初めて，2点をswapする山登り法…
きれいな問題だなあと思った。 問題 C - Division into Two 解法 簡単のためとする。逆のときはswapしても問題ない。こんなのdpしかないやろという見た目がするので，dpを考える。制約を無視すれば，今何番目の数を見てるかということと，またはに最後に振り…
これはわかればシンプルで楽に解けるので好き。 問題 H - Median Game 解法 このゲームでは，ある列の中央値がゲームのスコアになり，それを求めよと言われている(偶数のときは2つ候補があるが，大きいほうをとる)。中央値を求める問題では二分探索が有効で…
詰め切るのが大変。本番で通した人たちすごい。 問題 G - Sum of Cards 解法 カードについて，どちらか一方のスコアを獲得できるという状況だ。こういう状況は，グラフにしてみたくなる。からの数字が頂点，辺をの間に結んだグラフを考えよう。このグラフは…
本番は誤読をした...。 問題 F - Coins on the tree 解法 辞書順最小を作れという指示がある。辞書順最小ということは，前の数字が小さいことが正義である。ならば，先頭から「1にできるか？」を判定し，できるなら確定，できないなら「2にできるか？」とい…
良問だと思ったので記事にすることにした。Cさえなければ....。 問題 E - Weights on Vertices and Edges 解法 こういう重み付きの辺を追加/削除して連結成分が...という問題は，辺が一本もない状態から，一定の順番で辺を追加していくことを考えることで道…
解法自体は素直なので400点なのだろうが，見た目はとっつきにくいので難しいと思った。 問題 D - Various Sushi 考察・解法 食べることにする寿司の集合を，のネタの種類をと書くと，の最大値を求めることになる。解法はさまざまだが，ここではの和にまず注…
色が変わったら記事を書く人がそこそこいる競プロ界隈ですが，自分もその流れに便乗してみようと思います。ついでに，茶色からの話も少しだけしてみようかと思います。(本編は水色～青の話です。) 最初にこの記事の結論を言ってしまうと，「ちょっとレベルが…
解けてよかった。 問題: 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 解法 「数列の連続する…
