Codeforce #384 Div2 A~C
問題
codeforces.com
・Hackされた
考察
・0か1しかない。
・なので、AとBが同じcompanyを示すなら0,そうでない場合は0と1は必ず隣接するため1になる
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class A { int N,A,B; String s; public void solve() { N = nextInt(); A = nextInt() - 1; B = nextInt() - 1; s = next(); if(s.charAt(A) == s.charAt(B)){ out.println(0); }else{ out.println(1); } } public static void main(String[] args) { out.flush(); new A().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
考察
・愚直にstepごとに数列を書きなぐってみると同一の数字ごとに一定の間隔で現れることがなんとなくわかった。
・あとは1からNまでの数値を試していき、Kがその間隔にマッチするかをみていく
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class B { int N; long K; public void solve() { N = nextInt(); K = nextLong(); if(K % 2 == 1){ out.println(1); return; } for(int i = 1;i < N;i++){ long a = K - ((1L << i)); long b = (1L << (i + 1)); if(a % b == 0){ out.println(i + 1); break; } } } public static void main(String[] args) { out.flush(); new B().solve(); out.close(); } }
考察
・
・
・
・
・
・
・
やっとこどふぉのC理解した気がする。
— tookunn (@tookunn_1213) 2016年12月15日
2/n = 1/n + 1/n , 1/n = 1/x = 1/y + 1/z , ってことは1/yは1/nより小さいから仮に1/y = 1/(n+1)とすると1/z = 1/n(n+1)になるってことか
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class C { int N; public void solve() { N = nextInt(); if(N == 1){ out.println(-1); return; } long x = N; long y = N + 1; long z = (long)N * (N + 1); out.println(x + " " + y + " " + z); } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } }
Codingame Fantastic Bitsに参加
Codingameというサイトで行われた「Fantastic Bits」というコンテストに参加しました。
今回、事実上初めて長期間コンテストに出た && これから長期間コンテストに出始めようかなと思った ので参加した内容を記録した方が良いと思い、軽く記事にします。
ちなみに提出コードは可読性も良くないし、現状バグも多くあったりするので公開はしてないです。
このコンテストは8日間の間行われたので、覚えている限り、適当に書いていきます。
1日目
・コンテストが開始されたが、開始時刻が日本時間の26:00だったので開始直後には参加せず。
・昼間ぐらいからやっと参加できる状態になったので、最初にざっと問題文を眺める。
・初めての長期間コンテストの参加でノウハウが分からずだったので、とりあえず問題文の量に圧倒されながら翻訳しつつ、概要をgoogle documentにまとめていく。
・ふわっと概要を把握後、まず移動処理ではthrustをMAXで2体のWizard各々の一番近いSnaffleを追いかけるようにして、投げる処理ではGoalの中心座標(x,y) = (0 or 16000, 3750)に投げるようにして提出。
・提出したらWood League1に昇格した。
2日目
・このリーグからBludgerというお邪魔要素が追加された。
・Last Battlesをずっと眺めていたら、自分の2体のWizardが同じSnaffleを追いかけてWizard同士が衝突していたのを発見してよろしくないなと思った。
・なので、同じSnaffleを追いかけないように、同じSnaffleを選んでしまった場合Snaffleとの距離が短い方を優先して、距離が長い方は2番目に近いSnaffleを追いかけるようにした。
・その時点で提出したらBronze Leagueに昇格した。なおBludgerに対する処理はほとんど書かず...。
3日目
・このリーグからは4つの魔法が使えるようになった。
・概要を眺めた感じ、SnaffleをWizardに引き寄せる"ACCIO"という魔法が良さそうだったので、これを使おうと決意。
・使いどころはいずれかの敵WizardがSnaffleを掴んでいたら(正確には敵WizardとSnaffle間の距離がSnaffleを掴んでいると思われる距離の場合)"ACCIO"を使う という風にした。
・そして、提出してSilver Leagueに昇格
4日目 ～ 7日目
・ここからは色々「これ入れたら強そう(こなみ)」みたいな動きを入れてみて、League Bossと戦わせて余裕で勝てるまで実験して、考え直して、実験して...を繰り返して過ごす。
・あと上位勢のAIの動きを見て、なんでこんな細かい動きが出来たり、まっすぐ"FLIPENDO"でGoalにSnaffleを入れたりできるんだろうと思いつつ、考えて終わった
・そして7日目に提出してないが、Gold Leagueに昇格してた。
8日目
・頑張ってTシャツもらえる可能性がある250位圏内に入りたかったので、色々悪あがきをしたり、無駄にSubmitして順位を下げたりしてコンテスト最終日を満喫
・そして、コンテスト終了。
・Gold League内では 450ぐらい / 558人中、 全体順位は602位でした。Tシャツ圏内はさすがに難しかった。
全体の感想
・長期間コンテストに初参加だったので分からないことも多った。しかし、いつもやっている短時間のコンテストと違って気持ちの切り替えが何回も出来たりして精神衛生上かなり良くてあんまり途中で投げ出すことが少なかったのが個人的にはOK
・基本if文の処理が多くて,探索らしい探索処理は書いた覚えがないので、他の強い人はちゃんと探索処理とか書いているのかなと思った。
・今回の順位は全体の参加者の半数以上よりは良かったはずなので、よくやったと思いたい。
・シュミレータを作っている日本人参加者を観測して,自分も作ろうかと思ったけど簡単そうではなかったのでやめた。(そのうち他のコンテストで自作シュミレータが必要になる時が来そう)
・CodingameのコンテストはゲームAIのコンテストっぽいのでマラソンマッチ系の導入としては良さそうだった。（ちゃんとゲーム画面がVisualizeされていて試合風景を見るだけでも楽しかった）
yukicoder No443 GCD of Permutation
考察
まず愚直に整数の各桁を並べ替えて出来る整数の集合
を列挙することは制約から無理ということが分かる。
ここから公式解説の解法について考える(自分に向けての補足)
Sに含まれる整数"xxxxab"と"xxxxba"(である)を考える。この時、この2つの値の差は
になる。
このというのは
例えば、"12ab","12ba"という2つの整数があるとすると上2桁の数値は意識しないで良くて,
"ab" - "ba"を考えるとになる。
つまり、とすると先程の式は
になり
という風に考えることができる。
今回求める最大公約数は
の約数であると考えられる。
@tookunn_1213 ということは a > bと考えると(xxxxab - xxxxba)の差9(a - b)はxxxxabとxxxxbaの最大公約数の倍数になる ということか
— tookunn (@tookunn_1213) 2016年11月12日
考えられるのすべての組み合わせの最大公約数と
の最大公約数を求めると今回求めるべき最大公約数Gとなる。
ソースコード
def gcd(x,y): return x if y == 0 else gcd(y,x%y) N = input() n = int(N) s = set(map(int,list(N))) if len(s) == 1: print(N) else: G = 0 for i in s: for j in s: if i < j: if G == 0: G = 9 * (j - i) else: G = gcd(G,9 * (j - i)) div = set() i = 1 while i * i <= G: if G % i == 0: div.add(i) div.add(G//i) i+=1 div = list(div) div.sort() div.reverse() for d in div: if n % d == 0: print(d) break
POJ 1328 Radar Installation
問題
蟻本の練習問題埋めの一環として取り組んだ。
制約書いてないのがあったりして混乱したので解説記事をみて通した。
幾何的要素が若干あったので、色々理解するのに時間がかかった。
考察
レーダーの適用範囲を円とし、その円の中心をレーダーの座標位置とする。
島からレーダーの座標位置までの最大距離はDなので、レーダーの座標位置は(島の座標位置) =
とすると
になる。(三平方の定理から)
島の座標位置の中にを満たすものがある場合は必ずレーダーの適用範囲外になる
座標の値を昇順に島の座標位置をソートする。
ソート後の島を見ていき、出来るだけ一つのレーダーの適用範囲内に多く島の座標位置が内包するようにレーダーの座標位置を調節していく。
参考：
Radar Installation | Algorithm Notes
POJ 1328 Radar Installation greedy
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { int N,D; P[] points; private class P implements Comparable<P>{ int x,y; public P(int x,int y){ this.x = x; this.y = y; } public int compareTo(P p){ if(this.x == p.x){ return this.y - p.y; } return this.x - p.x; } } public boolean check(){ for(int i = 0;i < N;i++){ if(points[i].y > D){ return false; } } return true; } public void solve() { int cnt = 1; while(true){ N = nextInt(); D = nextInt(); if(N + D == 0)break; points = new P[N]; for(int i = 0;i < N;i++){ int x = nextInt(); int y = nextInt(); points[i] = new P(x,y); } Arrays.sort(points); int ans = 1; //y > Dをチェック if(!check()){ out.println("Case " + cnt + ": " + "-1"); }else{ double X = points[0].x; double Y = points[0].y; //現在のレーダーの座標位置 double radarX = X + Math.sqrt(D * D - Y * Y); for(int i = 1;i < N;i++){ int x = points[i].x; int y = points[i].y; //最低でもpointLeftにレーダーを設置すれば島iを適用範囲に内包可能 double pointLeft = x - Math.sqrt(D * D - y * y); //現在のレーダーの座標位置から島iを適用範囲内に設置できるか if(pointLeft > radarX){ X = points[i].x; Y = points[i].y; //現在のレーダーの座標位置を更新 radarX = X + Math.sqrt(D * D - Y * Y); ans++; }else{ //出来るだけxを値を小さくしないとpoints[i].x < points[i + 1].x && points[i].y < points[i + 1].yのケースで落ちる radarX = Math.min(radarX, x + Math.sqrt(D * D - y * y)); } } out.println("Case " + cnt + ": " + ans); } cnt++; } } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
CODE FESTIVAL 2016 qual B D
考察
本番中は貪欲っぽいな思って、色々考察して試して時間切れを迎えた。
どういう発想で解法に近づくのかを記録しておく。
・問題概要から数列Aのある要素はその要素の前の要素によって操作が変わる？だから前から走査していく？
・DPにするにしても遷移が決まっているので違う？じゃあ貪欲？
・なので単純に前の要素から貪欲に走査してみる。
・まず最初の要素から最大の操作回数を得るにはA[0] - 1回の操作を行う必要がある。
・次の2番目の要素では最初の要素は1になっているはずなので、Pを1にすることはできない。なので、P=2で引いていくことにしてみる。
・もし2番目の要素がP以下だったら引くことができない(0になるため)。P = A[i]の場合、次の要素からはP =A[i] + 1にしていかないと2番目の要素で所持金が0になるまで買ってしまう。
・Pより大きかったら1以上P以下になるまで引いてみる。
・これを最後の要素までやっていく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { int N; int[] A; public void solve() { N = nextInt(); A = new int[N]; for(int i = 0;i < N;i++){ A[i] = nextInt(); } long max = 1L; long ans = (A[0] - 1);//最初の要素を1にし、A[0] - 1をカウント for(int i = 1;i < N;i++){ if(A[i] > max + 1){ //A[i] - 1は1は残さないといけないため //1以上を残してmax+1ずつ減らしていく ans += (A[i] - 1) / (max + 1); }else if(A[i] == max + 1){ //A[i]はmax+1で減らすと0になってしまうので、スルー //次の要素からはmax = A[i] + 1にしないといけない max++; } } out.println(ans); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
どうせまた解き直す時、この問題の発想忘れてるんだろうな～
Codeforces AIM Tech Round Div2 C
考察
入力としてどの頂点がどの頂点つながっているかを与えられる。
頂点xと頂点yがつながっているということは頂点xと頂点yに対応する文字が隣接しているということ。
逆に頂点xと頂点yがつながっていないということは必ずその2つの頂点に対応する文字が'a'と'c',または'c'と'a'ということ。
なので、つながっていない頂点同士にそれぞれ'a'か'c'を当てはめて,それ以外の頂点には'b'を当てはめて,最終的に「頂点同士がつながっていないのに文字は隣接している場合」と
「頂点同士はつながっているのに,それぞれの文字が'a'と'c'の場合」はNoであり,それ以外の場合はYesと出力すればよい。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.*; public class Main { int N,M; int[] kind; boolean[][] connect; public void solve(){ N = nextInt(); M = nextInt(); connect = new boolean[N][N]; for(int i = 0;i < M;i++){ int u = nextInt() - 1; int v = nextInt() - 1; connect[u][v] = connect[v][u] = true; } kind = new int[N]; Arrays.fill(kind,1); for(int i = 0;i < N;i++){ for(int j = i + 1;j < N;j++){ if(!connect[i][j]){ if(kind[i] == 1){ kind[i] = 0; kind[j] = 2; }else if(kind[i] == 0){ kind[j] = 2; }else{ kind[j] = 0; } } } } for(int i = 0;i < N;i++){ for(int j = i + 1;j < N;j++){ if(!connect[i][j] && Math.abs(kind[i] - kind[j]) <= 1){ out.println("No"); return; } if(connect[i][j] && Math.abs(kind[i] - kind[j]) >= 2){ out.println("No"); return ; } } } out.println("Yes"); for(int i = 0;i < N;i++){ out.print((char)(kind[i] + 'a')); } out.println(); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
Codeforces #348 Div2 C
考察
問題を誤読していて,サンプルが合わなくて辛かった。
僕が行った解法としては愚直に与えらたクエリを実行して,指定された行,列の中の要素をシフトし,与えられた値を格納していく。
そして、すべてのクエリを実行し終わったら,逆からクエリをもう一度読み込んで,操作3の場合は何もせず,操作1の場合は右にシフト,操作2の場合は下にシフトしていく。
そうすると求めるべき解を得られる。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.*; public class Main { int N,M,Q; int[] t,r,c,x; int[][] table; public void shiftLeftRow(int n){ int tmp = table[n][0]; for(int i = 1;i < M;i++){ table[n][i - 1] = table[n][i]; } table[n][M - 1] = tmp; } public void shiftRightRow(int n){ int tmp = table[n][M - 1]; for(int i = M - 1;i >= 1;i--){ table[n][i] = table[n][i - 1]; } table[n][0] = tmp; } public void shiftTopColumn(int n){ int tmp = table[0][n]; for(int i = 1;i < N;i++){ table[i - 1][n] = table[i][n]; } table[N - 1][n] = tmp; } public void shiftBottomColumn(int n){ int tmp = table[N - 1][n]; for(int i = N - 1;i >= 1;i--){ table[i][n] = table[i - 1][n]; } table[0][n] = tmp; } public void solve(){ N = nextInt(); M = nextInt(); Q = nextInt(); table = new int[N][M]; t = new int[Q]; r = new int[Q]; c = new int[Q]; x = new int[Q]; for(int i= 0;i < Q;i++){ t[i] = nextInt(); if(t[i] == 1){ r[i] = nextInt() - 1; shiftLeftRow(r[i]); }else if(t[i] == 2){ c[i] = nextInt() - 1; shiftTopColumn(c[i]); }else{ r[i] = nextInt() - 1; c[i] = nextInt() - 1; x[i] = nextInt(); table[r[i]][c[i]] = x[i]; } } for(int i = Q - 1;i >= 0;i--){ if(t[i] == 3)continue; if(t[i] == 1){ shiftRightRow(r[i]); }else{ shiftBottomColumn(c[i]); } } for(int i = 0;i < N;i++){ for(int j = 0;j < M;j++){ if(j != 0)out.print(" "); out.print(table[i][j]); } out.println(); } } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
