【自分用】ターミナルの設定メモ
絶対忘れてしまうので、未来の自分へ覚え書き。
ターミナルアプリを「iTerm2」にして、簡単に呼び出せるようにする
インストールと使い方
Hotkeyで上から降ってくるようにする
Hotokeyには「Caps lock」のダブルタップを割り当てた。
デザインを設定
その他の設定
・Hotkeyでしか開かないようにする
General > 「Only Restore Hotkey Window」
・表示のズレを防ぐ
Profiles > Text > Double-Width Characters > 「Treat ambiguous-width characters as double width」のチェックを外す。
・好みのフォントサイズを追加
・lsした際ファイル属性ごとに色分けする
vimを見やすくするために「powerline」を導入
「vim-plug」をインストール
vimでpowerlineをインストールするためには、
先にvim用のパッケージマネージャ「vim-plug」が必要。
「vim-airline」をインストール
（追記）
設定をコピペする時、自動コメントアウト設定がONになってると、
2行目以降がすべてコメントアウトされるのでOFFにして行うこと！
-----------------------------------------------------------------------------
導入のときの参考リンクにあった「.vimrcへの記述」の追記部分に、
下記2つサイトのおすすめ設定を挟み込んで、保存してから「:PlugInstall」を実行。
背景を透過して使うので、テーマだけは色の濃い「luna」に替えた。
（let g:airline_theme = 'tomorrow' から let g:airline_theme = 'luna' に）
（追記）
設定をそのまま使うと、矢印がこのように崩れたので、
こちらのサイトを参考に設定を変えるとだいぶ増しになった。
・修正前
・修正後
「PowerLine font」のインストール
下記のリンクを参考にして、シェルスクリプトをインストールして実行。
iTerm2 > Preferences > Profiles > Text にて、
「hotkey Window」を選択して、Fontを変更する。
ただし、普段使ってるRictyはその中に含まれていないので、こちらを参照。
これでフォントが「Ricty for Poweline」になった。
SSH接続のときは背景の色を変更
今はまだ設定してない。
AtCoder Beginner Contest 103 を受けた結果
競プロを始めて一ヶ月が経ち、今回で5回目の参加です。
10回受けると実力に近いレートになるらしいので、ようやく折り返し地点ですね。
結果から言うと、今回もB問題までしか解くことができませんでしたが、
今回のC問題はちょっと考えれば解ける問題だったのでかなり悔しかったです…！
A - Task Scheduling Problem
はじめは問題文と出力例を見ても、問題の意味が全く頭に入ってきませんでした。
10分くらい文章と睨めっこしたのち、やっと問題の意味を理解してコーディングに入れました。
要するに、A地点、B地点、C地点が一直線上にあるので、
最短距離ですべて通ってくださいという問題です。
例えば、AからあえてBをスルーしてCに向かい、CからBへと逆戻りするより、
順番にA→B、B→C（もしくはC→B、B→A）と移動する方が無駄がありません。
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] task = new int[3]; task[0] = sc.nextInt(); task[1] = sc.nextInt(); task[2] = sc.nextInt(); Arrays.sort(task); int cost = 0; for (int i = 1; i < 3; i++) { cost += task[i] - task[i - 1]; } System.out.println(cost); } }
ちなみに僕は、A→Bの距離とB→Cの距離の和を求めましたが、
解説では、それなら最初からA→Cの距離を求めるだけでいいよと教えてくれています。
B - String Rotation
文字列の並びを回転操作して、もう一方の文字列と同じにできるかという問題です。
以前違う記事でも書きましたが、僕は数学が全くできないので、
競プロの勉強の一貫として、高校数学の勉強もしています。
先週まで「場合の数」を勉強していたのですが、
今回の問題はまさに円順列の考え方だったので、A問題よりもスムーズに解くことができました。
「あ！ここチャート式でやった問題だ！」
N文字からなる円順列は、回転することで同じになる文字列がN個できます。
なのでN回（文字数）だけ回転操作を行えばよいです。
回転操作は、
①末尾の1文字を先頭に持ってくる。
②末尾の1文字を削除する。
で行うことができます。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder S = new StringBuilder(sc.next()); String T = sc.next(); String ans = "No"; for (int i = 0; i < S.length(); i++) { S.insert(0, S.substring(S.length() - 1)); S.delete(S.length() - 1, S.length()); if (S.toString().equals(T)) { ans = "Yes"; break; } } System.out.println(ans); } }
C - Modulo Summation
ある数を数列の各項で割ったとき、余りの合計は最大でいくつか、という問題です。
割り切れる数、つまり倍数だと余りは0になってしまいます。
なので、ある数というのは各項の最小公倍数より1小さい数のことです。
手順としては、
①最小公倍数を求める。
②「最小公倍数- 1」を数列の各項で割る。
③数列の「各項 - 1」の合計が求められる。
が考えられるので、必死こいて時間いっぱい、手順①の最小公倍数を探し、
結局見つけられないままコンテストは終了してしまいました。
なお、勘の良い人はみなさんお気づきでしょうが、この問題は①②の手順は飛ばして良いのです。
つまり、最初から③の処理を実行するのが正解です。
明後日の方向へ向かっていた
各項の最小公倍数の導き方がどうしても分からない僕は、
「そうだ！手当たり次第、1から順に試していこう！！」
と思ってしまいました。
「最小公倍数 - 1」が分からなくても、
1から順に試していけば、合計の最大値が一番大きかったときが、
それだったんだろうという考えです。
しかし、数列の数Nは全部で3,000個、各項の最大値は100,000、
つまり、計算量は、(3*10^3) * 10^5 = 3 * 10^8
実行に3秒掛かるので、制限時間2秒に間に合いません。
「なるほど！計算を工夫して2秒以内にしろということか！」
（違います）
まず、この方法だと、最小公倍数が「1から100,000」の範囲しか対応できません。
ですが、このときの僕は問題の意図を全力で勘違いしていたので、全く気づいていませんでした。
それで思いついたのが、
数列の各項を割る処理を中心から左右に向かって行う作戦です。
もし6つの要素の配列があったとき、
1番目の要素から6番目の要素まで順番に割っていくと、その操作は6回ですが、
中心にある3番目と4番目の要素からスタートして、
3番目は先頭へ下り、同時に4番目は末尾へ上がれば、その操作は半分の3回で済みます。
これにより、3000だったNを1500に減らすことができ、
(1.5 * 10^3) * 10^5 = 1,5 * 10^8
となり、約1,5秒で実行できるので、制限時間2秒以内を満たすことができます。
実装したけど提出するに満たなかったコード
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) { int N = Integer.parseInt(br.readLine()); String[] line = br.readLine().split(" "); int[] a = Arrays.stream(line).mapToInt(Integer::parseInt).toArray(); long maxSum = 0; int left; int right; for (int i = 1; i <= 100000; i++) { long curSum = 0; if (N % 2 == 0) {// 偶数の場合 left = N / 2 - 1; right = N / 2; } else { // 奇数の場合 int center = N / 2; curSum += i % a[center]; left = N / 2 - 1; right = N / 2 + 1; } for (; left >= 0 && right <= a.length - 1; left--, right++) { curSum += i % a[left]; curSum += i % a[right]; } maxSum = Math.max(maxSum, curSum); } System.out.println(maxSum); } catch (IOException e) { e.printStackTrace(); } } }
先述したとおり、最小公倍数が100,000以下のときしか対応していないので、
入力例3で出力例と違う答えになり、提出していません。
D - Islands War
D - Islands War
たどり着けませんでした。
最後に
相変わらず、C問題の壁を突破することができません。
ただ、今回は計算量を意識して工夫を凝らしてみたりなんかして、
（全くトンチンカンなことだったけれど）
これまでの5回の中では一番、手応えというか、試合になってるように感じられました。
あと、競プロを始めて一ヶ月経ったので、なにか総括的な記事を近いうちに書きたいと思います。
アディオス！
【Javaで】AOJ 「4.5 標準ライブラリのデータ構造」
はじまり
名前が長いのでAOJ本やら螺旋本なんて呼ばれている、
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る
この本で、今日は「スタック」「キュー」「動的な配列」「リスト」を提供する
ライブラリの使い方を勉強していました。
しかし、こちらで紹介されているのはC++の標準ライブラリなので、
Javaで同様のデータ構造を持つクラスの使い方を調べてみました。
参考リンク
スタック
スタックはStackクラスというものが存在しますが、
こちらは推奨されていないようで、Dequeインターフェイスを使用します。
Dequeは両端キューといって、先頭からも末尾からも要素を操作できるので、
後入れ先出し(LIFO)のスタックとして使う場合は、
先頭の要素に対してのみ、追加や削除の操作を行うようにします。
java.util.Deque
java.util.Collectionインターフェースを継承しているので、
要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使用できます。
| 操作 | Stackと同名のメソッド | 対応するメソッド |
|---|---|---|
| スタックに要素を追加 | push(e) | addFirst(e) |
| スタックから要素を削除して取り出す | pop() | removeFirst() |
| スタックから要素を削除せずに取り出す | peek() | peekFirst() |
スタックとして使うときのために、プッシュやポップが用意されていますが、
対応する○○Firstメソッドと全く同じ操作みたいです。
また、要素が何もなかったり満杯だったという理由で、
挿入や追加の操作が失敗した場合には、
「例外をスローする」または「戻り値でnullやfalseを返す」
2つの形式のメソッドがそれぞれの操作に用意されています。
| 操作 | 例外をスロー | 戻り値で特殊な値を返す |
|---|---|---|
| スタックに要素を追加 | push(e) addFirst(e) |
offerFirst(e) |
| スタックから要素を削除して取り出す | pop() removeFirst() |
pollFirst() |
| スタックから要素を削除せずに取り出す | getFirst() | peek() peekFirst() |
Stackと同名のメソッドでいうと、
pushとpopの操作は失敗時に例外をスローしますが、
peekの操作では、例外は発生せずにnullが返ってきます。
ただし、後述のキューの方でもjavadocの説明を引用していますが、
戻り値で特殊な値を返すメソッドは、
「失敗が例外的ではなく通常のことである場合に使用する目的で設計されている」
とのことです。
これはどういうことかと言うと、
Dequeインターフェースの実装クラスは主に可変長なので、
要素の追加では失敗することがまずないそうで、
固定長のクラスで実装して使った場合の為だけに特別に用意されているそうです。
（Dequeの実装クラス4つの中では「LinkedBlockingDeque」だけがこれに該当する。）
だから、実際に使うのは太字のメソッドになると思います。
あと、キューの両端が空かどうかをnullで判定している為、
nullの追加は厳禁らしいです。
使ってみた
スタック | アルゴリズムとデータ構造 | Aizu Online Judge
import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main { public static void main(String[] args) { // Dequeはインターフェースなので、実装クラスのArrayDequeで実装 Deque<Integer> stack = new ArrayDeque<>(); Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int curNum = 0; String curStr = ""; if (sc.hasNextInt()) { curNum = sc.nextInt(); // スタックに追加 stack.push(curNum); } else { curStr = sc.next(); // スタックから要素を削除して取り出し int a = stack.pop(); int b = stack.pop(); switch (curStr) { case "+": stack.push(b + a); break; case "-": stack.push(b - a); break; case "*": stack.push(b * a); break; } } } // スタックから取り出して表示 System.out.println(stack.pop()); } }
キュー
キューは専用のインターフェースが用意されています。
こちらも上記のDequeと同じように、操作失敗時の挙動が異なるメソッドが、
それぞれ2つずつあります。
前述の通り、失敗時にnullやfalseを返す形式のメソッドは、
queueインターフェースを固定長のクラスで実装した場合を想定して設計しているそうです。
固定容量(バウンド)キューが原因で発生する場合のように、offerメソッドは、失敗が例外的ではなく通常のことである場合に使用する目的で設計されています。
───javadoc 「インタフェースQueue」より引用
そのため、固定長のクラスで実装する場合は、
挿入の操作はoffer()メソッドを使うことを推奨されていました。
また、こちらも同じくnullの追加は禁止されています。
キューの先頭の要素を取得するpollメソッドで、要素が存在しないときの戻り値のnullと見分けが付かなくなってしまうからだそうです。
java.util.Queue
同じく、java.util.Collectionインターフェースを継承しているので、
要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使えます。
| 操作 | 例外をスロー | 戻り値で特殊な値を返す |
|---|---|---|
| キューに要素を追加 | add(E e) | offer(E e) |
| キューの先頭の要素を削除して取り出す | remove() | poll() |
| キューの先頭の要素を削除せずに取り出す | element() | peek() |
使ってみた
キュー | アルゴリズムとデータ構造 | Aizu Online Judge
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; public class Main { public static void main(String[] args) { // Queueはインターフェースなので、実装クラスのArrayDequeで実装 Queue<Process> queue = new ArrayDeque<>(); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) { String[] str = br.readLine().split(" "); int n = Integer.parseInt(str[0]); int q = Integer.parseInt(str[1]); for (int i = 0; i < n; i++) { String[] tmp = br.readLine().split(" "); String name = tmp[0]; int time = Integer.parseInt(tmp[1]); // キューに追加 queue.add(new Process(name, time)); } int total = 0; // peek()メソッドは要素がなくても例外をスローせずnullを返す while (queue.peek() != null) { // キューから取り出し Process curPrcs = queue.remove(); int curTime = Math.min(q, curPrcs.time); total += curTime; curPrcs.time -= curTime; if (curPrcs.time > 0) { // キューに追加 queue.add(curPrcs); } else { System.out.println(curPrcs.name + " " + total); } } } catch (IOException e) { e.printStackTrace(); } } } // プロセスの情報 class Process { String name;// プロセス名 int time;// 処理時間 public Process(String name, int time) { this.time = time; this.name = name; } }
動的な配列
JavaにもVectorクラスは存在しますが、
Vectorクラスはかなり古いクラスなので、現在はArrayListを使います。
ただ、Vectorはスレッドセーフなのに対して、ArrayListは同期化されていません。
同期化されていない代わりに、Vectorより高速に動くそうです。
というわけですので、
スレッドセーフにしたい場合は、Vectorクラスを、
同期化が必要ない場合は、ArraysListクラスを使い分けることに……
なるかと思いきや、
Collections.synchronizedList メソッドを使用してラップすることで、
ArraysListも同期化を行えます。
結局の所、動的な配列はArraysListを使うということになるようです。
java.util.ArrayList
ArrayList (Java Platform SE 7)
同じく、java.util.Collectionインターフェースを継承しているので、
要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使えます。
| 操作 | メソッド |
|---|---|
| リストに要素を追加 | add(E e) |
| リストの特定の位置に要素を追加 | add(int index, E element) |
| リストから○番目の要素を取り出す | get(int index) |
| リストの○番目の要素を削除 | remove(int index) |
| リストのすべての要素を削除 | removeAll(Collection c) |
リスト
Javaの双方向連結リストは、LinkedListクラスが用意されています。
java.util.LinkedList
LinkedList (Java Platform SE 8)
太字のメソッドはLinkedListで宣言しているので、
Listインターフェースの実装クラスとして使う場合には、
使用できないので注意。
| 操作 | メソッド |
|---|---|
| リストに要素を追加 | add(E e) |
| リストの先頭に要素を追加 | addFirst(E e) |
| リストの最後に要素を追加 | addLast(E e) |
| リストの特定の位置に要素を追加 | add(int index, E element) |
| リストから○番目の要素を取り出す | get(int index) |
| リストから先頭の要素を削除せずに取り出す | getFirst() |
| リストから末尾の要素を削除せずに取り出す | getLast() |
| リストから先頭の要素を削除して取り出す | removeFirst() |
| リストから末尾の要素を削除して取り出す | removeLast() |
| リストの○番目の要素を削除 | remove(int index) |
| リストのすべての要素を削除 | clear() |
LinkedList と ArrayList
LinkedListはArrayListと同じく、Listインターフェースの実装クラスの1つですが、
ArrayListのjavadocを見ると、addを除くほとんどの処理は、
ArrayListの方がLinkedListよりも速いようなことが書いてあります。
size、isEmpty、get、set、iterator、および listIterator の処理は、一定の時間で実行されます。add の処理も、一定の償却時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。ほとんどの場合、ほかのすべての処理も比例的な時間で実行されます。定数の係数は、LinkedList の実装の場合より小さくなります。
───javadoc 「クラス ArrayList」より引用
LinkedListは双方向連結リストなので、
「4.4 連結リスト」で学んだ通り、ノードと呼ばれる各要素は、
前後のノードと連結することで順番に辿れるようになっています。
それに対し、ArrayListは動的な"配列"です。
各要素にはそれぞれ番号が割り振られています。
配列であれば、例えば1万番目の要素が欲しいと思ったときに、
きちんと1万番目と指定すれば、ピンポイントで要素を取り出すことができますが、
LinkedListの場合、番号は割り振られていませんので、
先頭（または末尾）から1つずつ順番に、1万番目まで辿らなくてはなりません。
そのため、LinkedListでは、
get(i) のような特定の位置の要素を参照する操作は、不向きと言えます。
一方で、リスト内の途中の要素を操作する場合の処理に関しては、
LinkedListに軍配が上がります。
それは、ArrayListではそれぞれの要素に番号が割り振られてるが為に、
リストの途中に要素を追加されると、
それ移行の要素の番号を全てずらしてやる必要があるからです。
もし、1万件の要素のうち"先頭の要素だけ"を削除した場合でも、
後続の9999個の要素にも変更を加えなければなりません。
双方向リストであれば、リストの途中に要素を加えても、
修正を加えるのは、その前後2つのノードだけで済みます。
使ってみた
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Iterator; import java.util.LinkedList; public class Main { public static void main(String[] args) { // LinkedList型としてインスタンス化 LinkedList<Integer> list = new LinkedList<>(); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) { int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { String[] cmd = br.readLine().split(" "); switch (cmd[0]) { case "insert": // リストの先頭に追加 list.addFirst(Integer.parseInt(cmd[1])); break; case "delete": // parseIntの戻り値はint型である為、 // そのまま渡すとremove(int index)が呼び出されてしまう。 // 明示的にInteger型に変換することで、 // remove(Object o)メソッドを呼び出す。 list.remove((Integer) Integer.parseInt(cmd[1])); break; case "deleteFirst": // 先頭の要素を削除 list.removeFirst(); break; case "deleteLast": // 末尾の要素を削除 list.removeLast(); break; } } StringBuilder sb = new StringBuilder(); // Iteratorを使って先頭の要素から順番に辿っていく for (Iterator<Integer> it = list.listIterator(); it.hasNext();) { sb.append(it.next()); if (it.hasNext()) { sb.append(" "); } } System.out.println(sb); } catch (Exception e) { e.printStackTrace(); } } }
AtCoder Beginner Contest 007 C - 幅優先探索
昨日は、解法に感心した問題をブログに書きましたが、
今日は、解説を見ても解けなかった問題を記しておきます。
解くことのできなかった問題は、
カテゴリー「負債」につっこんで、残しておくことにしました。
あとで見返して解くことができた時に、晴れてこの記事は「負債」から取り除かれます。
そして、未来の自分に宛ててるので、少し言葉遣いが雑になります。
AtCoder Beginner Contest 007 C - 幅優先探索
C - 幅優先探索
問題文があまりに長いので、引用しないからリンク先参照。
考え方
AtCoder Beginner Contest 007 解説
解説にもある通り、問題文で紹介されていた「幅優先探索」の手法をそのまま実装。
最大50マス×50マスになる迷路を、char型の二次配列[y座標][x座標]で初期化し、
それぞれの要素には、壁を表す'#'と、空きを表す'.'のどちらかが入っている。
上下左右のマスが空きマスかどうかを判定するために、
「y座標、x座標、手数」のメンバーを持つCellクラスを用意し、
Cellクラス型の一次配列でキューを作成。
キューには最初に、スタート地点の座標を持つ1つだけが格納されていて、
ゴールを見つけるまで以下のループを繰り返す。
1. popメソッドでキューの先頭のCellクラスを取り出す。
2. 取り出したCellクラスの(y , x)座標を使用して、上下左右のマスが空きマスかどうかを判定。
3. 空きマスだった場合は、そのマスの座標を持つCellクラスをキューの末尾に追加。
4. 次回以降の検索で、再びこのマスに逆戻りしないよう、現在のマスを'#'（壁マス）に変更。
提出したソースコード
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int head = 0; // キューの先頭 static int tail = 0; // キューの末尾 static Cell[] queue = new Cell[255]; public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) { // 行と列の値の受け取り String[] RC = br.readLine().split(" "); int R = Integer.parseInt(RC[0]); int C = Integer.parseInt(RC[1]); // スタートマスの座標の受け取り String[] sysx = br.readLine().split(" "); int sy = Integer.parseInt(sysx[0]) - 1; // 配列は0オリジンなのでそれぞれ-1 int sx = Integer.parseInt(sysx[1]) - 1; // ゴールマスの座標の受け取り String[] gygx = br.readLine().split(" "); int gy = Integer.parseInt(gygx[0]) - 1; int gx = Integer.parseInt(gygx[1]) - 1; // 迷路の内容を二次配列で保管 char[][] labyrinth = new char[R][C]; for (int i = 0; i < R; i++) { String cell = br.readLine(); for (int j = 0; j < C; j++) { labyrinth[i][j] = cell.charAt(j); } } // 上下左右のマスが、空きマスか壁マスかを判定 push(sy, sx, 0); boolean hasGoaled = false; int ans = -1; while (!hasGoaled) { Cell cur = pop(); // ゴールマスを見つけられたら抜ける if (cur.y == gy && cur.x == gx) { ans = cur.cnt; hasGoaled = true; } // 上 if (labyrinth[cur.y - 1][cur.x] == '.') { push(cur.y - 1, cur.x, cur.cnt + 1); } // 下 if (labyrinth[cur.y + 1][cur.x] == '.') { push(cur.y + 1, cur.x, cur.cnt + 1); } // 左 if (labyrinth[cur.y][cur.x - 1] == '.') { push(cur.y, cur.x - 1, cur.cnt + 1); } // 右 if (labyrinth[cur.y][cur.x + 1] == '.') { push(cur.y, cur.x + 1, cur.cnt + 1); } // 現在のマスは、逆戻りしないように壁マスにしてしまう labyrinth[cur.y][cur.x] = '#'; } System.out.println(ans); } catch (IOException e) { e.printStackTrace(); } } static void push(int y, int x, int cnt) { if ((tail + 1) % queue.length != head) { queue[tail] = new Cell(y, x, cnt); tail = (tail + 1) % queue.length; } else { System.err.println("キューが満タンです"); } } static Cell pop() { Cell ret; if (head != tail) { ret = queue[head]; head = (head + 1) % queue.length; } else { System.err.println("キューが空っぽです"); ret = null; } return ret; } } class Cell { int y; // y座標 int x; // x座標 int cnt; // 手数 public Cell(int y, int x, int cnt) { this.y = y; this.x = x; this.cnt = cnt; } }
実行結果
入力例1,2のような小さな迷路は「AC」になるが、
入力例3のように広い迷路の場合、すぐにキューが満杯になってしまい「WA」になる。
なお、キューの大きさをヤケクソで「10^6」くらいにしても満杯になるし、その場合は「TLE」に変わる。
（キューはリング上にしているので、本当に中身が満タンになっている）
要するに、とんでもない量のオーダーとなってしまう……
おそらく、同じマスを色んなルートから通ることができるので、
単純に50 * 50 の容量じゃキューは足りないのだと思う。
とはいえ、実行するごとに、
空きマスは壁マスに変更されて減っていくため、サイズを10^6に取っても満杯になるのは、
そもそも引数とか変数の設定にミスがあるのかも？
AtCoder Beginner Contest 006 C - スフィンクスのなぞなぞ
解説を見て、なるほど！と感心したので記しておきます。
C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder
自分で解いたとき
まず、この問題を見たとき、
「AtCoder Beginners Selection」の「ABC085C - Otoshidama」を思い出しました。
こちらは、価格の違うお札が3種類あり、そのお札をトータルでN枚使って、ぴったりY円にできるかという問題です。
僕が最初に解いたときは、まんまと3重for文で「TLE」を食らってしまいましたが、
実は、最後のお札の枚数は、前の2種類のお札の枚数が決まると、自動的に1つに決まるので調べる必要がなかったのです。
そして、今回の問題も、
脚の本数が異なる3種類の人間がいて、その合計人数N人で、ぴったりM本にできるか、
という問題だったので、「ABC085C - Otoshidama」と同じように解けると考えました。
提出したソースコード
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); // 大人の足のループ変数 for (int i = 0; i <= n; i++) { // 老人の足のループ変数 for (int j = 0; j <= n - i; j++) { int k = n - i - j; // 赤ちゃんの足 if (2 * i + 3 * j + 4 * k == m) { System.out.println(i + " " + j + " " + k); System.exit(0); } } } System.out.println("-1 -1 -1"); } }
結局これで「TLE」をもらってしまうのですが、
上記の「ABC085C - Otoshidama」と違うのは、制約のNの量です！
「ABC085C - Otoshidama」で入力で受け取る枚数Nは、最大 2000 でしたが、
今回の「C - スフィンクスのなぞなぞ」では、最大で 10^5 受け取ります。
同じように二重for文で実行した場合、そのループ回数は最大で、
・「ABC085C - Otoshidama」：2,000^2 = 4,000,000回（4 * 10^6）
・「C - スフィンクスのなぞなぞ」：100,000^2 = 10,000,000,000回（10^10）
となります。
ここで、
1 秒間で処理できる for 文ループの回数は、10^8 = 100,000,000 回程度
ということから、今回の問題は「ABC085C - Otoshidama」とは
同じ方法では解けないということが分かりますね。
qiita.com
（1秒間に処理できるループの回数のお話はこちら。）
ではどう解くのか？
前述の通り、今回与えられる入力値は「10^5」と大きな値であるため、
オーダーがN^2になることは許されません。
「解説」によると、この問題の解法には、
・つるかめ算を使う
・老人の数を固定する
の2パターンあるみたいです。
どちらもオーダーがNで済むように工夫されています。
そして、僕が個人的に感動したのは、後者の「老人の数の固定」です。
つるかめ算
恥ずかしながら、つるかめ算は名前しか知らなかったので、
さっきググって覚えました。
www.manabinoba.com
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); // 老人（3本足）の足 for (int i = 0; i <= n && m >= i * 3; i++) { int j = 0; // 2本足の数 int k = 0; // 4本足の数 // つるかめ算 // 残りすべてが2本足の場合の、足の総数を数える int needLegs = m - i * 3; int numJ = 2 * (n - i); if (numJ >= needLegs) {// 本数が上回った場合 int over = numJ - needLegs; if (over % 2 == 0) { k = over / 2; j = (numJ / 2) - k; } else { // 奇数なら2本足と4本足で賄えないので飛ばす continue; } } else if (numJ < needLegs) {// 本数が足りない場合 int more = needLegs - numJ; if (more % 2 == 0) { k = more / 2; j = (numJ / 2) - k; } else { continue; } } if (3 * i + 2 * j + 4 * k == m && j >= 0 && k >= 0) { // 出力する順は、大人(j)→老人(i)→赤ちゃん(k) System.out.println(j + " " + i + " " + k); System.exit(0); } } System.out.println("-1 -1 -1"); } }
つるかめ算を使うことで、
老人の人数を決めたときに、大人と赤ちゃんの人数も決められるので、
必要な計算量は、老人が0人からN人までの計N+1回だけで済みました。
老人の数の固定
2本足の大人、3本足の老人、4本足の赤ちゃんがいたとき、
老人2人は計6本、大人と赤ちゃん一人ずつの2人組も計6本となります。
人数がどちらも2人で変わらず、足の本数も変わらないので、
2人の老人は、すべて大人と赤ちゃんのペアによって置き換えることができます。
例）老人50人は、大人25人と赤ちゃん25人で置き換えられる。
例）老人11人のうち10人は、大人5人と赤ちゃん5人で置き換えられる。
よって、調べる老人の人数というのは、
0人の場合と、1人の場合の2パターンしかないのです！
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); // 老人2人=6本足、大人1人赤ちゃん1人の計2人=6本足 // 人数と足の本数が変わらないので、老人は0と1人のケースだけ調べれば良い for (int a = 0; a <= 1; a++) { for (int b = 0; b <= n - a; b++) { int c = n - a - b; if (3 * a + 2 * b + 4 * c == m) { System.out.println(b + " " + a + " " + c); System.exit(0); } } } System.out.println("-1 -1 -1"); } }
外側のループで、老人を0から1人までの2通り調べ、
内側のループで、大人の数を0からNまで調べます。
赤ちゃんの人数は「ABC085C - Otoshidama」と同じく、残った人数から自動的に決まります。
すると、オーダーは2*(N+1)となるので、10^8の範囲に収まります。
こういった、ひらめきや工夫で計算量を減らすタイプの解説を見ると、
「おわぁ〜〜！なるほどぉ〜〜！！！！！」ってすごく感心させられます。
この考え方を知っていれば、
もし今後、4本足、5本足、7本足の得体の知れない生き物が現れたときなんかに、
5本足が3匹は、4本足が2匹と7本足が1匹の計3匹で、同じように補えるので、
5本足は0匹、1匹、2匹の3パターンだけ調べれば良いことが分かりますね。
忘れないうちに、そんな問題お待ちしてます。
AtCoder Beginner Contest 101 にリベンジしてきた話
始まり
事の発端は先週に遡り、
今日は記念すべき100回目のBeginner Contest、AtCoder Beginner Contest 100なので、ぜひぜひ参加してみてくださいな！
— chokudai(高橋 直大) (@chokudai) June 16, 2018
Hello Worldが出力出来れば参加してみておっけーなレベルだよ！！！https://t.co/bCiCjMD2hT
こちらのツイートを見かけて、せっかくなのでABC100に参加してみました。
コンテスト自体は、実はプログラミングを始めてから、
過去に3回ほど受けたことがあり、
そのときはB問題までは解けるけど、C問題は厳しいくらいの感じでした。
そして、参加直後のツイートがこちら。
遅れてABC参加してみたけど一問目から分からなくてワロタｗｗ……ワロタ……
— わろさん (@a2606_sp) June 16, 2018
１時間半かけてA問題が解けないままコンテスト終了したなう。
— わろさん (@a2606_sp) June 16, 2018
0点でした。
言い訳をすると、A問題の内容を勘違いしてたというのもありますが、
何よりケーキの取り方のアルゴリズムがなかなか思い付けず……。
さすがにこの結果は悔しかったので、
ちゃんとプログラミングコンテストに取り組んでみようと思ったのでした……。
課題とやるべきこと
まず、AtCoderの勉強方法で調べたところ、
初心者向けにおすすめされていた、
・「過去問精選10問」を解いてみる
・「アルゴリズム」の勉強をする
をやってみました。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (7件) を見る
「アルゴリズム」の勉強に関しては、
評判の良かった「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」
という参考書を使用してます。
まだ読み始めて5日ですが、
理解するのに少し時間はかかるものの、結構楽しく進められてます。
ただ、これらの勉強をしていて、
新たな弱点が浮き彫りになりました。
僕はそもそも数学ができませんでした。
高校時代はもっぱら赤点で、受験もしてこなかったので、
上記の参考書の解説を読んでも、理解できないところが出てきます。
（例）
参考書「1 + 2 + … N-1 = ( N^2 -N ) / 2 と、なり」
ぼく「なんで？」
参考書「オーダーがO( √n )、O(logn)、」
ぼく「log？」
なので今は、プロコンの勉強をする前に、
一日45分くらい、数学の勉強をする時間を設けています。
とりあえず、コンテストに関係ありそうな「場合の数」から始め、
今日は「順列」を覚えました。
異なるN個のものからR個取り出せるようになったので、
恥ずかしながら、かなり役立ってます。
リベンジしてみた
一週間の修行期間を経て、かなりモチベの高い状態で当日を迎えました。
AtCoder Beginner Contest 101 - AtCoder
かなりモチベの高い様子↓
前回のABCではA問題すら解けずに0点に終わったから、今日はリベンジに燃えているぜ……！
— わろさん (@a2606_sp) June 23, 2018
今の俺は地獄のアルゴリズムサイボーグさ……
— わろさん (@a2606_sp) June 23, 2018
A問題
与えられた4つの記号で、インクリメント、またはデクリメントするだけだったので、
これはスムーズに解けました。
B問題
B問題では、まさに修行の成果が発揮できました！
与えられた整数Nの各桁の和を求めて、
Nをその和で割り切れるかという問題だったのですが、
各桁の和の求め方は、
AtCoder Beginners Selection - AtCoder
の第5問「ABC083B - Some Sums」でやっていたのです。
10で割った余りで、一の位の桁が取得できるということに、感心していたのでよく覚えています。
そのときは、まさに「あ！これ進研ゼミでやった問題だ！」みたいな感覚でした。
B問題もスムーズに解いて、ジャッジの経過も待たずに、駆け足でC問題へ移りました。
C問題
難しかったです。
1,2,…,Nを並び替えた数列から、k個の連続した要素を取り出して、
その中の最小値ですべて上書きする操作を繰り返し、
すべての値を等しくしたい。
その必要な操作の回数の最小値を求めよ、という問題でした。
そのとき考えていたのは、
最初に、配列の先頭から、k個の連続した要素のグループを操作する。
次に、そのグループの最後の要素を先頭にしたグループを作り操作をかけ、
それを末尾まで繰り返すという方法でした。
ただ、この処理だと、最後の1回でK個の要素を取ろうとしたときに、
配列の末尾を超えて、配列エラーが起きてしまう可能性と、
要素の先頭からK個以内に、数列全体の最小値がないといけないことに注意しないといけません。
試行錯誤の末、試験終了1分切ったタイミングで、
ギリギリ完成して、テストする間もなく滑り込ませて提出しました。
これが実際のコードです。
一つの提出で「AC」「WA」「TLE」「RE」すべて網羅しました。
最小値を先頭に持ってきたかったので一旦ソートしましたが、
それだけならすべての要素をソートする必要ありませんでしたね……。
D問題
たどり着けませんでした。
結果
C問題は解けなかったものの、A問題とB問題は解けたので、
一問も解けなかった前回に比べたら大躍進ではないでしょうか。
って、あれ？
提出結果を見たらB問題が「WA」になってる！！！？
B問題は知ってる問題だったので、早くに答えてC問題へ進んでいましたが、
C問題を試験ギリギリまで提出していなかったので、
B問題のジャッジの結果を一度も確認していなかったのです……！
ちなみにコンテスト終了後のツイートです。
おあぁ…おあぁぁ……
— わろさん (@a2606_sp) June 23, 2018
B問題がWAになってることに気づかずC問題やってた……
— わろさん (@a2606_sp) June 23, 2018
ふえぇぇ〜……
— わろさん (@a2606_sp) June 23, 2018
【成績】
100 / 1000点
1586 / 1664 位
終わりに
今回もまた、残念な結果に終わってしまいました。
ただ、もちろんプログラミングコンテストはこれからも続けてみます。
現段階の目標は、「C問題まで解けるようになる」です。
それでは。
はてなブログを開設してみた
みんなやってるから僕もやるくらいの気持ちで開設してみました。
主にプログラミング関係の記事を書くつもりです。
Qiitaとかに投稿するほどじゃない知見を、あとで思い出せるように備忘録代わりに使ったりしようかなと思ってます。
あと、文章を書くのが苦手すぎるので、その練習も兼ねています。
この4行を書くのに10分かかってるレベルです。
