Entries

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

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

ARC 005 B - P-CASカードと高橋君 (This story is a fiction) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

9*9のグリッドの各セルに1文字の数字が書かれている.
最初の場所と,方向が与えられるので,その方向に4文字読む問題.
端に到達したら,鏡に反射したように進行方向を変える.

解法

やるだけ.

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

続きを読む

ARC 005 A - 大好き高橋君 (Love me do) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

N個 (50以下) の単語からなる文字列が与えられる.
各単語はアルファベットのみから成り,単語と単語の間には1つのスペースがある.
また,最後の単語の直後に1つのピリオドがある.
単語の中に,TAKAHASHIKUN,Takahashikun,takahashikunが何個あるか,合計値を求める問題.

解法

やるだけ.

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

続きを読む

ARC 004 D - 表現の自由 (Freedom of expression) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

問題文が簡単なのでそのまま転載する.
整数 N (絶対値は10^9以下) と M (10^5以下) が与えられる時、整数 N を M 個の整数の積で表す方法は何通りあるでしょうか。
その答えを 1,000,000,007 で割った余りを答えてください。
補足:1*2と2*1は別とみなす.

解法

各素因数ごとに,M個のどこに割り振るか,重複組合せの数をかけていく.
-1は何個使うかを場合分けして,重複組合せの数を足していく.

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

続きを読む

ARC 004 C - 平均値太郎の憂鬱 (The melancholy of Taro Heikinchi) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

1からNまで平均値を求めるのに,1つの整数Mを足すのを忘れた.
つまり,(1+2+...+N - M) / Nの値が分数の形で与えられるので,考えうるNとMの値の組を全部求める問題.
存在しないならそれを指摘する.

解法

Mは1以上M以下なので,(1+2+...+N - M) / Nの値から大体のNの値を推定できる.
考えうるNの値は高々2個.
Nを決めれば,Mは計算できる.

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

続きを読む

ARC 004 B - 2点間距離の最大と最小 (Maximum and Minimum) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

N+1個の点が2次元上にある.点は0からNまで番号がついている.
点iと点i+1の距離(ユークリッド距離)が与えられる.(i=0, 1, ..., N-1)
点0と点Nの距離の最大値と最小値を求める問題.

解法

最大値は一直線上に番号順に並んでいる場合で,距離の和.
最小値は,最も距離が離れている点たちを基準に考えて,後はどんどん近づけていけば良い.
近づきすぎる場合は,うまく調整できて絶対に距離0にできる.

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

続きを読む

ARC 004 A - 2点間距離の最大値 (The longest distance) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

2次元平面上にN個 (100以下) の点が与えられる.
最も遠い2点間の距離(ユークリッド距離)を求める問題.

解法

全部の2点間の距離を求めて最大値を取る.

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

続きを読む

ARC 003 D - シャッフル席替え (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N人 (11以下) の人が,等間隔に円周上に座っている.
隣会いたくない人の組がM (10以下) 与えられる.
K回 (0以上20以下) だけランダムに異なる2人を選んで,入れ替えるという操作を行う.
隣会いたくない人の組が全部隣り合ってない確率を求める問題.
絶対誤差2*10^-3以下であれば正答とみなされる.

解法

許容誤差がとても大きいので,モンテカルロ法.
十分な回数だけランダムにシミュレーションして確率を計算すれば良い.

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

続きを読む

ARC 003 C - 暗闇帰り道 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N*M (500*500以下) のグリッドが与えられる.
また,各セルの明るさの初期値 (1以上9以下) が与えられる.
時間t後の各セルの明るさは 明るさの初期値 * 0.99^t となる.
上下左右に1マス移動すると,移動後に時間が1進む.
始点から終点まで移動するのに,通るセルの明るさの最小値を最大化したい.
最大値を求める問題.

解法

答えに対して2分探索する.
答えを決めると,各セルについて,どの時間までなら通ることができるか決まるので,BFSでゴールに辿り着けるかどうか判定できる.

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

続きを読む

ARC 003 B - さかさま辞書 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N個の文字列が与えられる.
各文字列は20文字以下で,アルファベット小文字からのみなる.
さかさま辞書順にソートする問題.
さかさま辞書では,最後の文字が早いほど最初に来て,最後の文字が同じなら最後から2文字目で比較する・・・といった感じ.

解法

それぞれの文字列を逆順にして,ソートして,それぞれの文字列をもとに戻す.

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

続きを読む

ARC 003 A - GPA計算 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N文字のABCDFのみからなる文字列が与えられる.
Aは4点,Bは3点,Cは2点,Dは1点,Fは0点として,平均点を求める問題.

解法

やるだけ.

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

続きを読む

ARC 002 C - コマンド入力 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #002
問題文

問題概要

ABXYのみからなるN文字の文字列Sが与えられる.Nは1000以下.
LとRをABXYからなる2文字の文字列を自由に選び,Sの中に含まれるL,Rを自由にL,Rという1文字に置き換え,
Sの長さを最小化する問題.最小値を求める.

解法

LとRをどれに割り当てるか,(4^2)^2通り全部試す.
Sに含まれるLとRを置き換えるのは,greedyに最初に表れるのから置き換えていけば良い.

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

続きを読む

ARC 002 B - 割り切れる日付 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #002
問題文

問題概要

Y年M月D日を含め,それ以降で,Y/M/Dが整数となる最初の日を求める問題.
Yは1000以上2999以下.

解法

1日ずつ進めながら条件を満たす日を探す.
1月1日は条件を必ず満たすので,365日程度探せば必ず見つかる.

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

続きを読む

ARC 002 A - うるう年 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #002
問題文

問題概要

Y年がうるう年かどうかを判定する問題.Yは1000以上2999以下.
うるう年の定義は問題文参照.

解法

やるだけ.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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