ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

精進メモ 2021/05/03~

最近は少しだけ忙しくて典型を埋めるので精いっぱいです(モンハンをしながら) 典型90 029 - Long Bricks(★5) 典型90 030 - K Factors(★5) 典型90 031 - VS AtCoder(★6) ABC200 D - Happy Birthday! 2 E - Patisserie ABC 2 F - Minflip Summation ARC1…

精進メモ 2021/04/26~

Reonaさんの新曲、良いですね。 典型90問 025 - Digit Product Equation(★7) ZONeエナジー プログラミングコンテスト “HELLO SPACE” C - MAD TEAM D - 宇宙人からのメッセージ E - 潜入 典型90問 025 - Digit Product Equation(★7) について考えると、こ…

精進メモ 2021/04/19~

競プロ典型 90 問 yukicoder contest 292 No.1487 ぺんぎんさんかっけー No.1488 Max Score of the Tree No.1489 Repeat Cumulative Sum No.1490 スライムと爆弾 ABC199 D - RGB Coloring 2 E - Permutation F - Graph Smoothing 競プロ典型 90 問 問題 day1…

精進メモ 2021/04/12~

先週もモンハンしていたら一週間が終わりました。 MY FIRST STORYをにハマりました、気に入った数曲をヘビロテしていますが良いですね。 形式的べき級数 ACL contest 1 E - Shuffle Window 第二回日本最強プログラマー学生選手権 C - Max GCD 2 D - Nowhere …

精進メモ 2021/04/5~

先週はモンハンしていたら一週間が終わりました。 ARC049 D - Convex Sequence ARC107 E - Mex Mat ゆきこ No.1471 Sort Queries No.1472 作為の和 No.1473 おでぶなおばけさん No.1474 かさまJ GCJ 2021 Round 1A Appen Sort Prime Time Hacked Exam AGC05…

精進メモ 2021/03/29~

解説ではないです。エスパーしたものもあります。 みんなのプロコン2019 E - Odd Subrectangles ARC116 E - Spread of Information 第6回 ドワンゴからの挑戦状 予選 D - Arrangement みんなのプロコン2019 E - Odd Subrectangles 問題 提出コード こういう…

精進メモ 2021/03/22~

