Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ARC 009 D - 覚醒ノ高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

ノード数T,枝数Mの無向グラフが与えられる.
同じノード間に枝はたかだか1本で,枝には,その枝を壊すコスト(1以上77以下)が付けられている.
ノードはA個 (77以下) の集合にわかれていて,枝は同じ集合に属すノード間にしかない.
各集合に属すノードの数は7以下.
k個の集合に属すノードの数をS[k]とすると,S[k] * (k-1)の和がA-1になっている.(解法1行目参照)
全域木にする方法が幾つか考えられるが,それをコスト順にソートして,コストが小さい方からk番目 (7777777以下) のもののコストを求める問題.
k通りも存在しないならそれを指摘する.

解法

結局は,それぞれの集合に対して,全域木にすれば,全体で全域木になるようになっている.
それぞれの集合に対して全域木を列挙してあげて,使う枝の合計コストcでできる全域木の数をカウントしておく.
(使わない枝のコストは大きくなるので,使う枝のコストを求めて,最後に全体の枝のコストから引く)
後は,DPで,全体のコストcでできる全体の全域木の数を求める.

Cによるスパゲッティなソースコード

続きを読む

ARC 009 C - 高橋君、24歳 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

要素数Nの置換Sで,S[i]=iとならないものがちょうどK個であるものの数をmod 1,777,777,777 (素数) で求める問題.
N, Kは2以上,8以下で40点.
Nは777,777,777,777,777,777以下,Kは777,777以下で100点.

解法

どの集合がS[i]=iとなってないかを選ぶ方法はC(N, K)で,これはN, N-1, ..., N-K+1をかけて,1, 2, ..., K で割ればよいのでO(K)で求められる.
すべてのiについて,S[i]=iとならない要素数Kの置換の数A[k]は漸化式があって,A[k] = (k-1) * (A[k-1] + A[k-2])などを用いればO(K).

Cによるスパゲッティなソースコード

続きを読む

ARC 009 B - おとぎの国の高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

数字 (0~9) の大小関係が与えられる.ただし0は一番小さい.
その時に整数を昇順ソートする問題.
整数を比較するとき,その整数の左には無限に0が詰まってると思い,最も左の桁で最初に違う数字をみて比較する.

解法

大小関係に対応するように数字を置き換えてソートして元に戻す.

C++によるスパゲッティなソースコード

続きを読む

ARC 009 A - 元気にお使い!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

N種類の品物を買う.(Nは10以下)
品物iはa[i]個買いたくて,1つあたり税抜でb[i]円. (a[i]は10以下,b[i]は1000以下)
消費税を5%として,必要な金額を求める問題.
消費税は合計金額にかかり,小数点以下は切り捨て.

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 012 D - Don't worry. Be Together (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

$N$ 人の人が,二次元平面上の格子点 $(x_i, y_i)$ にいる.
各ターン,各自が上下左右のいずれかの方向に $1$ だけ進む.
$T$ ターン後に,全員が $(0,0)$ にいるような進み方は何通りあるかを ${\rm modulo}$ で割った余りで求める問題.
$N \leq 100000 = 10^5$
$T \leq 100000 = 10^5$
${\rm modulo} \leq 1000000007 = 10^9 + 7$
部分点もあるが,略.

解法

各人が動く方法のパターン数をかければ良い.
まず,初期位置 $(x_i,y_i)$ と $(0,0)$ までの距離の偶奇が $T$ と一致しないなら $0$.
一致していれば,パターン数は\[ \begin{pmatrix}T \\ (T+x_i-y_i)/2 \end{pmatrix} \begin{pmatrix}T \\ (T+x_i+y_i)/2 \end{pmatrix} \]となることが観察できる.
(証明には,無駄な移動を上下か左右にいくら割り振るかで場合分けして,二項係数の積の和などに持ち込んで,Vandermonde's identityを使う)
${\rm modulo}$が素数の時(部分点にある)は,階乗の値を前計算しておいて,二項係数を求めれば良い.
満点を狙うには,$N$ 人通して累計で,各数字の階乗が何回使われたをメモる.(割り算は $-1$ 回とカウント)
後は,各階乗から,累積和を使って,各整数を何回かければ良いかを,求め,
各整数について,素因数分解したものを前計算しておいて,各素数を何回かければ良いか,まで落とす.
後は,かけていきながら,${\rm modulo}$ で余りを取る.

C言語によるスパゲッティなソースコード

続きを読む

ARC 012 C - 五目並べチェッカー (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

19*19の碁盤の上で行う,五目並べの盤面が与えられた時,その盤面が正常な状態であるかどうかを判定する問題.
ルールは,oが先手,xを後手として,交互にマークを書いていって,タテ・ヨコ・ナナメどれかに5つ並べたら終了.
それ以外のルールはないものとして扱う.

解法

まず,oとxの数を数えて,
 oの数 = xの数 + 1 なら最後に o が置いた
 oの数 = xの数 なら最後に x が置いた
 それ以外なら不正
とする.
すでに,5つ並んでいるなら,それは最後においた人でなければならない.
また,5つ並んでいるなら,どれか1個を取り除くと,5つ並ばないような状態にできなければならない.
とチェックしていく.
盤面のサイズが小さいので,取り除く石は全部確かめて計算しなおせば良い.

C言語によるスパゲッティなソースコード

続きを読む

ARC 012 B - アキレスと亀 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

高橋くんとカメが徒競走をしている.
高橋くんの速度を $v_a$,カメの速度を $v_b$ として,最初カメは高橋くんから $L$ だけ前にいる.($v_a > v_b$)
今カメがいる場所まで高橋くんが移動するのを1ステップとして,$N$ ステップ後には高橋くんとカメとの距離を求める問題.
$N \leq 100$.

解法

シミュレーションする.
距離はステップ数に関して幾何級数的に減少するのでpowなどを使って求めても良い.

C言語によるスパゲッティなソースコード

続きを読む

ARC 012 A - 週末 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

曜日の英語名が与えられるので,土曜日または日曜日までの日数を求める問題.
すでに土曜日または日曜日なら0が答え.

解法

やるだけ.

C言語によるスパゲッティなソースコード

続きを読む

ARC 016 D - 軍艦ゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

ノード数 $N$,枝数 $M$ のDAGが与えられる.
ノード $1$ からノード $N$ に移動するまでのかかる時間の期待値の最小値を求める問題.
以下の手順で移動する.
また,最大体力は $H$ で,初期体力は最大値である.
 1. 今いるノードから,出ている枝を $1$ つランダムに選び,その枝に沿って移動する.枝が出ていないなら移動できない.
 2. 辿り着いたノードに設定されている数値 $D_i$ だけ体力を減らす.体力が $0$ 以下になった場合は,それ以上何もできないので,そのようなことにはならないようにする.
 3. 現在の体力を $C$ として,$H-C$ だけ時間を消費して,ノード $1$ に移動しても良い.移動した場合は体力は全回復する.
1.~3.までの行動を $1$ 回行うと時間が $1$ だけ経過する.
ただし,期待値が無限大になる場合,ノード $N$ に辿りつけない場合はそれを指摘する.
$1 \leq N \leq 100$
$1 \leq H \leq 100$
答えは $10^6$ を超えない(期待値として有限時間で辿り着けるなら)

解法

3. のノード $1$ に戻る選択肢がなければ,今いるノードと現在体力を状態としてDPすれば良い.
答えを $X$ だと決め打ちすると,ノード $1$ に戻るときにかかる時間の期待値を $X$ を使って表すことができ,DPできる.
その結果の答え $T_X$ は,本当の答えを $T$ とすると,
 もし,$X \leq T$ ならば,帰るときに小さく見積もってしまうので $X \leq T_X \leq T$ となり,
 もし,$X \geq T$ ならば,帰るときに大きく見積もってしまうので $X \geq T_X \geq T$ となる.
これを利用して $2$ 分探索で答えを求めれば良い.

Cによるスパゲッティなソースコード

続きを読む

ARC 016 C - ソーシャルゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

カードが $N$ 種類,ガチャが $M$ 種類ある.
各ガチャを $1$ 回まわすコストと,どのカードが出るかという確率が全て与えられる.
全てのカードを集めるまでにかかるコストの平均値の最小値を求める問題.
$1 \leq N \leq 10$
$1 \leq M \leq 4$
部分点あり(原文を参照のこと)

解法

今どのカードが集まっているかを状態としてビットDPする.
既に持っているカードが出てくることがあるので,
 $X = pX + Y$

 $X = Y / (1-p)$
にするような式変形をする.

Cによるスパゲッティなソースコード

続きを読む

ARC 016 B - 音楽ゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

リズムゲームの譜面が与えられる.
譜面は $9$ 列,つまりボタンの数が $9$ 個で,ボタンを押す場所は x で書かれ,ボタンを押さない場所は . で書かれる.
また, o は連続した o の間ボタンを押しっぱなしにする.
ボタンを押す回数を求める問題.
$1 \leq$ 譜面の行の数 $\leq 100$

解法

答えは,xの数 + 上の列がoでないoの数,なとど求める.

Cによるスパゲッティなソースコード

続きを読む

ARC 016 A - クイズゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

クイズにおいて,選択肢が $N$ 個の問題を考える.
選択肢の番号は $1,\ 2,\ \ldots,\ N$ で,正解の選択肢は $M$ である.
不正解の選択肢を $1$ つ出力する問題.
$2 \leq N \leq 5$

解法

どうやっても良い.
例えば, $M=1$ なら $2$ を出力し,そうでないなら $1$ を出力する.

Cによるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B E - 天下一最短路コンテスト (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

まず,以下の問題を考える.
2次元平面上にN個の点が与えられるので,最初に与えられた点から出発して,全ての点を通るようなできるだけ短い経路を出力せよ.
この問題に対する貪欲なアルゴリズムとして,
・アルゴリズム1
 まだ通ってない最も近い点を選び,その点に行く,を繰り返す
・アルゴリズム2
 まだ通ってない点が3点以上あるなら,2番目に近い点に行く,を繰り返す
 まだ通ってない点が3点未満になったら,最も近い点に行く,を繰り返す
ただし,同じ距離の点が複数ある場合は,与えられた順番に近いとみなす.
この時,アルゴリズム2の方が,短いかアルゴリズム1と同じ長さの経路を返すようなデータセットを1つ求める問題.
Nが大きいほど点数が高く,N=100で満点だが,Nは100を超えてはいけない.

解法

適当にやればなんとでもなる.以下は解答の一例.
アルゴリズム2が良い結果を返す小さい点のパターンを見つけ,うまく繋げる
95点程度をほぼ1箇所に固めて,残りの点をランダムに配置して,条件を満たすまで繰り返す.(以下のコードはこれ)
アルゴリズム1の経路長 - アルゴリズム2の経路長などをスコアとして山登り,焼き鈍すなどの局所探索を行う.
はしご型や,規則正しく点を配置して,アルゴリズム2が勝つパターンを見つける.

Cによるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B C - 天下一ジグソーパズルふたたび (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

縦$N$マス,横$M$マス,全体で$NM$ピースのジグソーパズルを考える.
上下左右に隣り合うピースは,片方が凹で,片方が凸,端の辺は直線.
KLabのマークであるKっぽい,1辺が直線,3辺が凹のピースの数を最大がしたい.
ただし,4辺とも凹のピースを$A$個以上使って,4辺とも凸のピースが最大でも$B$個までしか使えない.
$2 \leq N, M \leq 8$.
部分点もある.(原文を参照)

解法

DPする.
左上から順番にピースを決めて行って,
 今の場所,4辺凹のピースを使った数,4辺凸のピースを使った数,過去1列分の下向きに接する面は凸か凹か?,一つ左のピースの右側の辺は凸か凹か?
を状態として,K型のピースの最大値をメモする.
状態数は多く見積もっても$1.2 \times 10^7$以下程度だが,配列で愚直にメモリ確保するとMLEに引っかかる可能性があるのに注意する.
いろいろ頑張って枝刈りすれば全探索も可能らしい.

C++によるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B B - 天下一後入れ先出しデータ構造 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

スタックのシミュレーションを行う問題.
ただし,1回の命令で,同じ数字をたくさん入れたり,たくさんPopしたりできる.
また,スタックに入っている数の数や,スタックのトップの要素を答えたりするクエリが混じっている.
また,スタックのサイズが決まっており,サイズを超えたり,空のスタックからPopしたりトップの要素を参照すると途中でエラーを出して止める.
詳細は問題文を参照.

解法

シミュレーションをやるだけ.
たくさん追加するのは,1つずつやるとTLEになるので,まとめて処理して,何が何個入っている,という形で保存する.
スタックのサイズが,符号付き32ビット整数で表せる限界まで来るので,オーバーフローに注意.(素直に64ビット整数使って気にしないのが楽)

C++によるスパゲッティなソースコード

続きを読む

天下一プログラマーコンテスト2013予選B A - 天下一人力比較 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

問題文中の15個の文字列の中で,辞書順で小さい方から7番目のものを求める問題.
文字列は入力として受け取ることもできる.
文字列はアルファベット大文字のみから成る.

解法

ソートして出力するのが一番楽.
最初の要素を0番目と数えるプログラミング言語では,7番目を出力するのにstr[6]などと指定しないといけないことに注意する.

C++によるスパゲッティなソースコード

続きを読む

ARC 008 D - タコヤキオイシクナール (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N個の箱がある.
各箱iにはパラメータa[i], b[i]が設定されている.(a[i], b[i]の絶対値は1以下)
箱iに数xを入れると,f_i(x) = a[i] * x + b[i]となって出てくる.
最初はa=1, b=0に設定されている.
M回だけ,ある1個の箱を指定して,パラメータを変える操作を行った履歴が与えられる.
また,パラメータを変更する前,各変更の後,合計M+1回だけ,
 箱1に1を入れて,出てきた数字を箱2に入れて,…,出てきた数字を箱Nに入れて出てきた数字を調べる
ということを行った.
つまり,M+1個の
 f_N( ... f_2( f_1(1) ) ... )
の値を調べた.
M+1個の値の最大値を最小値を求める問題.
50点 : Nは1000以下,Mは1000以下.
100点 : Nは10^12以下,Mは10^5以下.

解法

まず,Nが大きいので座標圧縮する.使う箱はたかだかM個.
f_2 * f_1などの合成関数はすべて a * x + b の形で書ける.
セグメントツリーのように,各区間のaとbの値を覚えておけばパラメータの変更と値の計算がlog M程度でできる.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 C - THE☆たこ焼き祭り2012 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N人 (1000以下) の人が2次元平面上にいる.移動できない.
それぞれの人は,投げることができる最大スピードと,受け取る事ができる最大スピードが設定されている.
番号0の人がたこ焼きをN個持っている.
たこ焼きを投げたら,次に投げるまでに1秒以上間隔を開けなくてはいけない.
全員にたこ焼きを配り終わる最小必要時間を求める問題.

解法

ダイクストラで各人に配布するのに必要な最小時間を求める.(1人だけに配るとして)
後は,遠い人から最短パスにそっと投げていけば良い.
最短パスなので,番号0の人が1秒おきに投げるなら,他の人は受け取るのに1秒は間隔が開くので他の人はすぐ投げれる.
自分には投げなくて良いことに注意.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 B - 謎のたこ焼きおじさん (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N文字 (50以下) の文字列Sと,M文字 (50以下) の文字列Xが与えられる.
XをK回繋げて,自由に文字を入れ替えたり,文字を消したりしてSを作りたい.
最小のKを求める問題.不可能ならそれを指摘する.
文字はアルファベット大文字のみ.

解法

各文字について,Sに含まれている数と,Xに含まれている数を調べて,必要なXの個数を求めて,それの最大値を取る.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 A - 元気にお使い!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

たこ焼き1個15円,10個100円で売っている.
N個以上のたこ焼きを買うのに必要な最小金額を求める問題.
Nは50以下.

解法

とりあえず,残り10個以上買わなくてはいけないなら,10個ずつ買っていく.
残りの端数は,10個買うか,1個ずつ買うか,安いほうを選択する.
無駄にDPしてしまった.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 D - 破れた宿題 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

N文字の数字のみから成る文字列が与えられる.
それは,等差数列をスペース無しで続けて書いた文字列で,最初の数文字,最後の数文字を消したものである.(消したのは0文字かもしれない)
ただし,初項は少なくても1文字は残っている.
元々の等差数列として考えられるものの初項と公差を答える問題.
複数あるなら,初項最小のもの,その中で公差最小のものを答える.
ただし,初項,公差は1以上の整数で,03のようにleading zeroは許されない.
25点 Nは4以下,50点 Nは6以下,75点 Nは200以下,100点 Nは1000以下.

解法

最小の初項は簡単に求まる.
例えば,192021だと1だし(2項目は92021で19,20,21は初項がでかい),1001だと100だし,00102でも100だし,000なら1000だし,800183なら800.
後は,2項目がどこからどこまでかを全部試す.
2項目が全部収まっていない時のコーナーケースに注意.
01なら初項10,公差1だし,201なら初項20,公差80だし,202なら初項20,公差1など.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 C - 節約生活 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

oとxからなるN文字 (10文字以下) の文字列が与えられる.
その文字列を,周期的に拡張して,長さ無限大の文字列と考える.(k文字目は元々のk mod N文字目)
その文字列をK個用意して,それぞれの文字列の最初にいくつかのxを追加して良い.
十分大きな全ての整数sに対して,K個の文字列のどれかのs文字目はoであるようにしたい.
Kの最小値を求める問題.

解法

最初にxを追加する数は,0からN-1までやれば十分.
なので,N種類の文字列のみ考えれば良い.
後は,どれを使うか2^N通り全探索する.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 B - 迷子のCDケース (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

N+1枚のCDがあり,0からNまで番号がついている.
CD 0はCDプレイヤーの中に入っており,その他はCD iはケースiに入っている.
M枚のCDを順番に聞く.
その際,CDプレイヤーの中に入っているCDを聞くなら何もしない.
そうでなければ,CDプレイヤーの中のCDを,聞きたいCDが入っているケースに入れ,聞きたいCDをCDプレイヤーの中に入れる.
最終的に,それぞれのケースに入っているCDの番号を出力する問題.
N, Mは100以下.

解法

愚直にシミュレーションする.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 A - 帰ってきた器物損壊!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

アルファベット小文字1文字Cと,アルファベット小文字から成る文字列Sが与えられる.
SからCを全部消した文字列を出力する問題.

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 D - アルファベット探し (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

H*W (1000*1000以下) のグリッドが与えられ,各セル白か黒.
アルファベットのABCがいくらか書かれている.
アルファベットは90度の整数倍回転してるかもしれず,鏡像反転してるかもしれず,正整数倍拡大しているかもしれない.
ただし,アルファベットは重なっておらず,アルファベットに属さない黒いセルもない.
ABCがそれぞれ何個書かれているか求める問題.

解法

色々やりかたはあると思う.
縦横斜めに連結と思い,各連結成分ごとに黒のセルの数を数え,例えば,その数が12*k^2の形ならAとする,などと判定した.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 C - 積み重ね (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

N個のダンボールが順番に運ばれてくる.
それぞれの重さが与えられる.
自分の上に積み重ねるには,自分より軽いダンボールしかすぐ上には置けない.
一度おいたら動かせない.
最小で何個の山を作れば良いかを求める問題.

解法

greedy.
置ける場所のうち,最も軽いダンボールの上に置く.
積み重ねられないなら,新しく山を作る.
もしくは,山を1つずつ作っていく感じで,ダンボールの中からgreedyに最も長い非増加列を引き抜いていく.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 B - あみだくじ (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

あみだくじのアスキーアートが与えられる.
あたりは左から何本目かを判定する問題.

解法

下から辿っていく.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 A - 宝くじ (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

ロト6っぽい宝くじが何等か判定する問題.
宝くじで,選ばれた数字6個,ボーナス数字1個,自分が選んだ数字6個が与えられる.

1等 : 6つ数字が一致
2等 : 5つ数字が一致し,残りの1つの数字がボーナス数字と一致
3等 : 5つ数字が一致で,2等でない
4等 : 4つ数字が一致
5等 : 3つ数字が一致
ハズレ : 全部に該当しない

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 005 D - 連射王高橋君 (We have nothing to do with him) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

0123456789+=のボタンのある電卓がある.
壊れているボタンが与えられる.ただし01+=は壊れていない.
最終的に表示させたい数 (10^18以下) を表示するまでに押さなくてはいけないボタンの回数の最小値化したい.
そのような方法を1つ出力する問題.

解法

数字をそのまま打てるならそうする.
そうでなければ,DP + 経路復元する.
まず,使える数字を使ってk (200以下ぐらい) を作る最小個数の組み合わせは最初にDPで計算しておく.
後は,各桁ごとにDPしていく.下の桁から見ていく.
何個の数字の和で作るかは全探索する.
状態は,どの桁を見ているか,繰り上がりはいくらあるか,前の桁で使った数の数(足し合わせるものの中でその桁が存在する数).

Cによるスパゲッティなソースコード

続きを読む

ARC 005 C - 器物損壊!高橋君 (Search and destroy) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

H*W (500*500以下) のグリッドが与えられる.
各セルは,通れるセルか,塀があるセルかのどちらか.
上下左右に移動でき,2個まで塀を壊すことができる.
スタートからゴールまで移動できるかどうかを判定する問題.

解法

何回塀を壊したかでノードを多重化してBFS,DFSなどする.

Cによるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。