Codeforces #389 Div2 A~C
@tookunn_1213 pic.twitter.com/SHGWcrMwJV
— tookunn (@tookunn_1213) 2017年1月6日
考察
rとdを導出する式を見つけ出すのに結構時間掛かってしまった
RかLかは偶奇を見ればよい
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class A { int N,M,K; public void solve() { N = nextInt(); M = nextInt(); K = nextInt(); int r = (int)Math.ceil(((double)K/(2*M))); int d = (int)Math.ceil((K-((double)r-1)*2*M)/2); char s = K%2==1 ? 'L' : 'R'; out.println(r + " " + d + " " + s); } 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()); } }
考察
文字列s,tを同時に一文字ずつ見ていき,その文字の対応を保持していく。
alpha[a] == b && alpha[b] == aの場合は既にaとbの対応が出来ているのでスルー
alpha[a] == -1 && alpha[b] == -1の場合はまだa,b両方に何も対応が出来ていないので,aとbを対応付ける
それ以外の場合は-1
その後はalphaを順に見ていき対応する文字を出力していく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; public class B { String s,t; int[] alpha; public void solve() { s = next(); t = next(); alpha = new int[26]; Arrays.fill(alpha,-1); for(int i = 0;i < s.length();i++){ int a = s.charAt(i) - 'a'; int b = t.charAt(i) - 'a'; if(alpha[a] == b && alpha[b] == a){ continue; }else if(alpha[a] == -1 && alpha[b] == -1){ alpha[b] = a; alpha[a] = b; }else{ out.println(-1); return; } } ArrayList<int[]> ans = new ArrayList<int[]>(); for(int i = 0;i < 26;i++){ if(i == alpha[i])continue; if(alpha[i] == -1)continue; if(i == alpha[alpha[i]]){ ans.add(new int[]{i,alpha[i]}); alpha[alpha[i]] = -1; alpha[i] = -1; } } out.println(ans.size()); for(int[] i : ans){ char a = (char)(i[0]+'a'); char b = (char)(i[1]+'a'); out.println(a + " " + b); } } public static void main(String[] args) { out.flush(); new B().solve(); out.close(); } }
考察
これはEditorial見たけどいまいちよく分からない。
codeforces.com
とりあえず,進んだ方向と逆方向に進むことがわかったら,その度にカウントするみたいな感じっぽい。
与えられた文字列Sを先頭から1文字ずつ見ていき,文字の対応を保持する。
見ている文字S[i]の対となる文字がiより前に出現していたらその文字同士を対応付けて,その他の保持している対応をリセットする。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class C { int N; char[] ch; boolean[] used; public void solve() { N = nextInt(); ch = next().toCharArray(); used = new boolean[4]; int ans = 1; for(int i = 0;i < N;i++){ if(ch[i]=='L'){ if(used[1]){ ans++; Arrays.fill(used,false); } used[0] = true; }else if(ch[i]=='R'){ if(used[0]){ ans++; Arrays.fill(used,false); } used[1] = true; }else if(ch[i]=='U'){ if(used[3]){ ans++; Arrays.fill(used,false); } used[2] = true; }else if(ch[i]=='D'){ if(used[2]){ ans++; Arrays.fill(used,false); } used[3] = true; } } out.println(ans); } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } }