judge.u-aizu.ac.jp 問題 100000 に以下の操作を n 回おこなった後の値を求めよ。 ・1.05倍し、1000未満を切り上げる 考察 まず 1.05倍する 操作についてですが、「v * 1.05」とするよりも「v * 105 / 100」としたほうが誤差が少なくなります。 次に 1000 未…

AIZU ONLINE JUDGE の Introduction to Programming I の最後に構えている問題、Dice I, II, III, IV を全部まとめて解いてしまいたいと思います。一見すると何やらややこしそうですが、実際にはオブジェクト指向・全探索と、プログラミングの基本が詰まって…

judge.u-aizu.ac.jp 問題 長さ N の数列と整数 X（※Long型）が与えられる。 数列の部分列のうち、和が X 以下であるようなものの個数を求めよ。 考察 しゃくとり法の問題です。例によって詳細は省略します。 今回は自分で一から実装するのではなく、以下のペ…

atcoder.jp 問題 長さ N の数列と整数 K が与えられる。 積が K 以下であるような数列の部分列のうち、最も長いものの長さを出力せよ。 考察 しゃくとり法の典型問題……ということで何とか自力で考察・実装しました。 ・積が K より大きい → 左端を伸ばす ・…

atcoder.jp 問題 長さ N の数列がある。 数列の長さ 3 の部分列のうち、初めて和が K 未満になるような部分列の位置を求めよ。 考察 勉強のため、二種類の解法で解きたいと思います。 累積和から部分和を求める 数列に対してあらかじめ累積和をとっておくこ…

atcoder.jp 問題 N 個の数字を A,B の2つのグループに分ける。 Aグループに属する数字の合計を sumA 、Bグループに属する数字の合計を sumB とする。 sumA, sumB の差が最小になるようにグループ分けをするとき、sumA, sumB のうち大きいほうを出力せよ。 考…

atcoder.jp 問題 N*M*L の大きさの箱に、P*Q*R の大きさの荷物はどれだけ入るか。 荷物はどの向きで入れてもよい。 考察 以前作成した nextPermutation の使いどころがやってきました。 ・Javaでnext_permutationメソッドを作ってみる - 文系プログラマーの…

atcoder.jp 問題 問題 i は、解いたときに貰えるスコアが 100*i 点、問題数が p[i] 問、全ての問題を解いたときに貰えるボーナススコアが c[i] である。これらの問題を解いてスコア G以上 を得るとき、少なくとも何問の問題を解かなければならないか。 考察 …

