AtCoder
HTTF 2024 (AHC027) に参加しました。最終順位は 71 位でした。コンテストを通して焼きなましを初めてフル活用したので、いろいろ振り返りをしていきます。 問題はこちらです。 atcoder.jp 最終的な解法 超かんたんに説明すると、こういう解法でやりました。…
tsutaj です。このたび、マイナビ出版から発行される 「アルゴリズム実技検定 公式テキスト[上級]~[エキスパート]編」 の執筆をさせていただきました。kenkoooo さん と けんちょんさん との共著です。2023/3/27 に発売予定です! アルゴリズム実技検定…
問題概要 原文はこちら atcoder.jp 棒が 本ある。これらのうち異なる 本に輪を投げ入れることを 回行う。投げ入れ方によって以下のように得点が定められる。 回目に 番目の棒に輪を投げ入れたとき、 点を得る。これらの合計を とする。 番目の棒について、全…
問題概要 原文はこちら atcoder.jp 長さ の数列 があり、 ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 回行った後、最終的にできた数列を出力せよ。 整数 が与えられるので、 と を交換する。 整数 が与えられるので、 を…
調べても解説がなかったので 問題概要 原文 → D - 大爆発 日本語なので元の問題文参照 解説 まず自明なケースとして、以下があります。地味に厄介なので最初に弾きましょう。 ブロックがひとつも存在しない (答えは ) 全てのマスにブロックが存在する (答え…
2019/8/31 に開催された 東京工業大学プログラミングコンテスト に参加しました。 前日まで 某社に行ったり五等分の花嫁展に行ったり中本を食べたりした。 かわいいを摂取 (@ 池袋サンシャインシティ 展示ホールA in 豊島区, 東京都) https://t.co/jl2h6XfzG…
問題概要 日本語があるので原文参照 → F - Permutation and Minimum 解説 と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態とし…
数学的な知見がいっぱいあったので備忘録です。 問題概要 日本語なので原文を参照してください → D: チップ・ストーリー ~黄金編~ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder 解説 この問題を解くには、いくつかの数…
問題概要 日本語なので原文参照 → D - Checker 解説 公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。 考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。こ…
hogehoge アルゴリズムのライブラリを貼るだけで解けるんじゃなくて、それにひと工夫加えないと解けない問題すき— tsutaj@進捗 6/35 (@_TTJR_) September 29, 2017 この手の問題すき。すきだから記事を書いてしまう。 問題概要 原文を参照してください → C: …
初めて Trie 木を使ったので、ハマったところとかを記事でまとめておきます (完全に自分用) 問題概要 原文参照 → C: たんごたくさん - 天下一プログラマーコンテスト2016本戦(オープンコンテスト) | AtCoder 解説 与えられる単語すべてを検索対象として、T…
どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。 問題概要 日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder 解説 まず、出力する数列の長さは に固定してしまいます。この…
もう 7 月かあ・・・。 問題概要 を求めよ。ただし は と の最小公倍数を指す。 制約: 解説 愚直にやるのは無理なので、数学をします。 まず、 なる関係があります。これを使って与式を変形すると が求めたいものになります。 ここで、 の取りうる値の数は …
ちょっと迷ってしまったので。 問題概要 原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder 解説 rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか? となるような配列を作ります。 あるマス について、この値は以…
何でこれが詰まっちゃうかな・・・。 問題概要 原文 → 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 種類のトッピングがある。トッピング は 枚のチケットを交換することで入手でき、その価値は である。 チケットにはスペシャルチケ…
競プロに逃げすぎてレポートが進みません。 問題概要 原文 → D: 文字列と素数 - 東京工業大学プログラミングコンテスト2015 | AtCoder 文字列 が与えられる。各文字を、同じ文字は同じ数字・違う文字は違う数字になるように '1', '3', '5', '7', '9' のいず…
久しぶりに解説記事。またまたゲームの問題。 問題概要 原文 → G: 石取りゲーム - code thanks festival 2014 B日程 | AtCoder 個の石が積まれた山があり、人のプレイヤーが交互に石を何個か取っていき、最後の石を取ったプレイヤーが勝ちとなるゲームを行う…
DISCO presents ディスカバリーチャンネル コードコンテスト 2016 本戦に参加しました。どこよりも早く、を目指して参加記書いてみます。 -N日目 (予選) セキュリティミニキャンプ in 北海道(過去記事参照) の1日目の夜にDDCCの予選があったので、ホテルから…
問題概要 原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder 長さの順列を並び替えたとき、 (1-indexed)となる要素が個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。 解説 まず、となる要素をどこにするかを決…
デジャヴを感じたので。 問題概要 原文 → B: 石取り大作戦 - AtCoder Regular Contest 046 | AtCoder 高橋くんと青木くんは個の石の山から交互に石を取るゲームを行う。交互に1個以上の石を山から取っていき、最後の石をとったプレイヤーが勝者となる。先手…
問題概要 原文 → D: 1 - AtCoder Beginner Contest 029 | AtCoder である十進表記の自然数Nが与えられる。1からNまで書きくだす時、1という数字を何回書いたかを求めよ。 数学解法 解説 ナイーブな解法(部分点解法)はここで解説してもしょうがないので略。 …