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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

この記事は立命合宿の 3 日目に行われた北大セットのまとめ的記事です。勝手にまとめてしまいました。 ※ 随時更新します 問題 実際にコンテストで使われたバージョン A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題 正式掲載 A 問題 | B 問…

立命館大学プログラミング合宿2017 に参加してきました。競技プログラミングの合宿に参加したのは初めてです。 帰りの電車ヒマなので参加記をつらつらと書いていこうと思います。 -1 日目 (作問班参加・準備編) 北大では立命合宿で作問を担当しているので、…

昨年のだるま落とし、ちらっと解説読みながらだけど AC できた。ちょっと嬉しい。— つたじろう (ABC-D 29/43) (@_TTJR_) March 6, 2017 昨年歯が立たなかっただけに解けてうれしい。 問題概要 原文を参照してください → Daruma Otoshi | Aizu Online Judge …

何でこれが詰まっちゃうかな・・・。 問題概要 原文 → D: 権力 - 京都大学プログラミングコンテスト2012 | AtCoder 個の区間がある。 を被覆するには、区間はいくつ必要であるか、その最小値を答えよ。 解説 まず、地点 を被覆する区間があるかを調べます。…

バレンタインデー、みなさんいかがお過ごしでしょうか。私はいつもと変わらず競プロをやっています。というわけで今回は ABC018 D 問題です。 問題概要 原文 → D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder 女子が 人、男子が 人いる中か…

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。 問題概要 問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder 長さ の数列が与えられる。この数列から、( 番目に取った数 ) ( 番目に取…

AGC010 の B 問題。本番解けなかったけどこれは良問だとおもう。 問題概要 原文 → B: Boxes - AtCoder Grand Contest 010 | AtCoder 個の箱が環状に並んでおり、 番目の箱に入っている石の数は 個である。 この環状に並ぶ箱に対して、ある箱を選んでそれを …

またまた DP 自力で解けた記念。 問題概要 原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder 種類のトッピングがある。トッピング は 枚のチケットを交換することで入手でき、その価値は である。 チケットにはスペシャルチケ…

正答率低いのはバグりやすいせいかな。発想自体はそんなに難しくない。 問題概要 原文 → TopCoder Statistics - Problem Statement の盤面があり、. は通行可能な座標、# は通行不可能な座標を表す。座標の移動は上下左右の方向のみ許されている。左上の座標…

個数制限付きナップザック問題です。 問題概要 原文 → Knapsack Problem with Limitations | Aizu Online Judge 価値 で重さ であるような 種類の品物と、容量が のナップザックがある。 番目の品物は 個まで使用できる。 ナップザックの容量を超えないよう…