応用情報合格
応用情報ギリギリで合格してました。
参考にした書籍はこちらです。
www.shoeisha.co.jp
基本情報と知識的には被るところも多かったですが、
択一式のテクノロジーが結構わからない単語が多いという印象でした。
過去問の使い回しが多いということも聞きますので、Webサイトのドットコムで対策を重ねた方が近道かもしれません。
xmlファイルはインデントに注意
Tomcatで認証機能の実装をしているところで、
libexec/conf/server.xml
のxmlファイルを設定している。
Realmがデフォルトではコメントアウトされていて、戻す時にインデントがずれてしまって認証がうまくできなかった。
具体的には以下のところ
<Engine name="Catalina" defaultHost="localhost"> <!-- <Realm className="org.apache.catalina.realm.JDBCRealm" driverName="org.gjt.mm.mysql.Driver" connectionURL="jdbc:mysql://localhost/authority" connectionName="test" connectionPassword="test" userTable="users" userNameCol="user_name" userCredCol="user_pass" userRoleTable="user_roles" roleNameCol="role_name" /> --> <!--For clustering, please take a look at documentation at: /docs/cluster-howto.html (simple how to) /docs/config/cluster.html (reference documentation) --> <!-- <Cluster className="org.apache.catalina.ha.tcp.SimpleTcpCluster"/> --> <!-- Use the LockOutRealm to prevent attempts to guess user passwords via a brute-force attack --> <!-- <Realm className="org.apache.catalina.realm.LockOutRealm"> --> <!-- This Realm uses the UserDatabase configured in the global JNDI resources under the key "UserDatabase". Any edits that are performed against this UserDatabase are immediately available for use by the Realm. --> <Realm className="org.apache.catalina.realm.UserDatabaseRealm" resourceName="UserDatabase"/>
Engineから見た時に、2つ分インデントを下げる。
逆元を使って組み合わせの数を求める
AtCoderのABC145、D問題です。
atcoder.jp
組み合わせの数は、nCkで求められます。
ただ、そのまま計算すると、n!/(n-k)!*k!となり、分母、分子ともに数値が大きくなります。
ここでは、modで割ったものを答えとするので、逆元を使って計算量をlog(mod)に抑えつつ、オーバーフローすることを防ぐことができます。
import java.util.*; public class Main{ static Scanner sc = new Scanner(System.in); static long x = sc.nextLong(); static long y = sc.nextLong(); static int t = (int)(x+y)/3; static long MOD = (int)1e9+7; static long[] facts = new long[t+1]; public static void main(String[] args){ facts[0] = 1; for (int i=1; i<t+1; i++){ facts[i] = facts[i-1]*i %MOD; } if ((x+y)%3!=0){ System.out.println(0); return; } long ans = 0; for (int i=0; i<t+1; i++){ int a = i; int b = t-a; if (((a+b*2)!=x) || ((a*2+b)!=y)){ continue; } ans += nck(t, a); ans %= MOD; } System.out.println(ans%MOD); } public static long modpow(long a, long b){ if (b==0) return 1; else if (b==1) return a; long x = modpow(a, b/2); return b%2==0 ? x*x%MOD : x*(x*a%MOD)%MOD; } public static long inv(long n){ return modpow(n, MOD-2); } public static long nck(int n, int k){ return n<k ? 0: facts[n]*(inv(facts[n-k])*inv(facts[k])%MOD)%MOD; } }
組み合わせ数を求めるためのCombinationクラスをライブラリ化したものが以下になります。
public class Combination{ static int n = 7; // 要素数 static long MOD = (long)1e9+7; static long[] facts; public Combination(int n, long MOD){ this.n = n; this.MOD = MOD; facts = new long[n+1]; facts[0] = 1; for (int i=1; i<n+1; i++){ facts[i] = facts[i-1]*i%MOD; } } public static void main(String[] args){ facts = new long[n+1]; facts[0] = 1; for (int i=1; i<n+1; i++){ facts[i] = facts[i-1]*i%MOD; } System.out.println(nck(7,2)); // output 21 } public static long modpow(long a, long b){ // 計算量はlog(MOD); if (b==0) return 1; else if (b==1) return a; long x = modpow(a, b/2); return b%2==0 ? x*x%MOD : x*(x*a%MOD)%MOD; } public static long inv(long n){ // 逆元。x^(-1)≡x^(p-2) (MOD p) return modpow(n, MOD-2); } public static long nck(int n, int k){ return n<k ? 0: facts[n]*(inv(facts[n-k])*inv(facts[k])%MOD)%MOD; } }
Bashによるテキストファイルの読み込みと出力
テキストファイルには、改行でテキストが入力されており、条件に合致した時に、出力させる、というスクリプトを書きます。
テキストファイル(sample.txt)の中身は以下のようになっています。
num 1 num 2 num 3 num 4 num 5 num 6 num 7
#!/bin/bash cnt=0; filename="sample.txt" # ファイル名を変数に入れる cat $filename | while read line || [ -n "${line}" ] # catでファイルを表示。while readで1行ずつ読み込む。 # while readでは改行なしの場合、最終行が読み込まれないため、|| [ -n "${line}" ]を加える。 do cnt=$(($cnt + 1)) # whileループで変数を1ずつ増やす if [ $cnt -eq 5 ]; then # -eqは等号。5行目のみを出力させる。 echo $line fi done
あとは、bash run.shで実行します。出力は以下です。
num 5
深さ優先探索(DFS)を再帰を用いて実装
有向グラフを想定した時の、DFSの使い方を整理しました。
ノード数nが与えられ、次に各ノードの出次数とそれぞれの隣接するノードをk個、入力された時に、どの順序でエッジを辿っていくかを出力するようにしています。
import java.util.Scanner; public class DFS { static Scanner sc = new Scanner(System.in); static int n = sc.nextInt(); static int[][] edge = new int[n][n]; static boolean[] visited = new boolean[n]; static int[] first_v = new int[n]; // 最初に訪れる時刻 static int[] end_v = new int[n]; // 最後に訪れる時刻 static int s = 0; public static void main(String[] args){ for (int i=0; i<n; i++){ int v = sc.nextInt()-1; int k = sc.nextInt(); for (int j=0; j<k; j++){ int u = sc.nextInt()-1; edge[v][u] = 1; } } dfs(0); for (int i=0; i<n; i++){ System.out.println(first_v[i]); } System.out.println(); for (int i=0; i<n; i++){ System.out.println(end_v[i]); } } public static void dfs(int v){ // 再帰によるDFS first_v[v] = ++s; for (int u=0; u<n; u++){ if (edge[v][u]==0) continue; if (!visited[u]){ dfs(u); } } visited[v] = true; end_v[v] = ++s; } }
二分探索のlowerboundとupperboundをライブラリ化
二分探索の、lowerbound(以上)、upperbound(より大きい)が手探り状態だったため、ライブラリ化しました。
public class BinarySearch { public static int lowerbound(int[] arr, int value){ int left = 0; int right = arr.length; while (left<right){ int mid = (left+right)/2; if (arr[mid]<value){ left = mid+1; }else { right = mid; } } return left; } public static int upperbound(int[] arr, int value){ int left = 0; int right = arr.length; while (left<right){ int mid = (left+right)/2; if (arr[mid]<=value){ left = mid+1; }else { right = mid; } } return left; } }
testBinarySearch.javaに配列と変数を代入した時の出力結果を出しています。
OSError: [Errno 48] Address already in useの対処法
Pythonでファイルを実行しようとしたところ、アドレスがすでに使われているというエラーが出た。
調べてみると、プロセスが起動されているので、killしてから実行しなければいけなかった。
lsof -i:5000
lsofコマンドで、現在開いているファイルを一覧表示して、-iオプションでネットワークソケットを指定します。
出力結果は以下です。
COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME agent 534 ----- 4u IPv4 0x50552883b95ae48b 0t0 TCP localhost:commplex-main (LISTEN)
PIDがprocessIDで、以下のようにプロセスをkillすると通常通り実行が可能になります。
kill 534
AtCoderのAGC039-A(300点)
場合分けが適切に行えず、WAを連発。
漏れのあったケースに合わせてif文をたてるものの、結局解決せず。。
Editorialを見て、やっとAC。
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String s = sc.next(); char[] c = s.toCharArray(); long k = sc.nextLong(); long ans = 0; int cnt = 1; for (int i=0; i<s.length()-1; i++){ if (c[i]==c[i+1]) { cnt++; } } if (cnt==s.length()){ System.out.println(((long)s.length()*k)/2); }else { if (c[0]==c[s.length()-1]){ String t = s+s; char[] cc = t.toCharArray(); long tmp = 0; for (int j=0; j<t.length()-1; j++){ if (cc[j]==cc[j+1]){ tmp++; j++; } } for (int j=0; j<s.length()-1; j++){ if (c[j]==c[j+1]){ ans++; j++; } } if (tmp == ans*2){ System.out.println(ans*k); }else { System.out.println(ans+(ans+1)*(k-1)); } }else { for (int i=0; i<s.length()-1; i++){ if (c[i]==c[i+1]){ ans++; i++; } } System.out.println(ans*k); } } } }
結局、必要だった場合分けは、
- if 文字列が全て同じ文字
- else if 文字列の両端が同じ文字
- else 残りの場合(両端が異なる)
両端が同じ場合はさらに以下のように分けられる
- 2つ目の文字列を繋げた時に、indexが0のものを変更することで、単純にcount*k回とはならないもの。
- count*k回となるもの。
まとめ
場合分けの試行は手を動かしてしてみたものの、より複雑な場合分けになってしまって、最後の1~2個のWAが解決しなかった。
1つ1つの場合に合わせて、if文をたてるという苦肉の策に出ないように、ちゃんと法則を見つけて整理した上で、場合分けしなければなと。