hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

CODE FESTIVAL 2018 参加記

CODE FESTIVAL 2018 に参加しました。予選は 2 年前から参加していましたが、3 度目の正直で今回やっと初めて本戦に参加できました。感想をいろいろつづります。 予選 予選 A で解けるタイプの DP が運良く出たので、通過しました。予選 B が結果的に早解き…

競技プログラミングで黄色になるまでにやったこと

先月末に、めでたく AtCoder 黄色になりました。 1976 -> 2025 (+49)念願の!!!! 黄色!!!! です✌️✌️✌️✌️✌️✌️✌️ pic.twitter.com/6S5whNlq8G— tsutaj (@_TTJR_) 2018年9月29日 きのう、ふと「黄色になりました記事書いてないなぁ」と思って雑に呟いた…

ACPC 2018 参加記

会津大学プログラミング合宿 2018 に参加しました。ACPC は実は初参加です。 0 日目 JAG に行っていたので東京にいた。TIke さんと seica さんと ferin さんと olphe さんでボドゲカフェに行ってあそんだ。ワイナリーはワイン農家をやめた者が勝つゲームだっ…

JAG 夏合宿 2018 参加記

初めて JAG 夏合宿に参加しました。同じ大学からは four-t のチームメイト (rsk0315 君と TAB 君) と waku 君も参加しました。以下、雑に記します。 0 日目 札幌から東京まで移動した。なんか自分が離陸した後に新千歳行きの電車が止まったらしく、わりとあ…

ICPC 国内予選 2018 参加記

昨日、ACM-ICPC 国際大学対抗プログラミングコンテストの国内予選 が行われました。自分が所属する北海道大学からは 4 チームが参加し、3 チームが 4 完・1 チームが 3 完しました。このうち 2 チームはアジア地区に行けそうで、弊学サークル全体のレベルの…

競技プログラミングで青になるまでにやったこと

リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。 自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒…

Google Code Jam 2018 Round1B: Rounding Error

問題概要 原文 → Google Code Jam 長さ の数列 (この数列の 番目の要素を とする) と、整数 が与えられる。 は より大きく、数列の要素の総和は 未満である。 新たな数列 を作ることを考える (この数列の長さを とし、 番目の要素を とする)。 は長さが 以上…

RUPC 2018 参加記

#RUPC2018 pic.twitter.com/cTQUtSQFcV— tsutaj (@_TTJR_) 2018年3月26日 立命館大学競技プログラミング合宿 2018 (通称 RUPC 2018) に参加しました。去年に引き続き 2 回目の参加です。いやあ濃密な三日間だったなあ・・・ 以下時系列順に振り返るいつもの …

AtCoder Regular Contest 089 D: Checker

問題概要 日本語なので原文参照 → D - Checker 解説 公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。 考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。こ…

CSAcademy Round #72: Spring Cleaning

問題概要 原文 → CS Academy 頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。 はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除…

CSAcademy Round #72: Beautiful Matrix

問題概要 原文 → CS Academy の行列 から、 の行列 を作る。 (作り方は原文参照) を作る前に、 について行どうし、または列どうしのスワップを合計 回まで行える (何もしなくても良い) とき、 の最大値を求めよ。 解説 ある要素が、 の要素のうちいくつに関…

TopCoder SRM 715 Div1 Med: ClassicTowers

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ハノイの塔をアレンジしたゲームを考える。 つの棒に、左から 個、 個、 個のディスクが刺さっている (ハノイの塔と同じように、大きさは相異なる)。これらのデ…

TopCoder SRM 715 Div1 Easy: MaximumRange

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので) この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取っ…

TopCoder SRM 716 Div1 Easy: ConstructLCS

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。 と の最長共通部分列 (LCS) が と の LCS が と の LCS が 解説 を仮定すると、次の…

TopCoder SRM 716 Div1 Med (Div2 Hard): JumpDistancesOnTree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距…

TopCoder SRM 717 Div 2 Hard (Div1 Med): DerangementsStrikeBack

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。 解説 Div2 では制約が小さいため、以下のように解くことができます。 「先頭 …

TopCoder SRM 718 Div2 Hard: ChainCity

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。 点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新…

TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 括弧列 と が与えられる。 に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?…

蟻本練習問題解説 Part3 (2-3)

蟻本練習問題の解説をします。今回のトピックは動的計画法です! 今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問…

TopCoder SRM 719 Div1 Easy (Div2 Med): LongMansion

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。 から まで移動するとき、コスト和の最小値を求めよ。 解説 横方向に移動す…

TopCoder SRM 719 Div2 Hard:TwoDogsOnATree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。 与えられた木から、辺の重…

TopCoder SRM 720 Div1 Easy: SumProduct

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement digit1 桁の数 と、digit2 桁の数 を、以下の条件のもとで作ることを考える。 leading zero を許す の各桁において、登場する の個数の合計は最大で 個 このよう…

TopCoder SRM 720 Div2 Hard: RainbowGraph

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる無向グラフがある。頂点にはそれぞれ色 が付いている。 同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) …

TopCoder SRM 721 Div1 Easy (Div2 Med): RememberWords

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement が与えられるので、以下の条件を満たす数列が構成できるか判定せよ。 数列の長さが であり、各項は非負整数で、隣り合う項との差の絶対値は または 第 項から第 …

TopCoder SRM 721 Div1 Hard (Div2 Hard): Apocalypse

するめうめ tsutaj.hatenablog.com 問題概要 頂点からなる木がある。 このうち 個の相異なる頂点に、ルークと爆弾が つずつ置かれている。ルークは ステップで隣接した頂点に移動させることができる。 ステップを終えた後に爆弾と同じ頂点にいるルークは、爆…

TopCoder SRM 722 Div2 Hard: MulticoreProcessingEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement CPU が 個あり、 番目の CPU は ミリ秒につき仕事量 を消化でき、コア数は である。 いま、仕事量 のタスクがある。 個ある CPU のうちどれか つだけ選び、この…

TopCoder SRM 722 Div1 Easy: TCPhoneHome

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement leading zero を許して 桁の数字を作ることを考える。 文字列がいくつか与えられる。作る数字の prefix は、この文字列のいずれとも一致してはならない。 この状…

TopCoder SRM 723 Div1 Easy: TopXorer

するめうめ tsutaj.hatenablog.com 問題概要 個の非負整数列 がある。 から までの範囲で非負整数 を、 から までの範囲で非負整数 を、・・・以下同様に合計 個の非負整数を決め、それらの XOR をとるとき、 XOR 値の最大値を求めよ。 解説 XOR を最大化し…

TopCoder SRM 723 Div2 Hard: SimpleMazeEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement の部屋が十字型に並んでいる。 (詳細は原文をご覧ください) すべての部屋と部屋の間の最短距離の総和を求めよ。 解説 ※ちゃんとした解説は kmjp さんのブログ に…

TopCoder SRM 724 Div1 Easy: OrAndSum

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ともに長さが の数列 , が与えられる。以下の条件を満たす長さ の数列 が構成できるかを判定せよ。 解説 まず、任意の非負整数 に対して、 が成立します (これは…