hogecoder

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

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 から始まるのと、親と子の取得方法がわかってればセグ木は書けます (ホンマか?)— つたじろう@帰省 (@_TTJR_) March 29, 2017 この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳しい・…

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

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

RUPC2017 Day3 北大セットのまとめ

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

立命館大学プログラミング合宿2017 参加記

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

ICPC 国内予選 2016 D: ダルマ落とし

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

KUPC2012 D: 権力

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

AtCoder Beginner Contest 018 D: バレンタインデー

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

AtCoder Regular Contest 043 B: 難易度

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

AtCoder Grand Contest 010 B: Boxes

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

AtCoder Regular Contest 027 C: 最高のトッピングにしような

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

TopCoder SRM707 Div 2 Med: StepsConstruct

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

AOJ DPL_1_G: Knapsack Problem with Limitations

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

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。 問題概要 原文 → Equal Sum Sets | Aizu Online Judge 以下の相異なる自然数 個の合計が となる組み合わせの総数を求めよ。 解説 以下の各数字 について、 を使うときと使わないときを考えてみます。 を使うと…

TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました) 今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。 問題概要 原文 → TopCoder Statistics - Problem Statement 英小文字のみで構成された文…

東京工業大学プログラミングコンテスト2015 D: 文字列と素数

競プロに逃げすぎてレポートが進みません。 問題概要 原文 → D: 文字列と素数 - 東京工業大学プログラミングコンテスト2015 | AtCoder 文字列 が与えられる。各文字を、同じ文字は同じ数字・違う文字は違う数字になるように '1', '3', '5', '7', '9' のいず…

AOJ 0037: Path on a Grid

AOJ

バグが取れなくて相当苦労した。 問題概要 原文 → 格子状の経路 | Aizu Online Judge 格子の各辺が壁であるかどうかの情報が与えられる。壁に右手をついたまま1周するときの経路を出力せよ。 解説 前回の記事 と同様の方法で解いてみました。 今見ている方向…

ICPC 国内予選 2010 B: 迷図と命ず

AOJ

あけましておめでとうございます。私はひたすら AOJ-ICPC を埋めています。 実装が面倒だなあこれ・・・と思ったのでほぼ自分用記事を書きます。 問題概要 原文 → Amazing Mazes | Aizu Online Judge 縦 、横 の迷路が与えられる。迷路の壁の情報が与えられ…

ICPC アジア地区予選 2014 F: There is No Alternative

今年ももう終わりですね。 問題概要 原文 → http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf 重み付き無向グラフ が与えられる。 の最小全域木に必ず含まれる辺はいくつあるか? 重みの総和と共に出力せよ。 解説 まず、普通に最小全域木…