The Secret Number 解説
問題名：The Secret Number (PKU) 出典：Problem C, ACM/ICPC Japan Domestic, 2003-10-03 難易度：☆☆☆ 問題の種類：DP 解法：動的計画法 解答ソースコード： 2030-deq_loop.cpp（ループ） 2030-deq_memo.cpp（メモ化探索） アルゴリズムの概略と計算量 素直な方法 「2次元のマトリックスから最も大きな数字列を探し出せ」という問題。 真っ先に思い浮かぶのは「始点ノードを探して再帰で右or下に数字を連結していく」という解法でしょう。 先頭のゼロや細かなあれこれを無視すると，こういう感じのコーディングになります： def rec(x, y, string): string += field[x][y] answer = max(answer, string) if 右が数字: rec(x+1, y,
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
コンテスト用 細かなコーディングテクニックについて
ICPC国内予選直前会議 細かなコーディングテクニックについて 自己紹介 SRM: tomerun Marathon: tomerun Codeforces:tomerun 小さな会社で何でも屋な感じのプログラマやってます Java・C++・C#・Ruby・Objective-C ※ICPC参加経験はありません 内容 大きな定数の打ち間違え防止 簡易なdoubleへのキャスト 探索での番兵 プログラムできることは手動でやらない Off-by-Oneエラー防止 できるだけルート取らない 積極的に関数化 (C++)配列のゼロ埋め (Java)ペアをソートする (Java)ビット演算の便利機能 注意 紹介するのは、コンテストのコードを書くために特化したスタイルです。 仕事や研究で使うような、長期的にメンテナンスする可能性のあるコードで使うのは推奨されないものも多くあります（推奨できるものもありま
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
