Coder-Strike 2014 - Round 1B: Network Configuration
2問目
1問目より簡単だったと思われる。
こちらも読解に時間がかかったのが敗因
・問題
R1カンパニーにはN個のコンピュータがあり、それらのコンピュータにはそれぞれのデータ送信速度a(1~N)が設定されている。
このとき少なくともK個のコンピュータを同じ速度、また最大の速度で、動作させる必要がある。
データ送信速度の最も高いパソコンのデータ送信速度は任意の値に下げることができるとき、
R1カンパニーが動作させることができる最大のデータ送信速度を求めよ。
・解法
データ送信速度の上からｋ個を同じ値にすればいいので、
aの配列をソートして、値が上からｋ番目に高い要素を出力してやればよい。
・ソースプログラム
import java.util.Arrays; import java.util.Scanner; public class B { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++){ a[i] = sc.nextInt(); } Arrays.sort(a); System.out.println(a[n-k]); sc.close(); } }
こういう問題は5分くらいで解けるようになりたい。
そのためにもやはり英語力を底上げする必要がある。
Coder-Strike 2014 - Round 1A: Poster
一問目
30分もこの問題にかけてしまった。
B問題よりも難しく感じたのは自分だけだろうか？
・問題
N個の区画に分けられた横長のポスターがある。
また、自分は今、k番目の区画の前に立っている。
このポスターのそれぞれの区画に決められたN個のキャラクターを描きたい。
それぞれの区画にキャラクターを描く際には、その区画の前に立たないといけない。
一つの区画にキャラクターを描く作業に1時間
区画の移動(左右どちらでも)に1時間
がかかるとき、
最短で全ての区画のキャラクターを書き終える動きを出力せよ。
※出力オプション
ポスターに”x”を描く→PRINT x
左に移動→LEFT
右に移動→RIGHT
・解法
最短の動きというのは、
①現地点から近い方の端まで移動
↓
②ポスターにキャラクターを描く
↓
③移動
↓
②③をもう一方の端まで繰り返す。
これを実装するだけ。
非常に簡単な問題だが、読解に時間がかかり死亡
・ソース
import java.util.Scanner; public class A { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); String s = sc.next(); int pos = k-1; while(pos!=0 && pos!=n-1){ if(pos <= (n-1)/2){ System.out.println("LEFT"); pos--; }else{ System.out.println("RIGHT"); pos++; } } int way; if(pos==0)way=1; else way=-1; int pos2 = pos; for(int i=0; i<n; i++){ if(way==1){ System.out.println("PRINT "+s.charAt(pos2)); if(i!=n-1)System.out.println("RIGHT"); pos2++; }else{ System.out.println("PRINT "+s.charAt(pos2)); if(i!=n-1)System.out.println("LEFT"); pos2--; } } sc.close(); } }
TLEの罠
前回の記事の通り、Coder-Strike 2014 - Round 1のÇ問題でTLEを食らってしまった。
その際に少し気になったことがあったため、メモ
・最初に提出したソースコード(TLEしたコード)
import java.util.Scanner; public class C { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] s = new String[n]; for(int i=0; i<n; i++){ s[i] = sc.next(); } String ans =""; for(int i=0; i<s[0].length(); i++){ char c = '?'; boolean flag = false; for(int j=0; j<n; j++){ char c2 = s[j].charAt(i); if(c == c2 || c2 == '?'){ continue; }else if(c=='?'){ flag = true; c = c2; }else{ flag = true; c = '?';break; } } if(!flag)c='x'; ans += ""+c; } System.out.println(ans); sc.close(); } }
・後に提出したコード(AC)
import java.util.Arrays; import java.util.Scanner; public class C_3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] s = new String[n]; for(int i=0; i<n; i++){ s[i] = sc.next(); } char[] ans = new char[s[0].length()]; Arrays.fill(ans, '?'); for(int i=0; i<s[0].length(); i++){ boolean flag = false; for(int j=0; j<n; j++){ char c2 = s[j].charAt(i); if(ans[i] == c2 || c2 == '?'){ continue; }else if(ans[i]=='?'){ flag = true; ans[i] = c2; }else{ flag = true; ans[i] = '?';break; } } if(!flag)ans[i]='x'; } System.out.println(ans); sc.close(); } }
1つ目のソースだと大きな入力になると実行時間が1000msを超えTLEとなってしまう
2つ目のソースだと最高でも実行時間は155msと、1つ目のプログラムに比べて断然速い。
しかし、この2つのコード。
違っているのは、答えを格納する"ans"のデータ構造の部分だけ。
その他のアルゴリズムだったりは全て同じである。
一つ目のプログラムでは、初めに
ans = "";
として、適宜ansに文字を付け足していく方針であるのに対し、
2つ目のプログラムでは、
char[] ans;
というようにchar配列で初めに宣言し、それを書き換えていく方針である。
このことから、
ある文字列に後ろから新たな文字を連結させるという動作は処理に時間がかかることが分かる。
一回だけその動作を行うのなら実行時間に影響は無いであろうが、
繰り返しが多くなるときにはそのようなことでも、実行時間に大きく影響してくる。
前々回の記事
http://tkslimee-beginner-procon.hatenablog.com/
でもSystem.out.println()を使うことでTLEが起きてしまっていたが、今回と全く同じである。
今回はfor文の中で、
String ans += c
という処理を入れていたために、TLEが起こってしまった。
実行時間はオーダーだけで決まるわけではない、という教訓でした。
Coder-Strike 2014 - Round 1に参加しました
先日に行われたcodeforcesのCoder-Strike 2014 - Round 1に参加しました。
結果は○○☓☓☓でレートが1428→1355
順調にレートを下げていっている。
今回はC問題を提出することが出来たのでレートがそこまで下がることは無いと思っていたが、
まさかのシステムテストで落とされた(TLE)。無念である。
そのC問題で気になることがあったため後で別途に記事を書きます。
RCC 2014 Warmup (Div. 2) C問題：Football
CodeforcesのRCC2014の予選？に参加した。
結果は2/5問正解。レートは下がって1428
相変わらず問題を解くのが遅い。
問題文が英語ということもあり、問題の意図を汲み取るのにかなりの時間がかかっているのが敗因の一つのように思われる。
では今回は時間内に解けなかったC問題を取り上げる。
・問題
1～NのN個のフットサルチームがある。
それぞれのチームは同盟を結んでいて、N個の全てのチームがそれぞれk回勝利すると決まっている。
一度当たった相手とは二度と当たらない。
「試合数」と「全ての試合の結果(勝ちチームと負けチーム)」を時系列順に出力する。
もし条件に合う試合の組み合わせが無かった場合、-1を出力する。
試合は、数値の順番で行われる。
・方針
まず、どんなときに-1を出力することになるのかを考える。
N個全てのチームがk回ずつ勝利することが出来ないときにというのは例えば
n=5, k=3
等が挙げられる。
これの試合を上から列挙すると
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
と、この段階でチーム3は戦える相手チームがいないので、全てのチームが3回勝つという条件に満たさない。
また、逆に
n=5, k=2
のときは
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
のように条件を満たす。
これを踏まえて、条件を満たせるときというのは、
チームN(最後のチーム)が重複無しでk回勝利できるとき→"チーム数n - 1 > 2k"を満たすとき
である。
説明しにくいのでこの辺にしておく。
出力は、試合を順番に出力するだけ。
・ソース
import java.io.PrintWriter; import java.util.Scanner; public class Main3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int n = sc.nextInt(); int k = sc.nextInt(); sc.close(); if(2*k+1>n){ out.println("-1"); }else{ out.println(k*n); for(int i=1; i<=n; i++){ for(int j=0; j<k; j++){ int count = (i+j)%n+1; out.println(i+" "+count); } } } out.close(); } }
初めは、出力にSystem.out.printlnを使用していたが、
それだと処理に時間がかかるらしく無念のTLE
他の人のソースを参考にして、PrintWriterを使ってみたら、余裕のACだった
そのせいで、こんな問題にかなりの時間を使ってしまったが
オーダー以外にも大切なことは多いということを学べたので、良しとする。
topcoderとcodeforcesを開始
かなり久しぶりの更新。
プログラミングを辞めたわけではなく、日々修行に励んでいたためブログが更新できなかっただけである(半分本当)
この約一ヶ月半の間に世界的なプログラミングコンテストである、「topcoder」と「codeforces」を始めた。
2つともまだ一度しか参加していないためこれからもどんどん参加していきたい
※結果
topcoder:0完(一問も正解できず)→レーティング635
codeforces:2完(二問正解)→レーティング1453
底辺大学生らしい結果を残してしまい大変遺憾ではあるが、腐らずに今後も頑張っていこうと思う。
これからは解いた問題をどんどん上げていく方針でいく
Javaの練習のためにABC#003を解いてみました
今回もいつもどおりABC(Atcoder Beginner Contest)を解いてみました。
javaなどほとんど忘れていた状態だったのですが、毎日書いているとやはり書けるようになってきますね。
それでもまだまだ初心者レベルからは脱出できていませんが。。。
今回はABC#003を解いてみました。
これでbeginner contestの方は全て解き終わったことになります。
初めはビギナーコンテストなのだからどうせ簡単な問題だろう、とたかをくくっていました。
しかし、実際はコンテスト一回につき一問はかなり解き応えのある問題があるので、やりごたえがあります。
リアルタイムで参加したABC#004の4問目は未だに解けていませんし(笑)
宣伝のようになってしまいますが、競技プログラミングを初めてみたい方、プログラミング初心者の方には本当にお勧めです。
では問題の方に移っていきたいと思います。
まず1問目
A: AtCoder社の給料 - AtCoder Beginner Contest #003 | AtCoder
これは簡単な問題なのでパス。以下コード
import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int ans=0; for(int i=1; i<=n; i++){ ans+=10000*i; } System.out.println(ans/n); } }
2問目
B: AtCoderトランプ - AtCoder Beginner Contest #003 | AtCoder
こちらは2問目にしては少し苦戦しました。
私は、一文字ずつ読み取って、それを比べていく方式を取りました。
知らなかったことをメモ
・文字列の長さを求める
int length = s.length();
・文字列の任意の場所の文字を取り出す(今回は先頭の文字を取り出した)
char s1 = s.charAt(i);
i番目の文字を取り出します
以下コード
import java.util.Scanner; public class Main { //トランプ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); String t = sc.next(); char s1; char t1; boolean flag = true; int len = s.length(); for(int i=0; i<len; i++){ s1 = s.charAt(i); t1 = t.charAt(i); //System.out.println(s1+","+t1); if(s1==t1)continue; else if(s1!=t1){ if(s1=='@'){ if(t1=='a'|t1=='t'|t1=='c'|t1=='o'|t1=='d'|t1=='e'|t1=='r'|t1=='@'){ continue; }else{ flag=false;break; } }else if(t1=='@'){ if(s1=='a'|s1=='t'|s1=='c'|s1=='o'|s1=='d'|s1=='e'|s1=='r'|s1=='@'){ continue; }else{ flag=false;break; } }else{ flag=false;break; } } } if(flag)System.out.println("You can win"); else System.out.println("You will lose"); } }
3問目
C: AtCoderプログラミング講座 - AtCoder Beginner Contest #003 | AtCoder
これは一見難しいかと思いきや、アルゴリズムを考えればとても簡単な問題でした。
間違っても全探索なんかで解いてはいけないですね。
N個のレートの中から大きい順にK個を選んで(これはソートで実現)、選んだものをレートの小さい順に計算処理します。
以下コード
import java.util.Scanner; import java.util.Arrays; public class Main { /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); double[] r = new double[n]; double ans = 0; for(int i=0; i<n; i++){ r[i] = sc.nextInt(); } Arrays.sort(r); for(int i=n-k; i<n; i++){ ans = (ans+r[i])/2; } System.out.println(ans); sc.close(); } }
4問目
D: AtCoder社の冬 - AtCoder Beginner Contest #003 | AtCoder
毎回一番難しい4問目ですが、今回は100点満点ではなく101満点でした。
100点の解法はアルゴリズム自体は易しく少し考えれば分かるのですが、問題は実装方法でした。
何かというとこの問題
145180660592914517790287604376765671109248284280228061640640
↑のようなとても大きな桁の数値を扱うのです。
初めはdouble型を用いて書きました。double型は非常に大きな数、小さな数を扱えます。
しかし、その代償に、誤差が生じてしまいます。double型では大きな数や小さな数は指数表記で表すため、数値が丸められてしまいます。そのため正しい答えを出力することはできませんでした。
そこで次はBigDicemal型という型を使って演算を行いました。これを使うことで、intやlongなどで扱えないような大きな数でも誤差なく計算することができ、正しい答えを出力することができました。
詳しくは別の記事でまとめたいと思います。
アルゴリズム説明
①R×Cの長方形の中にあるX×Yの長方形が何通りあるかを求める
②D,Lの置き方が何通りあるのか求める
今回はD+L＝X×Yの場合なのでXYの中に空白は生まれない。よってD(またはL)の置き方が何通りあるのかを求めれば、それが求める組み合わせ数になる。
この組み合わせ数はX×Y個からD(またはL)を選ぶ場合の数なので、(xy)C(d)で求めることができる。
③①と②を掛けあわせたものが全てのパターンとなるのでそれを100000007で割った余りを求める。
こんなかんじです。
以下ソース
import java.util.Scanner; import java.math.BigDecimal; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int r = sc.nextInt(); int c = sc.nextInt(); int x = sc.nextInt(); int y = sc.nextInt(); int d = sc.nextInt(); int l = sc.nextInt(); int p1 = (c-y+1)*(r-x+1); BigDecimal p2; BigDecimal p1b = new BigDecimal(Integer.toString(p1)); BigDecimal up = new BigDecimal(Integer.toString(x*y)); BigDecimal d_d = new BigDecimal(Integer.toString(d)); BigDecimal l_d = new BigDecimal(Integer.toString(l)); BigDecimal upans = new BigDecimal("1"); BigDecimal downans = new BigDecimal("1"); BigDecimal one = new BigDecimal("1"); BigDecimal wari = new BigDecimal("1000000007"); if(d<=l){ for(int i=d; i>=1; i--){ //upans *= up; upans = upans.multiply(up); //downans *= i; downans = downans.multiply(d_d); //up--; up = up.subtract(one); //d_d--; d_d = d_d.subtract(one); } p2 = upans.divide(downans,0,BigDecimal.ROUND_HALF_UP); }else{ for(int i=l; i>=1; i--){ //upans *= up; upans = upans.multiply(up); //downans *= i; downans = downans.multiply(l_d); //up--; up = up.subtract(one); //l_d--; l_d = l_d.subtract(one); } p2 = upans.divide(downans,3,BigDecimal.ROUND_HALF_UP); } BigDecimal p1p2 = p1b.multiply(p2); BigDecimal div = p1p2.divide(wari,0,BigDecimal.ROUND_DOWN); BigDecimal mul = div.multiply(wari); int ans = p1p2.subtract(mul).intValue(); System.out.println(ans); sc.close(); } }
今回はかなり長い記事になってしまいました。
ではこの辺で。
