Atcoder
青色の問題.鉄則本で習ったNimのいい練習になりそうです. atcoder.jp
水色の問題.本番だとしんどそう. atcoder.jp
水色の問題.そのまま約数列挙するのが不可能なものをどう見るか. atcoder.jp
水色の問題.桁DPの立て方をしっかり学べてよい. atcoder.jp
橙色の問題.箱に入れるという動作がどういうものか解釈してみましょう. atcoder.jp
青色の問題.最小コストは求められる.そっからどうするか.グラフの問題は難しい. atcoder.jp
Markdownでのテスト投稿. うまく反映されていると嬉しい. atcoder.jp
Atcoder Beginners Contest 250(ABC250)で無事,茶色になれましたので何をやったかのご紹介をいたします.これが初心者プログラマーやAtcoderをやってみたいけど何をすればいいか分かっていない人の参考になれば幸いです.
青色の問題.Atcoder版蟻本に掲載されているやつです.何重のマトリョーシカを作れるか. atcoder.jp 問題の説明 箱が個あり,それらを入れ子にします.ある箱が,それより縦・横ともに大きいサイズの箱にのみ入れられるとしたとき,最大で何重の入れ子が作成可能か…
コンテストの名前の通りDPの問題.どのようにDPテーブルを更新するかが少し特徴的なのでブログにまとめておく.新規性は1ミリもありません. atcoder.jp 問題の説明 以下の正整数であり,十進表記したときの各桁の数の和がの倍数であるものの個数を[tex: mod 1,0…
青色の問題.久々にアルゴリズムもへったくれもない問題です.数学好きなのでこういった問題の方が好きです. atcoder.jp 問題の説明 からを並べた順列が与えられる.以下の条件を満たす数列および,を出力せよ. 条件 正整数列は狭義単調増加 正整数列は狭義単調…
DPの問題.前日の情報をどうするか,そこがカギとなります. atcoder.jp 問題の説明 温度条件が度の下で日服を選んだ場合の派手さの差の絶対値の合計の最大値を求めよ. 条件 考えた事 派手さの差の絶対値の合計を考える.つまり前の情報を遷移させる必然性を伺わ…
DPの問題.ナップサック問題+α.スクリーンショットの重要度ってなんやねん. atcoder.jp 問題の説明 枚数が枚,幅がに収まる条件の下で画像を選ぶときの重要度の合計の最大値を求めよ. 条件 考えた事 枚数制限がない場合,これは典型的なナップサック問題と呼ば…
いよいよDP.最初は優しめの問題から. atcoder.jp 問題の説明 高橋君が回または段のジャンプを行います.回のジャンプの後ににいる可能性があるか答えなさい. 条件 入力は全て整数. 考えた事 まず,DPとは何をする手法なのか.端的に言えば値を記憶する配列を作…
Greedyの問題.どうマッチングさせると仲良しさんが作られるか. atcoder.jp 問題の説明 赤い点の外側にある青い点を結ぶことで作る事の出来るペアの個数の最大値を求めよ. ただしでかつのとき,はの外側にあるという. 条件 赤い点と青い点の座標,座標は全て相…
Greedyはブログにまとめてなかったなと思ったので.ゴミ屋敷の住人必見!? atcoder.jp 問題の説明 高橋君が個の箱を積み上げる時に出来る箱の山の最小個数を求めなさい.箱にはその重さ以下の箱を重ねる事ができる. 条件 考えた事 Greedyの基本は「その場での…
0-1BFSの問題.障害は多い方が燃えるよね. 問題のリンク 問題の説明 高橋君はの迷路を移動する.高橋君は2回まで障害物を乗り越えられるものとして,ゴールに辿り着けるかを判定せよ. 条件 考えた事 迷路の基本的な実装は, garakutagoya.hatenablog.com BFSにつ…
BFS(深さ優先探索)の問題.最短時間で工場見学できるカナ?! 問題のリンク 問題の説明 の区画のこの町には個の工場があり,それぞれの工場が硬さのチーズを作っている.チーズの硬さは工場によって異なり,硬さからまでのチーズを生産出来る工場がちょうどつず…
全探索の問題.基本にして大事なんだと思う(ゆるふわっとした表現.) 問題のリンク 問題の説明 人の生徒のグループが与えられ,こいつらが「カラオケ大会」に出る事となった. 歌える曲は曲であり,番号が曲を歌うと,点を取る事が分かっている. コンテストのルー…
DFS(深さ優先探索)の実装の練習です.蟻本を読みながらチャレンジ. 問題のリンク 問題の説明 の大きさの迷路が与えられています.各々のマス目にはs,g,.,# のいずれかが与えられ,高橋君は自分のいる場所から上下左右に動く事が出来ますが,斜めに移動する事は出…