codeforces.com 問題 x (1 以下の条件を全て満たすように、a,b を選んで出力せよ。条件を満たすように a,b を選べない場合は -1 を出力せよ。 ・1 ・a を b で割り切ることができる ・a*b > x ・a/b 考察 x=1 のとき、明らかに選べないので、-1 を出力します…

AtCoder Grand Contest 031 に参加しました。 2時間、一生懸命考えましたが解法のカの字も浮かびませんでした。したがって提出していません。 A - Colorful Subsequence atcoder.jp 文字の出現回数+1 をかけ合わせるだけでいいみたいです。 仮に、a=1, b=1, …

codeforces.com 問題 範囲 L,R (1 L,R の範囲内にあるような x,y (x!=y) で、y を x で割り切ることができるものを出力せよ。 なお、そのような x,y が存在することは保証されている。 考察 x!=y であるような x,y の存在が保証されているので、範囲には少な…

atcoder.jp 問題 省略 考察 ※以下、0オリジン 問題文を ・Xの指定された部分を連結すると S,Tになる ではなく、 ・S,T を指定された通りに並べたとき、矛盾なく X を作ることができるか と読み換えて考えます。 N=6, M=3 のとき、S,T は表のように並べること…

atcoder.jp 問題 最初、3人はクッキーを A,B,C 個持っている。 操作を1回おこなうごとに、それぞれの人は「他の2人が持っているクッキーの個数の平均値」を同時に受け取る。 いずれかの人のクッキーが奇数になるまで操作をおこなうとき、操作は何回可能か。 …

codeforces.com 問題 N (2素数の和で表せ。 どの素数を何回使ってもよい。 考察 以前記事にした以下の問題とほとんど同じ考え方で解けます。 ・Dice Rolling [ Educational Codeforces Round 56 (Rated for Div. 2) A ] - 文系プログラマーのプログラミング…

前回作成したオセロのプログラムを、Eclipseではなくコマンドプロンプトから実行してみます。 jpliterature.hatenablog.com JARファイルを作成する ・プロジェクトを右クリック → エクスポート ・Java → Jarファイルを選択して次へ → エクスポート先を指定し…

オセロを作ったので、ソースコードを淡々と紹介していきます。 対戦画面はこんな感じです。 コンソールに石を置きたい位置を打ち込むことで対戦を進めていきます。 対戦相手となるAIの強さは以下の2種類から選ぶことができます。 ・よわい（裏返す個数がなる…

codeforces.com 問題 1～n のIDを持った生徒が合計で n 人いる。 それらの生徒の 4教科のスコア が ID の小さい順に与えられる。 ID が 1 である生徒の成績（4教科の合計スコア）は上から何番目か、出力せよ。 ただし、スコアが同じ場合は ID が小さいほうを…

codeforces.com 問題 2～7の数字が書かれた六面体ダイスと、n 個の数字がある。 ダイスを振って、出た目の和でそれぞれの数字を作るとき、何回振れば作ることができるか、それぞれの数字について出力せよ（最小回数ではないことに注意）。与えられる数字は、…

codeforces.com 問題 文字列 s が与えられる。 s の 0,2,5,9,14......n 番目 (ns.length()) を取り出した文字列を出力せよ。 考察 0,2,5,9,14......n は階差数列というらしいです。 この階差数列の一般項は n(n+3)/2 になります。 文字列 s の n(n+3)/2 番目…

yukicoder.me 問題 UNOの対戦ログから局面をシミュレーションして、 ・勝った人の番号 ・勝った人が最初に持っていた手札の枚数 を出力せよ。 考察 純粋な実装の問題です。 よって、コードを見ていただいたほうが手っ取り早いです。 コード void solve (Fast…

codeforces.com 問題 最初、Mahmoud が整数 n を持っている。Mahmoud と Ehab は、以下の操作をおこなってから n を相手に渡す。 ・Mahmoud は偶数、Ehab は奇数の数 a (1 この操作をおこなえなかったとき、その人はゲームに負ける。 最終的にこのゲームで勝…

codeforces.com 問題 口座の n 円を 1,5,10,20,100 円ずつ引き出す。 残高を 0 円にするためには、最小で何回引き出せばよいか。 考察 600点（下から2番目の難易度）なのにタグにDPとあり、心構えをして臨んだら制約に n 両替問題なのかコイン問題なのかは、…

codeforces.com 問題 ある会社の社員数 n が与えられる。 この中から i 人選んでチームリーダーとし、残りの n-i 人の社員をそれぞれのチームリーダーに従属させる。 全てのチームリーダーが同じ人数の社員を持てるような i の選び方は何通りあるか。 考察 i…

僕がEclipseでよく使っているショートカットをまとめてみました。 インデントを整理する（Ctrl + i） コードの切り貼りをしてインデントが崩れてしまった場合でも、このショートカットを実行すれば一発でインデントを正すことができます。 コメントアウト（C…

codeforces.com 問題 n=1 のとき、"I hate it" n=2 のとき、"I hate that I love it" n=3 のとき、"I hate that I love that I hate it" と出力する。n が与えられるので、適切な文字列を出力せよ。 考察 n=1,2,3 でループするのかと思っていましたが、実際…

codeforces.com 問題 整数 n に対して、以下の操作を k 回おこなう。 ・n の最後の桁が 0 なら、n を 10 で割る ・そうでないなら、n から 1 を引く k 回の操作が終わったあとの n の値を出力せよ。 考察 「最後の桁が 0 かどうか」を判定するには、さまざま…

codeforces.com 本ブログでは初めてとなる Codeforces の記事です。 問題 n * m の平面に a * a のタイルを詰める。タイルは最低何枚必要か？ 考察 二次元の切り上げ問題です。Double型を使わずに切り上げるやり方は以前に記事に書きましたね。 さっそく使い…

Codeforces で 初ACを獲得するまでの記録です。 登録は Googleアカウント で手早く済ませられるので、省きます。 問題を選択する ProblemSet から問題一覧を見ることができます。 右端のチェックを押すとAC者数順にソートされるみたいなので、今回は一番AC者…

AtCoder Beginner Contest 121 に参加しました。 順位は悲惨なので書きたくないです。 A - White Cells atcoder.jp h行w列を塗りつぶすと、重複して塗られるマスが h*w 個できます。 よって答えは H*W - (h*W+w*H-h*w) です。 B - Can you solve this? atcod…

atcoder.jp 全ての文字列に共通する文字を取り出して、辞書順最小の文字列を合成する問題です。 解説はコードの中に埋め込んだので、そちらをご覧ください。 方針としては、 ・1番目の文字列に含まれる文字を共通文字とする ・2番目以降の文字列について、そ…