ツバサの備忘録

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

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: Fitness H: RGBtree I: M…

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

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

AGC032 D - Rotation Sort

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

AGC043 D - Merge Triplets

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

ARC082 F - Sandglass

問題 提出コード 解法 クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。 時刻のクエリに答えるには、となるようなの中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いで…

Typical DP Contest I - イウィ

問題 提出コード 解法 操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。 の区間の文字全てを消すことができるかどうか という区間DPを考えます。が3の倍数でない時はもちろんNOです。 を全て消去…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

問題 提出コード 解法 が回文になる条件は、a ~ zについて、に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。 a, b, ..., zとします。 先頭の文字から番目の文字までを見て、奇数個になる文字について、を計算したもの…

ARC099 E - Independence

問題 提出コード 解法 頂点との間に辺が張られていない場合、これらを同じ州に含めることができません。 これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフ…

AGC029 D - Grid game

問題 提出コード 解法 高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。 よって、高橋君が動けなくなるように青木君がうまく動けば…

AGC029 C - Lexicographic constraints

問題 提出コード 解法 種類以下で問題の条件を満たすような文字列たちを作成できるか?という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるについて問題の条件を満たすかどうか、を見ながら二分…

Typical DP Contest G - 辞書順

問題 提出コード 解法 まず、 文字目の次にという文字が現れるインデックスの最小値 を計算します。 これは、という更新を行えばよいです。 さて、 文字目を先頭で使った際にできる、部分文字列の種類数 というDPを考えます。 文字目を使った際に考えられる…

AGC009 C - Division into Two

問題 提出コード 解法 集合を、集合0、集合1とし、をとします。 番目の要素まで見て、番目の要素を集合に入れるような振り分け方のパターン数 を数えます。 という区間が集合に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このよう…

オイラーツアー、HLD解いた問題まとめ

提出場所見失いそうなので個人用まとめです もう少し解法の中身っぽいところを後で加えたいです(加えてください) HLD オイラーツアー 頂点 辺 HLD Submission #12187038 - 2010年 日本情報オリンピック春合宿OJ Aizu Online Judge Submission #12180953 - At…

Waseda Orientation Programming Contest 2020 J - トレジャーハンター

問題概要 解法 Med Large 1つめ:01ナップサックに帰着 2つめ:個数制限なしナップサック 3つめ:ダイクストラ法 おまけ(Med解以外の想定TLE,MLE解法) コード 問題概要 種類のはしごがあり、番目のはしごの長さはです。 以上以下の値で、以下の条件を満たさない…

AOJ 2335 - 10歳の動的計画

問題 提出コード 解法 縦方向が、横方向がとします(多分問題と逆…?) 移動は必ず全体で回になります。 縦に回、横に回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのが回、横方向が回になるので、先にその方向を決め打つと、 通りになります。…