ファイルの保存時に不要なimport文を削除する

Eclipseにはファイル保存時にソースコードのフォーマット等をいろいろ編集してくれる保管アクションと言うものがあったのでメモ。余分なimport分の削除をやってみる。環境はPleiadesで日本語化済みの3.7.1。表記揺れはあるかも。

Eclipseの設定からJavaエディタ保管アクションのページを開き、保管時に選択したアクションを実行インポートの編成のチェックを入れる。

プロジェクト固有の設定として追加したい場合は,プロジェクトを右クリックしてプロパティJavaエディタ保管アクションを開き、プロジェクト固有の設定を可能にするインポートの編成をチェック。

これとは別にソース・コードのフォーマットにチェックを入れるとファイル保存時に自動的にインデントをそろえてくれる。また、追加アクションの項目をいじると、更にいろいろなソースコードの操作が出来るみたい。

File APIを使って書いたり読んだり

Chrome限定.更に--unlimited-quota-for-filesオプションを付けて起動しないと使えないので注意.

ベンダープレフィックスが必要とわからずに結構詰まったんだけど,こういう情報ってどこを参照すればいいんだろう?

//エラーハンドリング用
var errorCallback = function(e){
  alert("File Error : "+e.code);
};

//書いたり
webkitRequestFileSystem(PERSISTENT, 1024*1024, function(fileSystem){                                                                                                          
  fileSystem.root.getFile("testfile.txt", {'create':true}, function(fileEntry){                                                                                               
    fileEntry.createWriter(function(fileWriter){                                                                                                                              
      var blobBuilder = new WebKitBlobBuilder();                                                                                                                              
      blobBuilder.append("File API Test!!");
 
      fileWriter.onwrite = function(e){                                                                                                                                       
        alert("write completed.");                                                                                                                                            
      };                                                                                                                                                                      
      fileWriter.onerror = function(e){                                                                                                                                       
        alert("write failed : "+e);                                                                                                                                           
      };                                                                                                                                                                      
                                                                                                                                                                                
      fileWriter.write(blobBuilder.getBlob("text/plain"));                                                                                                                      
    }, errorCallback);                                                                                                                                                        
  }, errorCallback);                                                                                                                                                          
}, errorCallback);


// 読んだり
webkitRequestFileSystem(PERSISTENT, 1024*1024, function(fileSystem){
  fileSystem.root.getFile("testfile.txt", null, function(fileEntry){
    fileEntry.file(function(file){
      var fileReader = new FileReader();

      fileReader.onloadend = function(e){
        alert("read completed : "+fileReader.result);
      };
      fileReader.onerror = function(e){
        alert("read failed : "+e);
      };

      fileReader.readAsText(file, "UTF-8");
    }, errorCallback);
  }, errorCallback);
}, errorCallback);

京都大学プログラミングコンテスト(KUPC)参加記

8月6日に行われたKUPCにオンラインから参加してました。
結果は以下の通り。

順位 ユーザ名 A B C D E
73 shirokurostone2 00:05 00:12 00:51 - (2)

A - KUPC

文字列の中に'K','U','P','C'が何回現れるか数える問題。
素直に数えて最小値を出力しました。
stringをincludeし忘れてます。

#include <iostream>
using namespace std;

int main(void){
  string str;
  int k, u, p, c;
  cin >> str;
  k = u = p = c = 0;
  for(int i=0; i<str.size(); i++){
    if      (str[i] == 'K') k++;
    else if (str[i] == 'U') u++;
    else if (str[i] == 'P') p++;
    else if (str[i] == 'C') c++;
  }
  
  cout << min(k, min(u, min(p, c))) << endl;

  return 0;
}

B - 蝉

学校に行くまでに遭遇する蝉の最小値を求める問題。
動的計画法で蝉の最小値を更新していく方法で解きました。
後から見直すと、入力格納用とDP用で配列を2つ使っていたりして効率が悪いですね。

#include <iostream>
#include <cstring>
using namespace std;

int main(void){
  int h, w;
  cin >> h >> w;
  int semi[w][h];
  int dp[w][h];
  memset(dp, 0, sizeof(dp));

  char c;
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cin >> c;
      semi[j][i] = c-'0';
    }
  }

  for(int y=0; y<h; y++){
    for(int x=0; x<w; x++){
      if (x == 0 && y == 0){
        dp[x][y] = semi[x][y];
      }
      else if (y == 0){
        dp[x][y] = dp[x-1][y] +  semi[x][y];
      }
      else if (x == 0){
        dp[x][y] = dp[x][y-1] +  semi[x][y];
      }
      else{
        dp[x][y] = min(dp[x][y-1], dp[x-1][y]) +  semi[x][y];
      }
    }
  }
  cout << dp[w-1][h-1] << endl;
  return 0;

C - しりとり

2文字までしか話せないAIとしりとりをしてAIを負かせる問題。
このような対話型の問題は初めてだったのですが面白いですね。
方針は末尾が同じ文字列を返答し続け、AIの自滅を待つ感じになっています。

#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
  vector<string> talked(100);
  char ai[11];
  int al = 0;
  
  for(int i=0; i<50; i++){

    if (i == 0){
      printf("?a\n");
      talked.push_back(string("a"));
      fflush(stdout);
    }
    else{
      string ai = talked.back();
      while(1){
	al = (al+1)%(26*26);
	string next("   a");
	next = next.replace(0, 1, 1, ai[ai.length()-1]);
	next = next.replace(1, 1, 1, (char)('a' + al/26));
	next = next.replace(2, 1, 1, (char)('a' + al%26));
	if (count(talked.begin(), talked.end(), next) == 0){
	  talked.push_back(next);
	  printf("?%s\n", next.c_str());
	  fflush(stdout);
	  break;
	}
      }
      
    }

    scanf("%s", ai);
    string last = talked.back();
    if (count(talked.begin(), talked.end(), string(ai)) != 0 ||
	last[last.size()-1] != ai[0] ){
      break;
    }
    talked.push_back(string(ai));
  }
  
  printf("!OUT\n");
  fflush(stdout);
  
  return 0;
}

