hogecoder

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

TopCoder SRM 726 Div2 Hard: HeroicScheduled2

するめうめ tsutaj.hatenablog.com 問題 原文 → TopCoder Statistics - Problem Statement 個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。 個の仕事の部分集合であって、適切にこなすこ…

TopCoder SRM 727 Div1 Easy: OnlySanta

するめうめ tsutaj.hatenablog.com 問題概要 文字列 が与えられる。 にいくつか文字を挿入して、"SANTA" を部分列として含み、かつ "SATAN" を部分列として含まないような文字列を構成せよ。 解説 方針は同じ回の Div2 Hard (hogecoder での解説) と全く同じ…

TopCoder SRM 727 Div2 Hard: ManageSubsequences

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 文字列 が与えられる。 に対して、部分列として を含むが は含まないように、いくつか文字を挿入したい。この条件を満たす文字挿入個数の最小値を求めよ。不可能…

TopCoder SRM 728 Div1 Easy: Halving

するめうめ tsutaj.hatenablog.com 問題概要 自然数が 個与えられる。各数字 に対して、次の操作を何度でも行える。 が偶数のとき、その数字を に変える。 が奇数のとき、その数字を か のどちらかに変える。 操作を何回か行い、 個全てが同じ数字になるよう…

TopCoder SRM 728 Div2 Hard: TrisomorphismEasy

するめうめ 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点の有向グラフがあり、各頂点はそれぞれ から までの番号でラベル付けされている。 ある つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリン…

TopCoder SRM 729 Div2 Hard: RareItems

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 個のアイテムが出るくじがある。 番目のアイテムが出る頻度は である (すなわち、 番目が出る確率は )。 個すべてのアイテムを出すまでに必要な、くじを引く回数…

TopCoder SRM 729 Div1 Easy: MagicNumberThree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 数字のみからなる、 文字の文字列が与えられる。この文字列の (連続とは限らない) 部分列であって、それを数字に直したときに の倍数になるものの総数を、 で割…

TopCoder SRM 730 Div1 Easy (Div2 Hard): StonesOnATree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点に重み がついている、 頂点からなる木がある。子よりも親の方がインデックスが小さく、重みについても子と同じか小さいことが保証される。 この木に石を置…

AOJ 2320: Infinity Maze

AOJ

Infinity Maze、自分の解法と違う方法でやってるひとが割と多くてビックリ— つたじろう (tsutaj) (@_TTJR_) February 8, 2018 なんか自分の解法と違うやり方でやってる人がわりといたため記事にします。 問題概要 問題原文 → Infinity Maze | Aizu Online Ju…

分割数 DP について

昨日の 第4回ドワンゴからの挑戦状 予選 C 問題 で、分割数 DP を必要とする問題が出されました。 蟻本をよく読んでいる人ならご存知のとおり、この DP は dp[i][j] := j を i 分割する時の場合の数 とするとき、 dp[i][j] = dp[i][j-i] + dp[i-1][j] となり…

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

蟻本練習問題の解説をします。今回のトピックは貪欲法です! シリーズ目次はこちらからどうぞ。 tsutaj.hatenablog.com 猪突猛進! "貪欲法" 区間 POJ 2376: Cleaning Shifts 問題リンク 区間が 個あり、 番目の区間は の閉区間である。これらの区間の中から…

蟻本練習問題解説 Part1 (2-1)

この記事は 解説 Advent Calendar 2017 の 23 日目の記事として書かれました。 みなさんは、蟻本の「練習問題」を解いたことはありますか?本の中で掲載されている例題は見たことがあっても、練習問題までは手を出していない、という人はそれなりにいるので…

ACM-ICPC 2017 Asia Tsukuba Regional Contest 反省記 (コンテスト部分のみ)

参加記は後日書こうと思っていたのですが、記憶が鮮明なうちにコンテストの反省をしたほうが良いだろうなあと思ったので、コンテスト部分だけ別記事で先に書くことにしました。 ※割と真面目に分析したり反省したりしているので、おもしろ要素はありません。…

動的計画法における空間計算量削減テク

この記事は 「競プロ!!」競技プログラミング Advent Calendar 2017 の 日目の記事として書かれました。 競技プログラミングをそれなりにやってきた方となれば、動的計画法に触れたことも多いでしょう。今回は、その動的計画法における空間計算量削減テクを色…

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 に参加しました。今回が初参加です。 予選 予選の順位は 予選 順位 qual A 308th qual B 454th qual C 757th 予選 A は C 問題までそこそこ早解きできたけど、予選 B と C は D 問題が解けそうで解けなくて結構下の順位になってし…

