2019-05-01から1ヶ月間の記事一覧
ABC079-B - Lucas Number …リュカ数？ なんだか圧倒されるが、定義が書かれているので落ち着いて読んでみる リュカ数の最初の2つは 2 と 1 で、3番目の数は1番目と2番目を足した数 4番目の数は2番目と3番目を足した数、5番目の数は3番目と4番目を足した数 6…
ABC078-B - ISU ・席全体の幅がX ・人の幅がY ・席の端と人との間はZだけ空ける、人と人との間もZだけ空ける 以上の条件で最大何人の人が座れるか、という問題 まず、1人座るためには、両側にZの間隔が必要（2Z）で 人の幅分の長さ（Y）も必要なので、Y + 2Z…
ABC077-B - Around Square を解く(1) の続き 1から順に列挙していく方法ではTLEになってしまった 試しに手元で実行して 10^9 を入力してみたら5分経っても終わる気配がなかった 提出する前に気づけましたねこれは… ということで、もっと効率のよい方法を考え…
ABC077-B - Around Square N以下の平方数（整数を2乗した数）を求める問題 1, 4, 9, 16 … と順番に列挙していって Nを追い越した時にその1つ前の数を答える方法でいこうと思う 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 N=int(input())…
ABC076-B - Addition and Multiplication 初期値 1 に対して N回、「2倍する」か「Kを足す」かを行ったときに 考えうる最小の値を求める問題 常に小さくなるような選択を続ければ、最終的な値も最も小さくなるはず よってN回ループを回して、1回毎に「どちら…
ABC075-B - Minesweeper '#' を地雷と見立てて、実際のマインスイーパーのように 隣接地雷数を記載する問題 左上から右下にかけて全マスを探索していって '#' ならそのままにする '.' なら 隣接八近傍を確認して '#' の数に書き換える という処理をしていく …
ABC074-B - Collecting Balls (Easy Version) 問題文が長い… プログラムを書くこと以上に、問題内容の理解の方が大変そうだ …読んでみたがイマイチよくわからなかったので サンプルの説明を読んでみた 入力形式 N K x1 x2 ... xN 上記の形式で入力があったと…
ABC073-B - Theater 映画館の席に座っている人数を「区間」で与えられるので その合計を求める問題 例えば、6 - 8 という区間が与えられたら 6 7 8 に 3人 座っているということになる 答えは 8 - 6 + 1 = 3 で導かれる。 + 1 することに注意したい また、席…
ABC072-B - OddString 与えられた文字列の奇数文字目だけを抜き出した文字列を出力する問題 ループ処理を使って1字ずつ取り出していって 奇数番目のときにくっつけていくイメージで解く 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 s=inp…
ABC071-B - Not Found 与えられた文字列に含まれないアルファベットを答える問題 26字全パターン確認すればいい 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 S=input() # a〜z l=['a','b','c','d','e','f','g','h','i','j','k','l','m','…
ABC070-B - Two Switches 1発で通すのは中々難しい問題 場合分けの際に漏れがでやすい シミュレーションするならば 2つの線分を横に並べた状態をイメージするとわかりやすいだろう 全パターンを以下に示す その1 AーーーーーーB CーーーーーーD その2 Aーー…
ABC069-B - i18n 'internationalization' のような 先頭の文字 'i' と 末尾の文字 'n' の間に 18字の文字がある場合は 'i18n' のように変換する、という問題 'smiles' なら 's4s' となる 数字の部分は、「文字全体の長さ - 2」で表すことができる 以上を踏ま…
ABC068-B - Break Number 整数Nが与えられるので、1以上N以下の整数のうち 最も2で割れる回数が多いものを求める問題 制約が 1 <= N <= 100 なので 1つ1つ確認していっても十分に間に合うだろう 以上を踏まえて書いたコードを以下に示す 提出したコード # 入…
ABC067-B - Snake Toy N個の数字からK個の数字を選び それらの和の最大値を答える問題 要するに大きいものからK個選べばいいだけ 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 N,K=map(int,input().split()) l=list(map(int,input().split…
ABC066-B - ss 与えられた文字列の末尾を削除して それが「偶文字列」であるかを判定していく問題 （偶文字列とは、同じ文字列を2つ並べてできた文字列） 1文字ずつ末尾を消していって その都度2つに割って一致するかどうかを確認していけばいい 以上を踏ま…
ABC065-B - Trained? 結構混乱する問題だ 適当にシミュレーションしてみて、ボタン2が光ればOK、としたいところだが… 光らない場合は無限ループしているということになる 無限ループになった場合にすぐに気づけるよう 一度押したボタンを記録していく必要が…
ABC064-B - Traveling AtCoDeer Problem なんだか一見難しそうな雰囲気の問題だが よく読むとかなり簡単な問題だ というのも、ソートして端の数の差をとるだけでいい 方向転換せずに端から端まで移動するパターンが最小になるのは明らかだからだ 以上を踏ま…
ABC063-B - Varied 与えられた文字列中にアルファベットの重複があれば 'no' 重複がなければ 'yes' と答える問題 重複と言えば、set を使うのは典型パターン （参考：ABC009-B - 心配性な富豪、ファミリーレストランに行く。 を解く） set を使った後の文字…
ABC062-B - Picture Frame '#' で与えられた文字列を囲って出力する問題 サクッと実装していきたい ポイントとしては 与えられた文字列の横幅 W を枠で囲った後の横幅は W+2 になる、という点 つまり、一番上は '#' を W+2 個並べればいい。一番下についても…
ABC061-B - Counting Roads 各都市の間に引かれた道の本数を数える問題 一見難しそうに見えるけれど 各数字の出現回数をカウントしていけばいいだけ 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 N,M=map(int,input().split()) l=[0]*N fo…
ABC060-B - Choose Integers を解く(1) の続き 余りの出現パターンはループするのでは？ という推測が立ったので その推測が成り立つ前提で考察を進めていく ループするとなると、2周目以降を調べる必要がなくなるので 1周目までの余りの中に答えがあれば 'Y…
ABC060-B - Choose Integers Aの倍数を好きなだけ選んでよいので、選んだ数の総和をBで割った余りが Cになるのかどうかを調べる問題 なんか凄く難しそうな問題が来た。どうやって解けばいいんだ… というか、好きなだけ選べるんならどんな余りであろうが 出来…
ABC059-B - Comparison 2つの数の大小比較を行う問題 Python のように多倍長整数が使える言語なら、そのまま比較するだけ 以上を踏まえて書いたコードを以下に示す 提出したコード # 入力 A=int(input()) B=int(input()) if A>B: print('GREATER') elif A==B…
ABC058-B - ∵∴∵ 2つの文字列が与えられるので、各文字列の先頭から1文字ずつ 交互に組み合わせて文字列を作る問題 言われた通りにシミュレーションして文字列を作ればいいだけだが 2つの文字列の長さが同じ場合と、異なる場合がある 適当に実装すると配列外…
ABC057-B - Checkpoints 平面状にいる複数の人を、与えられた複数のチェックポイントのいずれかに 移動させる。そのときの移動距離の総和の最小値を求める問題 人の数とチェックポイントの数はそれぞれ最大で50なので 総当たりで距離を計算しても充分間に合…
ABC056-B - NarrowRectanglesEasy 2つの同じ幅の長方形があり、上側にある長方形を横方向にどれだけ動かせば お互いが接する位置に移動できるかを求める問題 この問題は、2つの図形の位置関係をよく考える必要がある 具体的には、上の図形が下の図形より右側…
ABC055-B - Training Camp 問題文の通りにシミュレーションすることで答えを求めることができるが N が大きくなると、シミュレーションではとても時間がかかってしまう しかしこの問題では、答えを 1000000007 で割った余りを 出力することとなっている この…
ABC054-B - Template Matching テンプレートマッチングをする問題 画像処理の勉強をしたことがある人ならば一度は書いたことがあるかもしれない イメージとしては、テンプレート画像を探索先の画像の左上から 右端にかけて動かしていき、各領域が一致するか…
ABC053-B - A to Z String 与えられた文字列内にある連続する部分文字列の中で 'A' で始まって 'Z' で終わるもののうち、一番長いものを求める問題 そういった連続する部分文字列が1つしか存在しない場合は 適当に取っても特に問題はないが、複数存在する場…
ABC052-B - Increment Decrement 条件を満たしたときに加算・減算するのは問題ないと思う 最終的な値を出力するのではなく、最高値を出力することに注意 加算・減算後に最高値を随時更新していく方法が簡単かと思われる 以上を踏まえて書いたコードを以下に…