algorithmをincludeするのを忘れコンパイルエラーを出したのはご愛嬌。

D - 列の構成

問題の条件に合うような数列を出力する問題。
A-Cを約1時間で解き、残りの時間をDとFに半分ずつ使いました。
Dは貪欲に先頭から求めていこうと考えていましたが、全問通る気がせず結局断念しました。
乱数で条件に合う数列を探し続ければ解けたそうです。なんてこった。

E - Fox Number

指定された範囲の中から条件に合う数字を数え上げる問題。
これも解法が浮かばずに馬鹿正直に素因数分解してみるソースを書いてみて、TLE出してました。
ちょっと難しい問題になると、どうしようもなくなるのはなんとかしたいですね。

まとめ

C問題が解けてから、残りの4時間ほとんど手が出ていない状態だったのでもう少し解きたかったです。
また、STLのメソッドについて忘れていたり、includeするのを忘れているヘッダがあったりとミスも目立ったので
解法だけではなくミス/不注意を減らせるように練習していきたいと思います。

ACM/ICPC 2011 国内予選 参加記?

早生まれのM2なので今年が最後の挑戦でした.

順位 チーム名 メンバー A B C D E-G
20 Rokkaku @shirokurostone @epee_noir @_shnyh 8:07 25:44 50:58 116:21(+1) -

3時間前

実験室に移動して会場のセットアップ.机を大移動させたり,LANにつないだり,本並べたり.

1時間前

学内のコンビニに買い出しに行く.そこで別チームの@kioa341くんと@slip0110くんに遭遇.
微妙な空気になる.

30分前

15分前

30秒前

時計見ながらカウントダウン

開始

Aを@shirokurostone,Bを@epee_noirくん,Cを@_shnyhくんが担当.

A

@shirokurostone単独で担当.効率とか特に考えず愚直に実装してAC.

B

@epee_noirくんに問題の概要を教えてもらい,解法を二人で考える.
練習のときに似たような問題をやったせいで,そっちの方に引きずられて
解法を間違えて実装.サンプルが通らないので考え直し.
最終的に括弧を置換していけばええんちゃう?ってことに気付いて再実装.
無事AC.

C

@_shnyhくんに問題の概要を教えてもらって,これも解法を考える.
模擬予選のときにC問題の解法を間違えて時間を取られた事があったので
必要以上に計算量を警戒する.
が,結局幅優先以上の解法が思い浮かばなかったので実装開始.
え?計算量大丈夫?とか思ってたけど,サンプルが通ったので大丈夫だった.

D

@epee_noirくんと@_shnyhくんに概要を教えてもらい,
ホワイトボードに図を書きながら3人で考える.
円の上下関係を木で保存して(後々考えればグラフだった),どう取り除いていくかの探索を考える.
これも練習の時に使ったbitDPが適用できる事がわかったので,実装開始.
サンプルは通った!よっしゃ提出だ! -> bus error ( ゚д゚)
gdbで落ちた箇所を調べてみると,DP用の配列に値を確保しているところ.
状態数分は確保しているはずなのになんでやーとか思って調べてみると,
何故か配列サイズが状態数(2^24)より小さい.
あってるはずなのにと思いながら計算した値(16777216)に変更し再挑戦.
(終わってから2^24を1024*1024*4と書いていたが,正しくは1024*1024*16という事に気付いた)
落ちる事なく終了したので提出.がWA.
また固まりかけたが,DP後の最大値を取得するループがおかしかったのを修正し,再チャレンジ.
今度はAC.ちょっともったいない事をした.

E, G

この時点で残り1時間.
また,解ける可能性のありそうなEに手をつける.
が,エリアの分割方法が上手く立たず,Gに移行.
幅優先探索と最短経路かと思ったけど,状態が爆発しそう&確信がなかったのでEに戻る.
この時点でもう時間がなかったので,方針が立たないまま実装を始めたがタイムオーバー.

終了後

Standingsを確認しアジア地区予選に出られることがわかり,一安心したところで,
超笑顔の@kioa341くんが飛び込んできました.

結果

うちの大学から初めて2チーム出場できる事になりました.
国内予選では大学内での潰し合い(で潰される)ことを本気で危惧していたので
両チームとも出られる結果になって本当に良かったです.

11月のアジア地区予選に向けて,頑張っていきたいと思います.

コマンドラインからクリップボードにコピーする

Macのpbcopy,pbpasteコマンドがLinuxでも使いたくて,探してみたら見つかったのでメモしておく。

# コピー
% xsel -b -i

# ペースト
% xsel -b

priority_queueで昇順にソートして要素を取り出す

priority_queueを普通に使うと要素が降順にソートされる。

  priority_queue<int> queue;
  int data[] = {3, 1, 2, 5, 4};

  for(int i=0; i<5; i++){
    queue.push(data[i]);
  }

  while(!queue.empty()){
    cout << queue.top() << " ";
    queue.pop();
  }
  cout << endl;
% ./a.out
5 4 3 2 1

昇順にソートして要素を取り出したい場合はキューを作成するときのテンプレートにgreaterを指定すればOK。

  priority_queue<int, vector<int>, greater<int> > queue;
  int data[] = {3, 1, 2, 5, 4};

  for(int i=0; i<5; i++){
    queue.push(data[i]);
  }

  while(!queue.empty()){
    cout << queue.top() << " ";
    queue.pop();
  }
  cout << endl;
% ./a.out
1 2 3 4 5