ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

前計算

ABC113 D - Number of Amidakuji

問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…

AOJ 2233 Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

AOJ 1175 - そして,いくつになった?

問題 提出コード 個人的にICPCの中でも結構好きな部類の問題です。 解法 今回もc言語です。 メモ化再帰をしていきます。 円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、…

CODE FESTIVAL 2018 qual A D - 通勤

問題 提出コード 解法 後ろの方から見ていくと見通しが良くなるのかな、と思いきやそうでもありませんでした。 番目のガソリンスタンドで燃料を補給する場合の、~番目のガソリンスタンドの建て替え方 とします。 仮に今燃料が満タンの状態で番目のガソリンス…

AOJ 1167 - ポロック予想

問題 提出コード 解法 正四面体数を記録して、重複可能ナップサック問題を解いていきます。 dp[i][j] = i番目までを使用して、数がjになるような組み合わせの中の最小個数 = i番目の正四面体数 とすると、 dp[i][j] = min(dp[i-1][j],dp[i][j-]+1) となりま…

AOJ 1154 - 月曜土曜素因数

月曜土曜素因数 提出コード まずは、nの最大値である300000までの月曜土曜数を抽出し、動的配列に保存します。 愚直に1つずつ、7で割ったときの余りが1or6になっているかどうか調べて問題ありません。 そうしたら、次に月曜土曜素数を求めます。先ほど求めた…

ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店 提出コード 満点を取るには、ほぼでクエリにこたえていかないといけません。 そこで、 ans[i][j] = i番目の品物を使わずにj個選ぶ方法 とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。 まず…

ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

ABC106

なんだかんだまだARC出たことないので出てみたいですね A - Garden 提出コード (a-1)*(b-1)をすればよいです。 道の部分を無視して畑をくっつけると、実際に上の式のように、a-1とb-1の辺の長方形になります。 B - 105 提出コード 1からnまでの数字について…

ABC084

バチャコン5回目です(4回目は復習回でした)。 A - New Year 提出コード 12月30日のn時から年が明けるまでにどれくらい時間がかかるか、という問題です。 12/31の一日分まるまる24時間+今日の残り時間(24-n)を出力します。 12/31の分は、問題を読み間違えてい…

Mujin Programming Challenge 2018

目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました A - コンテスト名 提出コード 頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危な…