更新は飽きたらやめます。クオリティも気分次第です。 Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) C. Skyline Photo ARC115 E - LEQ and NEQ ARC115 D ARC111 E - Simple Math 3 AGC052 B - Tree Edges XOR AGC050(Good Bye rng_…

ARC029 D - 高橋君と木のおもちゃ

問題 提出コード 解法 まず、整数を置く回数は、全体で回になります。 葉から見ていき、追い出したい数字が置いてある頂点に数字を置く、という操作を繰り返すことでこれは達成できます。 また、ある数字を追い出したいとき、今置いてある頂点より親にあるも…

競技プログラミングを始めて3年が経ちました

2/7にAtCoderで初ACをしたようなので、3年になりました。 この手の記事を書くのは初めてなのですが、自分の昔を振り返りたいときに残っているデータがほとんどなかったため、記録しておくことにしました。 データは2/6の19時時点のものです。 AtCoder AOJ-IC…

ARC 095 E - Symmetric Grid

問題 提出コード 解法 それぞれの行に含まれている文字の種類とその個数の状態関係について見てみると、 行をswapしても、列をswapしても、個数自体に変化はないことがわかります。 最終的に点対称になるので、先ほどの状態の一致不一致を使って、行と列それ…

AGC051 B - Bowling

問題 提出コード 解法 まず、という置き方を考えます。すると、下の図のように、対角線上に点が10個並びます。この時、A, C, Dは同じ個数だけ見えて、Bだけ1個しか見えません。よって、この置き方を1つのブロックとして大きな1個の点とみなすと、このブロッ…

AGC049 B - Flip Digits

問題 提出コード 解法 できる操作が、 1 をひとつ左に動かす 連続する1 を消す のどちらかとなっています。 また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。 そのため、…

AGC010 D - Decrementing

問題 提出コード 解法 わかりやすい部分、つまりが小さい方から考えていきます。 のとき 1回の操作で必ず1減少するので、明らかに、の偶奇で答えが判定できます。 奇数であれば後手勝ち、偶数であれば先手勝ちです。 のとき のどちらかが1であった場合、先ほ…

ICPC2020国内予選 参加記

とまとさん、るぎうさんとの三人で出る。正直、AtCoderで黄色三人のチームは弊学でここだけで、最近は自分の調子も良かったので何もなければ通っていると思っていた。 コンテスト前、大学に来て出ている他の5チーム(?)全部に挨拶してまわる。イケメンだったs…

ARC106 D - Powers (畳み込み解)

NTT

問題 提出コード 解法 まずは式を分解していきます。ループの中、つまりに注目すると、これは二項定理そのもので となり、さらにコンビネーションを分解すると、 となります。は最後にかければよいので、の部分が高速に計算できればよいです。 ここから、答…

ICPC2020模擬国内 参加記

とまとさん、るぎうさんと組んでの出場です。 準備 流れ 結果 終わり 準備 前日はライブラリの印刷をしました。去年はwordに貼り付けて適当に印刷していましたが、読みづらい(シンタックスハイライトが欲しい)上、量も増えてきたので以下のサイトを利用しま…

AGC037 D - Sorting a Grid

問題 提出コード 解法 当たり前ですが、ある数字を取ってくると、最終的にどの行、どの列にいるべきか、というのが決まっています。 そこから逆算すると、3回目の操作開始時点では、 全ての数について、いるべき行は正しい という条件が成り立っていればよい…

京都大学プログラミングコンテスト 2020 H - Beans on the Grid

問題 提出コード 解法 豆は自由に選んで操作できるので、定石通り、それぞれの豆に対してグランディ数を求め、最後にxorを取れば良いです。 まず、とりうるグランディ数の値を考えると、遷移先としてあり得るのが{右、左、下}の3パターンが最大です。よって…

ACPC2020 3日目

最終日!です 内容 A(0:05) B(0:07) C(0:11) E(0:37, 2ペナ) D(0:56, 2ペナ) F(1:27) G(2:49) 結果 おしまい 内容 通した順です。 A(0:05) なんで4方向じゃないのだろう…とぼやきながら頑張って実装しました。 幸いバグらせることはほぼなかったのでよかった…

ACPC2020 2日目

ICPCチームです。 内容 A(0:00) B(0:06) C(0:26) E(0:45) F(1:31) J(3:53) G 結果 おしまい 内容 また通した順です。 A(0:00) 2 * a + 3 * bを出力するタイピングコンテストです。 B(0:06) とまとさんが実装しました。問題内容は何もしらず… C(0:26) るぎう…

ACPC2020 1日目

全日程 Ramen as a Service で参加予定です。 内容 A(0:02) B(0:31) D(1:09) C(1:15, 3ペナ) G(1:58) E(2:36, 2ペナ) F 結果 おしまい 内容 通した順です。 A(0:02) どうせ割り算すると誤差死するんだろうなと思ったので、きちんと手元で立式しました。 普段…

HUPC2020Day3 G Katsusando

問題 提出コード 解法 まず、二人が出会う地点は必ずカツが置いてある座標になります。途中で挟むとしても、左右どちらかのカツで出会うように適切に調整することで損をすることはありません。 左から番目のカツまで食べ終えた状態のときに経過した時間の最…

HUPC2020 3日目

1日目はこちら、2日目はこちら 3日目は、とまとさんるぎうさんとのチームです。 例によって問題は解いた順です。 内容 A C I M B E G F 結果 反省 おしまい 内容 A ここはサクッと。全体3番目だったので良かったかと思います。 C るぎうさんがサクッと考察し…

HUPC2020 2日目

一日目はこちら yamadさん、とまとさんと yamad as a Serviceで出場しました。 yamadさんが助っ人サービスになる時代… 通した順に書いていきます。 内容 A B C G M J D I 結果 反省 おしまい 内容 A 3秒くらいオーバーフローどうするんだろう…って悩んでいま…

HUPC2020Day1 F: n 角錐グラフ

問題 提出コード 解法 頂点0と別の頂点を結ぶ辺の集合を中心の辺、とを結ぶ辺の集合を円周上の辺と呼ぶことにします。 回頂点0に戻る、と仮定したときの数え方が高速に求まれば、これを全部のについて試せばよいです。 このとき、頂点0を1回だけ通る閉路は個…

HUPC2020 1日目

僕、とまとさん、るぎうさんで組みました。 コンテスト開始直前に、チーム名が変わって Ramen as a Serviceになりました。 捨てられてしまったアカウント(ごめんなさい) ICPCのチームはこの三人で行く予定でしたが、チーム練習は初めてでした。果たして… 流…

WUPC4th を開催しました

2020/9/12に行われた、WUPC4thの運営側目線の感想です! コンテストサイト 運営陣について 問題セットについて A: Prime Number Sum 2 B: Canceling Sequence C: Flip Difference Sequence D: Treasure Mountains E: LCM Count F: Abyss and Coins G: Fitnes…

DDCC2020本戦 C - 特別講演「括弧列と塗り分け」

問題 提出コード 解法 という区間の塗り分け方、みたいなものを考えたいですが、上手いこと工夫しなければ計算量が大きくなってしまいそうです。 ここで、括弧列が木に対応することを思い出すと、二乗の木DPができそうになってきます。 番目の文字(開き括弧)…

AGC032 D - Rotation Sort

問題 提出コード 解法 シフトという操作が少しわかりづらいのですが、結局は 任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストは、右であれば) という操作ができることになります。 ので、それぞれの要素を、 右側に移動し…

AGC043 D - Merge Triplets

問題 提出コード 解法 いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。 この原因を考えてみると、長さ3の数列を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要…