勉強予定、あるいは記事にして理解を深める予定の項目のメモです。自分用です。 記事にする予定 ・棒倒し法（迷路） ・自作Scanner ・ローマ数字変換メソッド ・計算量について（logを理解してから） ・少数と誤差 勉強予定（問題、Java文法、アルゴリズム）…

atcoder.jp 相手を殴ったとき、自分の体力と同じだけ相手の体力を減らせるという設定のもと、体力 A を初期値として持つ n 体のモンスターたちが殴り合いをしたとき、最後に生き残ったモンスターの体力の最小値として考えられるものを出力せよ、という問題で…

AtCoder Beginner Contest 118 に参加しました。 結果はAB2完、順位は1807/2881位でした。 A - B +/- A（AC+1WA） B-A を A-B と勘違いしてWA。致命的。今回の反省点の1番目。 B - Foods Loved by Everyone（AC） 赤線で囲った部分の数字の意味が分からず、5…

競プロの問題で入力を受け取る際には、最初に入力の総数を表す n が与えられ、その後にn個の入力が続けて与えられる、というパターンが多いです。この場合は、以下のように書くことで入力を受け取ることができます。 int n = sc.nextInt(); for (int i=0; i

judge.u-aizu.ac.jp 行列が2つ与えられるので、その積となる行列を求めよという問題です。 この問題のために行列同士の積の求め方を習得しましたが、相変わらず行列自体については何もわかっていません。それはともかくとして、いい機会だったので、次に行列…

judge.u-aizu.ac.jp goto文で書かれたC++言語のプログラムを読んで、同じ動作をするプログラムを書け、ただしgoto文は使うな、という問題です。 C++が読めず、goto文もよくわからないので、このプログラムが何をやっているのか全然わかりません。他の方の提…

AIZU ONLINE JUDGE に登録しました。 競プロの参考書『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』と一緒に進めていきたいと思います。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆出版社/メーカー: …

AtCoder の200点問題をすべて解きました。 このくらいの難易度がいまの自分にとってはちょうどいい感じです。300点問題も頑張ります。

解説を見ながらACしたはいいものの、理解が浅く、復習が必要な問題のメモです。自分用です。 200点問題 ・A - Zero-Sum Ranges 累積和、実装、Long 300点問題 ・C - Base -2 Number 二進数 ・C - Pyramid 全探索 DP ・C - 123引き算 ・C - 節制 部分点解法が…

atcoder.jp 正方形の4つの頂点座標のうち、連続した反時計周りの2点が与えられるので、残りの2点を復元せよという問題です。 解説を読んでも全く理解できません。それもそのはず、まともに解こうとしたら回転行列の考え方が必要らしく、回転行列どころか、行…

yukicoder のレベル1問題をすべて解きました。 AtCoder Scores のような難易度別の達成率を表示できるサイトが見つからなかったので、このような大変わかりにくい画像を貼り付けることになってしまいました。 yukicoder のレベル1問題は、AtCoder の100点問…

yukicoder.me 文字列sの中にある最短のチワワ列を探す問題です。 チワワ列とは、 c,w,w がこの順で含まれている文字列と定義付けられています。正規表現で表すと "c.*w.*w" ですね。 調べたところによると計算量 O(N) で解ける方法もあるみたいですが、私に…

yukicoder.me A と B の排他的論理和が C であることがわかっている。A と C が与えられるので B を求めよ、という問題です。 import java.util.*; class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { lon…

yukicoder.me 日付が与えられるので、その二日後の日付を出力する問題です。 import java.text.SimpleDateFormat; import java.util.*; class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.…

yukicoder.me A日～B日の範囲に入っているコンテストには参加できません。したがって、23,24,25日がそれぞれa~bの範囲内にあるかを判定して、範囲内にある日数を3から引いたものが答えです。 import java.util.*; class Main { static Scanner sc = new Scan…

yukicoder.me 与えられた数字にカンマを入れる、というシンプルな問題です。 // import java.util.*; class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { StringBuilder sb = new StringBuilder(sc.next()…

GitHub と yukicoder に登録しました。というより、yukicoder に登録するために GitHub に登録しました。 これからは AtCoder だけでなく yukicoder も頑張っていきます。

atcoder.jp 解説にある「ボタンを押す順序は関係なく、また、各行/列に対して 2 回以上ボタンを押す必要はありません」という部分がイマイチよくわからなかったので、記事を書いて理解を深めることにしました。 といっても、その疑問は以下のような図を描い…

競技プログラミングでは System.out.println() を使って解答を出力しますが、出力回数が数万・数十万回に及ぶような場合、実行時間がかかりすぎてしまうことがあるみたいです。例えば、以下のような問題です。 atcoder.jp この問題では Yes/No の出力を最大…

atcoder.jp ①長さ n の数列が与えられる。この数列の各項には 0,1,2,3,4......n-1 の番号が付けられている ②数列の平均値に最も近い項の、その番号を出力せよ。 解説に「a の平均値を X とします。X は整数となるとは限りませんが、NX は平均値の定義より必…

atcoder.jp みんなのプロコン2019の予選に参加しました。 結果はABC3完、順位は1497/2820位でした。 A - Anti-Adjacency 提出：https://yahoo-procon2019-qual.contest.atcoder.jp/submissions/4206624 nが偶数ならn/2とkを、nが奇数ならn/2+1とkを比較して…

atcoder.jp ①最初、1枚のビスケットと0円を持っている。 ②以下の操作を好きな順にk回おこなったときの、ビスケットの最大値はいくつか。 操作1：ビスケットを1枚得る 操作2：a枚のビスケットを1円に変える 操作3：1円をb枚のビスケットに変える b-a b-a>2の…

atcoder.jp ①長さnの整数列A [A1,A2,A3......An] が与えられる。 ②整数列Aの各項に [-1,0,1] から1つ選んで加算していき、整数列Bを作る。 ③全ての項の積が偶数となるような整数列Bの作り方は、何通りあるか？ 全ての項の積が偶数となるような整数列Bとは、…

atcoder.jp ①数直線上の0の地点にカンガルーがいる。 ②カンガルーは時刻iのとき、負もしくは正の方向へiだけ移動できる。 ③カンガルーが座標xに到着する時刻の最小値を求めよ。 x=16のときを考えてみます。 カンガルーは時刻5以内にxに到着することができま…

atcoder.jp 問題文の理解にずいぶん時間がかかってしまいました。ではその問題文を整理してみたいと思います。 ①半径Rの円を縦にN等分することを考える。 ②その際、N-1本の切断線ができるはずである。これをカットラインと呼ぶ。 ・カットラインに、上から1,…

atcoder.jp まず問題を整理します。 ・青いカードがn枚、赤いカードがm枚ある ・好きな文字列を一つ選ぶ ・選んだ文字列が書かれている青いカードは何枚あるか数える。1枚につき1円を得る ・同様に、選んだ文字列が書かれている赤いカードは何枚あるか数える…

はじめに 競プロで剰余を利用する問題というと、1000000007で割ったあまりを出力せよ、みたいな問題とか、現在からn時間後の時刻を24時間表記で表せ、みたいな問題が思い浮かびますが、今回はそういったものではなく、数列における剰余の周期性についてです…

atcoder.jp 学生の座標n個とチェックポイントの座標m個が与えられ、それぞれの学生をマンハッタン距離で最短のチェックポイントに移動させるときの、そのチェックポイントの番号を出力せよ、という問題です。 200点にしてはずいぶんいやらしい問題……というわ…

AtCoderの100点問題を全て解きました。 一番簡単な難易度とはいえ、コードの書き方に多少の工夫を求められる問題もあり、勉強になりました。 画像の表はAtCoder Scoresというサイトのものです。点数で問題を絞り込んだり、未提出の問題のみ表示したりといっ…

atcoder.jp しばらく考えたのち、座標と座標の間隔を広いほうからn-1個調べ上げることで、それをもとに各コマが移動する区間を決められるのではないか、と発想しました。最初に断っておきますと、大変回りくどいやり方で解いています。スマートな解答は後ほ…