DDCC2017 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 に参加しました。去年の DDCC に引き続き、 2 回目の参加となります。 予選 予選は全完 122 位でした。D 問題が解けたのは嬉しかったのですが、結構条件漏れが多くてサブミットデバッグ…

CS Academy: Sorting Steps

公式の解説が鮮やかだったけど、英語がちょっと読みにくかったので日本語解説を作ってみたくなりました。 問題概要 原文 → CS Academy 長さ の配列をバブルソートすることを考える (どんな実装かは、原文にサンプルコードがあるのでそちらを参照してください…

天下一プログラマーコンテスト 2016 予選 A C: 山田山本問題

hogehoge アルゴリズムのライブラリを貼るだけで解けるんじゃなくて、それにひと工夫加えないと解けない問題すき— tsutaj@進捗 6/35 (@_TTJR_) September 29, 2017 この手の問題すき。すきだから記事を書いてしまう。 問題概要 原文を参照してください → C: …

天下一プログラマーコンテスト 2016 C: たんごたくさん

初めて Trie 木を使ったので、ハマったところとかを記事でまとめておきます (完全に自分用) 問題概要 原文参照 → C: たんごたくさん - 天下一プログラマーコンテスト2016本戦(オープンコンテスト) | AtCoder 解説 与えられる単語すべてを検索対象として、T…

AtCoder Regular Contest 079 D: Decrease (Contestant ver.)

どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。 問題概要 日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder 解説 まず、出力する数列の長さは に固定してしまいます。この…

ICPC 国内予選 2017 参加記

今日を終わらせたくないので、この勢いのまま参加記を書いてしまいます。 チーム情報 今年は構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と就寝のプロ・自分 (tsutaj) の 3 人で、チーム four-t で出場しました。チー…

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

本番出てた回。ようやく復習できました。 問題概要 原文 → Problem - C - Codeforces 長さ の数列があり、 番目の要素を と書く。 次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合…

AtCoder Beginner Contest 020 D: LCM Rush

もう 7 月かあ・・・。 問題概要 を求めよ。ただし は と の最小公倍数を指す。 制約: 解説 愚直にやるのは無理なので、数学をします。 まず、 なる関係があります。これを使って与式を変形すると が求めたいものになります。 ここで、 の取りうる値の数は …

Snackdown 2017 Pre-elimination A: Consecutive Snakes

これは良問だなあと思った。 問題概要 原文 → Contest Page | CodeChef 長さ の蛇が数直線上に 匹おり、 番目の蛇の左端の座標は である。つまり、 番目の蛇は区間 にいる。 いま、この蛇たちを以下の条件が成り立つように移動させたい。 N 匹の蛇すべてにつ…

競プロをやりはじめてから一年が経ちました

競プロをやりはじめて、今日でちょうど一年です。半年記事 に引き続き、ポエム的なものを書いていきます。

AtCoder Regular Contest 038 B: マス目と駒

ちょっと迷ってしまったので。 問題概要 原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder 解説 rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか? となるような配列を作ります。 あるマス について、この値は以…

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。 問題概要 街が つあり、街 と を結ぶ道路の長さは (km) ( ただし の時は道路がないことを表す) である。 それぞれの街には馬がおり、街 にいる馬は時速 (km/h) で移動することができ、最大で (km) 移動できる。街…

TopCoder SRM 712 Div1 Easy: LR

オーバーフローで死ぬつらい問題。 問題概要 原文 → TopCoder Statistics - Problem Statement 環状になっているサイズ の数列 がある (0-indexed)。 番目の要素に対して左隣は要素 であり、右隣は要素 である。 (ただし、 番目の要素の右隣は要素 である。)…

遅延評価セグメント木をソラで書きたいあなたに

最下段が N-1 から始まるのと、親と子の取得方法がわかってればセグ木は書けます (ホンマか?)— tsutaj (ARC-C 93/96) (@_TTJR_) 2017年3月29日 この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳し…

セグメント木をソラで書きたいあなたに

セグ木がソラで書けなかったらセグ木に何か生やす問題とか解けない— つたじろう@帰省 (@_TTJR_) March 29, 2017 セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと…